Solutions to the Second Assignment Basic Algebra

October 7, 2005

Solution of the problem 1. It need not be the case. Here are two counterexamples: a = 2, b = c = 1; or a = 5, b = 2, c = 3.

Solution of the problem 2. Here are again two counterexamples: a = 6, b = 2, c = 3; or a = 9, b = 6, c = 15. Remark The statement will be true if we assume that a is a prime in ℤ.

Solution of the problem 3. First of all, it is readily seen that R = {a + b\sqrt{−5} : a, b ∈ ℤ\}, usually denoted by ℤ[\sqrt{−5}], with usual addition and multiplication of complex numbers, is a ring whose identity element is 1. Also let us recall that in any ring R with identity element 1_{R}, an element α is called a unit if αβ = 1_{R} for some β in R. We now identify all the units in ℤ[\sqrt{−5}].

To do this, it is useful to introduce the norm of an element. For α = a + b\sqrt{−5} ∈ ℤ[\sqrt{−5}], the norm of α is defined by N(α) = a^{2} + 5b^{2} = αᾱ, where ᾱ is the usual complex conjugate of α. The norm function enjoys the following properties:

(1) N(α) ∈ {0, 1, 2, 3, ⋯}; and N(α) = 0 iff α = 0.

(2) α is a unit iff N(α) = 1 iff α = ±1.

(3) α | β implies N(α) | N(β). Note that the first divisibility is in ℤ[\sqrt{−5}], whoever, the second one is in ℤ.

We shall now show that p = 3 is irreducible in ℤ[\sqrt{−5}], i.e., its only divisors are ±1, ± 3. To see this, assume that β | α. So α = βγ for some γ. Taking the norms of both sides, we deduce that 9 = N(β)N(γ). If N(β) = 1, namely if β is a unit, we are done. Likewise we are on the safe side if N(γ) = 1. Thus suppose that N(β) = N(γ) = 3. Writing β = a + b\sqrt{−5}, this is equivalent to a^{2} + 5b^{2} = 3, which is impossible for a, b ∈ ℤ. This concludes the assertion.

For the second part of the problem, note that

3 | 6 = (1 + \sqrt{−5})(1 − \sqrt{−5}).

However, 3 divides neither 1 + \sqrt{−5} nor 1 − \sqrt{−5}. For assume that for example 3 | 1 + \sqrt{−5}, so 1 + \sqrt{−5} = 3(c + d\sqrt{−5}). This in turn implies that 3c = 3d = 1 which is absurd in ℤ.

Remark All these show that ℤ[\sqrt{−5}] is not a unique factorization domain.

Solution of the problem 4. First of all notice that 1 < 2 ≤ 1! + 1, and 2 < 3 ≤ 2! + 1. So, we actually don’t need to require that n be > 2. Let us now recall the following well-known fact:

Every m > 1 has a prime divisor.

We now proceed the proof. By the above fact, it will suffice to show that no prime p ≤ n can divide m = n! + 1. So, suppose that p ≤ n. Therefore p | 1 × 2 × ⋯ × p × ⋯ × n = n!. Now if p | n! + 1, then it has to divide (n! + 1) − n! = 1, which is a contradiction.

To conclude that there are infinitely many primes, note that if we had only a finite number of them, and if p were the largest one, then by what we have shown above, there would be a prime p < q ≤ p! + 1, which is nonsense.

Solution of the problem 5. Let p_{1} = 2, p_{2} = 3, ⋯, p_{k} be the complete list of all primes ≤ N, and let n be an N-smooth number. Thus n = p_{1}^{α_{1}}p_{2}^{α_{2}} ⋯ p_{k}^{α_{k}}, for some nonzero α_{i}’s, and note that this factorization is unique by Fundamental Theorem of Arithmetic. Now let us recall that for −1 < x < 1,

\frac{1}{1 − x} = 1 + x + x^{2} + x^{3} + · · · .

So, for any prime number p, since 0 < \frac{1}{p} < 1, we have

\frac{1}{1 − \frac{1}{p}} = 1 + \frac{1}{p} + \frac{1}{p^{2}} + · · · .

Therefore,

∏_{p≤N} \frac{1}{1 − \frac{1}{p}} = ∏_{i=1}^{k} \frac{1}{1 − \frac{1}{p_{i}}}

= ∏_{i=1}^{k} (1 + \frac{1}{p_{i}} + \frac{1}{p_{i}^{2}} + ⋯) .

Now if we expand the right-hand side, we obtain all the fractions of the form

\frac{1}{p_{1}^{α_{1}}p_{2}^{α_{2}} ⋯ p_{k}^{α_{k}}}, where α_{i}’s are ≥ 0. What we get is in fact the sum of reciprocals

of all N-smooth numbers. Hence

∏_{p≤N} \frac{1}{1 − \frac{1}{p}} = ∑_{all N−smooth n′s} \frac{1}{n}.

Solution of the problem 6. Let us write

S_{N} := ∏_{p≤N} \frac{1}{1 − \frac{1}{p}} .

¿From the previous problem we know that S_{N} = ∑_{all N−smooth n′s} \frac{1}{n}. On the other

hand, since any n ≤ N is clearly N-smooth, so we immediately deduce that

S_{N} ≥ ∑_{n≤N} \frac{1}{n}.

Now taking the limit when N → ∞ and observing that the sum on the righthand sude of the above inequality is in fact the N-th partial sum of the harmonic series (which is divergent), we infer that

lim_{N→∞} ( ∏_{p≤N} \frac{1}{1 − \frac{1}{p}} ) = lim_{N→∞} S_{N} = ∞.

Solution of the problem 7. If we take the natural logarithm of S_{N}, and if we use the well-know expansion

log \frac{1}{1 − x} = x + \frac{x^{2}}{2} + \frac{x^{3}}{3} + ⋯, − 1 < x < 1

we deduce that

log S_{N} = log ∏_{p≤N} \frac{1}{1 − \frac{1}{p}}

= ∑_{p≤N} log \frac{1}{1 − \frac{1}{p}}

= ∑_{p≤N} (\frac{1}{p} + \frac{1}{2p^{2}} + \frac{1}{3p^{3}} + ⋯)

= ∑_{p≤N} \frac{1}{p} + ∑_{p≤N} (\frac{1}{2p^{2}} + \frac{1}{3p^{3}} + ⋯) .  (⋆)

However, the very last sum is bounded above:

∑_{p≤N} (\frac{1}{2p^{2}} + \frac{1}{3p^{3}} + ⋯) ≤ ∑_{p≤N} (\frac{1}{p^{2}} + \frac{1}{p^{3}} + ⋯)

≤ ∑_{all p′s} (\frac{1}{p^{2}} + \frac{1}{p^{3}} + ⋯)

= ∑_{all p′s} \frac{1}{p(p − 1)}

≤ ∑_{all n≥2} \frac{1}{n(n − 1)}
= 1.

Now if N tends to ∞, then S_{N} will go to ∞, so does log S_{N} as well. So the right-hand side of (⋆) has infinite limit when N → ∞, and since the second sum in (⋆) has a finite contribution, we conclude that

∑_{all p′s} \frac{1}{p} = lim_{N→∞} ∑_{p≤N} \frac{1}{p} = ∞.