Exercises in Elementary Number Theory (III)

Exercise 1

The Fermat numbers are defined as follows:

\[ F_{n} = 2^{2^{n}} + 1 \quad n =0,1,2,\cdots \]

Prove that all Fermat numbers with \(n \gt 1 \) have the last digit equal to \(7\).

Hint
The number \(2^{2^{2}} = 16 \) ends with the digit \(6 \). The same is therefore true for the numbers \(2^{2^{n}} \) with \(n \gt 2\).
For the properties of Fermat numbers you can see the article on this blog.

---

Exercise 2

Prove that a necessary condition for a number of the form \(n^{n} +1\) to be prime is that \(n = 2^{2^{r}} \).

Hint
Suppose \(n = 2^{t} m \), where \(m \) is odd. If it were \(m \gt 1 \) then \((n^{2^{t}})^{m} +1 \) would be composite, due to the following formula:

\[ a^{2k+1}+b^{2k+1}=(a+b)(a^{2k}-a^{2k-1}b+ \cdots -ab^{2k-1}+b^{2k}) \]

If \(t = 0 \) we are done. If \(t \gt 0 \) then \(t = 2^{r}s \), where \(s \) is odd. By reasoning as above, we can deduce that it must be \(s = 1 \).

---

Exercise 3

Prove the following identity:

\[ \left(1-\frac{1}{2^2}\right)\left(1-\frac{1}{3^2}\right) \cdots \left(1-\frac{1}{n^2}\right)=\frac{n+1}{2n} \]

---

Exercise 4

Prove the following formula:

\[ 2 \cos \left(\frac{\pi}{2^{n+1}}\right)=\sqrt{2+\sqrt{2+ \cdots \sqrt{2}}} \]

where the number of square roots is equal to \(n \).

---

Exercise 5

Prove that if an integer \(n \) is of the form \(n = 4k + 3,\ k \in \mathbb {N} \), then \(n \) has at least one prime factor of the same form.

Hint
The odd primes are all of the form \(4k + 1 \) or \(4k + 3 \). Also note that the product of two numbers of the form \(4k + 1 \) is also of the same form.

---

Exercise 6

Prove that if \(n \) is an odd positive integer then:

\[ \binom{n}{1}-5\binom{n}{2}+5^{2}\binom{n}{3}- \cdots + 5^{n-1}\binom{n}{n} =\frac{1}{5}(1+4^{n}) \]

---

Exercise 7

Prove that the last non-zero digit of \(n! \) is always even, if \(n \gt 2 \).

Hint
We can write \(n! = 2^{r} 5^{s} m \), where \((m, 10) = 1 \). Then we observe that it must always be \(r> s \).
As a further consequence, we can say that the maximum power of \(10 ​​\) which divides \(n! \) is \(10 ​^{s} \).

---

Exercise 8

Let \(d (n) \) be the arithmetic function that counts the number of positive divisors of \(n \). Prove the following formula:

\[ \sum_{k|n}d^{3}(k)=\left(\sum_{k|n}d(k)\right)^{2} \]

For the properties of the \(d (n) \) function, you can see the article in this blog mentioned in the first exercise. See also the article concerning arithmetic functions and in particular Dirichlet product.

Hint
Prove first that both the left and right functions are multiplicative. Then prove the formula for the case \(n = p^{a} \). Also remember the following formula:

\[ \sum_{k=1}^{n}k^{3}=(1+2+ \cdots + n)^{2} \]

---

Exercise 9

Prove that an integer of the form \(4k + 3 \) cannot be the sum of two squares.

Hint
The square of an integer is congruent to \(0 \) or \(1 \) modulo \(4 \).

---

Exercise 10 – Euler

Prove that the Fermat number \(F_{5} = 2^{2^{5}} + 1 \) is divisible by \(641 \).

Hint
Use the relationship \(5 \cdot 2^{7} \equiv -1 \pmod {641} \). Raise to the fourth power and note that \(5 ^ {4} \equiv -16 \pmod {641} \).

The Fermat numbers

\[ F_{0} = 3, F_{1} = 5, F_{2} = 17, F_{3} = 257, F_{4} = 65537 \]

are all prime.
Fermat made the conjecture, in 1650, that all the Fermat numbers are prime. However, no prime Fermat numbers have been found for \(n \ge 5 \) to date. The computed ones are all composite.