In this article we propose some exercises on Elementary Number Theory; they don’t require advanced mathematical knowledge. Other articles will follow with exercises related to this beautiful branch of mathematics.
We recall that the symbol \(\left\lfloor x \right\rfloor\) denotes the integer part of the real number \(x\), i.e. the largest integer that is less than or equal to \(x\). For example \(\lfloor \frac{30}{7} \rfloor=4 , \lfloor -\frac{10}{3} \rfloor=-4\). The following properties easily follow from the definition (\(x \) real number, \(n\) integer):
\[ \begin{array}{l} \lfloor x+n \rfloor = \lfloor x \rfloor + n \\ \\ \left\lfloor \dfrac{x}{n} \right\rfloor = \left\lfloor \dfrac{\left\lfloor x \right\rfloor}{n} \right\rfloor \text { if $n \ge 1$} \end{array} \]Exercise 1
Let \(n \ge 1\) be a positive integer. Prove that the number of digits in the decimal representation is
\[ \lfloor \log_{10}(n) \rfloor + 1 \]Exercise 2
Given a real number \(x\) and a positive integer \(n\), prove the following formula:
\[ \displaystyle \left\lfloor x \right\rfloor + \left\lfloor x+\frac{1}{n} \right\rfloor +\left\lfloor x+ \frac{2}{n} \right\rfloor + \cdots + \left\lfloor x+ \frac{n-1}{n} \right\rfloor – \left\lfloor nx \right\rfloor =0 \]Hint
Let \(F(x)\) the expression on the left. Note that \(F(x)=0\) for each \(x \in [0,\frac{1}{n})\). Then prove that \(F(x + \frac{1}{n})= F(x)\).
Exercise 3
Prove the following properties:
\[ \begin{array}{l} 2^{n} \equiv 1 \pmod{3} \quad \text { if \(n\) is even} \\ 2^{n} \equiv 2 \pmod{3} \quad \text { if \(n\) is odd} \\ \end{array} \]Hint
Recall the following property of congruences: if \( a \equiv b \pmod {n}\) and \(c \equiv d \pmod {n}\) then \( ac \equiv bd \pmod{n} \).
Exercise 4
Compute the following sum:
\[ S = \displaystyle \left\lfloor \frac{1}{3} \right\rfloor + \left\lfloor \frac{2^{1}}{3} \right\rfloor +\left\lfloor \frac{2^{2}}{3} \right\rfloor + \cdots + \left\lfloor \frac{2^{100}}{3} \right\rfloor \]Hint
Use Exercise 3. Also recall the formula of the sum of a geometric progression:
Solution
\[ S=\frac{1}{3}(2^{101}-2)-50 \]Exercise 5
Let \(n,m\) be non-negative integers. Prove that the following expression is always an integer:
\[ \frac{(2m)!(2n)!}{m!n!(m+n)!} \]Hint
Recall the factorial definition of a non-negative integer:
Exercise 6
If \((a,m)=1\) then
\[ a^{k} \equiv a^{k \pmod{\varphi(m)}} \pmod{m} \]Hint
Use the Euler-Fermat theorem (Wikipedia).
Exercise 7
Prove that
\[ n^{n^{n^{n}}} – n^{n^{n}} \equiv 0 \pmod{9} \]Solution
If \(3|n\) we are done. Otherwise use the Euler-Fermat theorem and Exercise 6. Recalling that \( \varphi (9) = 6 \), we have to show that \( n ^ {n ^ {n}} – n ^ {n} \equiv 0 \pmod {6}\). Meanwhile, we have \( n ^ {n ^ {n}} – n ^ {n} \equiv 0 \pmod {2} \). Since we assumed that \(n\) is not divisible by 3, we have to show that \( n ^ {n ^ {n}} – n ^ {n} \equiv 0 \pmod {3}\). This is equivalent to \( n ^ {n} – n \equiv 0 \pmod {\varphi (3)}\). But \( \varphi (3) = 2 \) and since the two members of the congruence have the same parity the formula is proved.
Exercise 8
Prove that an odd perfect number has at least three distinct prime factors. For the perfect numbers see the article in this blog or the book [1].
Solution
We distinguish the following cases:
- \( n = p^{k}\)
In this case \(\sigma(n) = 1+p+p^{2}+ \cdots + p^{k} \lt 2p^{k}=2n\) contrary to the hypothesis that \(n\) is a perfect number. - \( n=p^{a}q^{b}\)
In this case \(\sigma(n)=\sigma(p^{a})\sigma(p^{b})\). Then
We can bound from above the two sums with the respective geometric series obtaining:
\[ \sigma(n) < p^{a}q^{b}\frac{1}{1-\frac{1}{p}}\frac{1}{1-\frac{1}{q}} \]Taking the most unfavorable case for inequality (\(p=3,q=5\)) we finally get
\[ \sigma(n) \lt p^{a}q^{b} \frac{1}{1-\frac{1}{3}}\frac{1}{1-\frac{1}{5}}= \frac{15}{8}p^{a}q^{b} \lt 2n \]contrary to the hypothesis that \(n\) is a perfect number.
In fact, no perfect odd number has been found to date. If they exist they must be very large numbers. For a summary of the mathematical research situation see this link to Wolfram.
Exercise 9
The Goldbach conjecture states that every even number greater than 2 is the sum of two prime numbers.
Prove that the Goldbach conjecture is equivalent to the claim that any even number greater than 4 is sum of 3 primes.
Also show that the Goldbach conjecture implies that every odd number greater than 7 is the sum of three odd prime numbers.
The Goldbach conjecture to date has not yet been proved. For a summary of the results achieved in an attempt to prove Goldbach’s conjecture, see this link to Wolfram.
Exercise 10
We recall the definition of the following arithmetic function
\[ \pi (x) = |\{p \in \mathbb{P} : p \le x\}| \]where \(x\) is a positive real number and \( \mathbb{P}\) represents the set of prime numbers \(\{2,3,5,7,11, \cdots \}\).
Prove the following inequalities:
Solution
If \( n \) is a composite number then \( \pi(n) = \pi(n-1) \) and therefore the second formula is satisfied.
If \( n \) is prime, \(\pi(n) = \pi (n-1) +1\). Then
From this we derive the first formula, given that \(\pi(n) < n \).
The function \(\pi (x)\) plays an important role in the study of the distribution of prime numbers. A fundamental result is the Prime Number Theorem:
\[ \lim_{x \to \infty} \dfrac{\pi (x)}{\left(\dfrac {x}{\ln x}\right)}=1 \]For an “elementary” proof of the theorem that does not use advanced tools of mathematical analysis see [2].
For a good overview see this link to Wikipedia.
Bibliography
[1]Niven-Zuckerman-Montgomery, An introduction to the Theory of Numbers – V edition – (Wiley, 1991)
[2]Hardy-Wright, An Introduction to the Theory of Numbers – (Oxford U.P.)
0 Comments