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}$
Contents

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

$\sum\limits_{i=0}^{n}x^{i} = \frac {x^{n+1} -1}{x-1}$

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:

$n! = \begin{cases} n \cdot (n-1)! \quad n \gt 0 \\ 1 \qquad \qquad n = 0 \\ \end{cases}$

## 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 .

Solution
We distinguish the following cases:

1. $$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.
2. $$n=p^{a}q^{b}$$
In this case $$\sigma(n)=\sigma(p^{a})\sigma(p^{b})$$. Then
$\sigma(n)=p^{a}q^{b}\left(1 + \frac{1}{p} + \cdots + \frac{1}{p^{a}}\right)\left(1 + \frac{1}{q} + \cdots + \frac{1}{q^{b}}\right)$

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:

$\begin{array}{ll} \dfrac{\pi (n-1)}{n-1} \lt \dfrac{\pi (n)}{n} \quad \text{ (n prime)} \\ \dfrac{\pi (n-1)}{n-1} \gt \dfrac{\pi (n)}{n} \quad \text{(n composite)}\\ \end{array}$

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

$\dfrac{\pi (n)}{n} – \dfrac{\pi (n-1)}{n-1} = \dfrac{1}{n}\left(1 – \dfrac{\pi (n-1)}{n-1}\right)$

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 .
For a good overview see this link to Wikipedia.

## Bibliography

Niven-Zuckerman-Montgomery, An introduction to the Theory of Numbers – V edition – (Wiley, 1991)

Hardy-Wright, An Introduction to the Theory of Numbers – (Oxford U.P.)