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:**

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