Exercises in Elementary Number Theory (II)

Exercise 1

Let $x_{n}$ be a sequence of positive integers so defined:

$$\begin{array}{l} x_{1}= 2 \\ x_{n + 1} = x_{n}^{2} – x_{n} +1 \quad n \gt 1 \\ \end{array}$$

Prove that the numbers $x_{n}$ are pairwise relatively prime.

Solution
The values of the sequence are obtained by iterating the polynomial $P (x) = x^{2} -x + 1$. Reasoning by induction, it can be easily seen that given $m \lt n$ the following relation hold true:

$$x_{n}= x_{m}Q(x_{m}) +1$$

where $Q (x)$ is a polynomial with integer coefficients. So $(x_{n}, x_{m}) = 1$, as a factor common to $x_{n}$ and $x_{m}$ should divide the number $1$ .

---

Exercise 2

Let p be an odd prime number. Prove that the numerator of the following rational number:

$$1 + \frac{1}{2} + \frac{1}{3}+ \cdots + \frac{1}{p-1}$$

is divisible by $p$.

---

Exercise 3

Let p be an odd prime number greater than $3$. Prove that the numerator of the following rational number:

$$1 + \frac{1}{2} + \frac{1}{3}+ \cdots + \frac{1}{p-1}$$

is divisible by $p^{2}$.

---

Exercise 4

Let $\{p_{1}, p_{2}, \cdots p_{n}, \cdots \}$ be the ordered sequence of primes. Prove that

$$p_{n+1} \le p_{1}p_{2} \cdots p_{n} +1$$

---

Exercise 5

Prove that for every positive integer $N$ there exists a prime number whose sum of decimal places is greater than $N$.

For this exercise we use the following important theorem of Dirichlet (1805-1859):

Theorem (Dirichlet)
Each arithmetic progression $\{an + b, n = 1,2, … \}$ with $(a, b) = 1$ contains infinite primes.
For a proof see for example ^[1].

Hint for exercise 5
For each $N \gt 0$ we have $(10^{N}, 10^{N} -1) = 1$. Dirichlet’s theorem assures the existence of a prime number $p = 10^{N} n + 10^{N} -1$. Note that the $N$ digits of the number $10​​^{N} -1$ are all equal to $9$.

---

Exercise 6

Prove that the last four digits of the numbers $\{5^{n},\ n = 1,2,3 … \}$ form a periodic sequence. Find the period.

Solution
The first values ​​of the sequence are the following:

$$\{5,25,125,625,3125,15625,78125,390625,1953125\}$$

We note that $5^{n + 4} -5^{n} \equiv 0 \pmod {10000}$ if $n \ge 4$, since $5^{4} \cdot (5^{4} -1) = 390000$; therefore the last $4$ digits form a period of length $4$. The period consists of the numbers $\{0625,3125,5625,8125 \}$.

---

Exercise 7

Find all the integers $(m, n)$ such that $m^{4} + 4n ^{4}$ is a prime number.

Hint
Use the following relationship:

$$m^{4} + 4n^{4}=[(m+n)^{2}+n^{2}][(m-n)^{2}+n^{2}]$$

Then, deduce that it must be $(mn)^{2} + n^{2} = 1$ and conclude.

Answer

$$[m = n = 1]$$

---

Exercise 8

The Euler function $f (x) = x^{2} + x + 41$ takes all prime values ​​for $x = 0,1,2, \cdots 39$, as can be verified.
Prove, without making calculations, that it assumes prime values ​​even for negative numbers $x = -1, -2, \cdots -40$.

---

Exercise 9

Prove the following relationship:

$$0 \le \Bigl \lfloor x \Bigr \rfloor – 2 \left \lfloor \frac{x}{2} \right \rfloor \le 1$$

In other words, the expression $\left \lfloor x \right \rfloor – 2 \left \lfloor \frac {x} {2} \right \rfloor$ takes only the values ​​$0$ and $1$.

---

Exercise 10

Let $\{p_{1}, p_{2}, \cdots p_{n}, \cdots \}$ be the ordered sequence of primes. Prove the following inequality:

$$p_{n} \lt 2^{2^{n}}$$

Hint
Use exercise $4$ and proceed by induction.

---

Exercise 11

Let us consider $9$ distinct positive integers whose prime factors lie in the set $\{3,7,11\}$.
Prove that there must be two whose product is a perfect square.

---

Bibliography

^[1]T. Apostol – Introduction to Analytic Number Theory (Springer-Verlag)