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:
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:
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:
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)
0 Comments