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 \]

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} \]

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 \]

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} \]


\[ 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)!} \]

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} \]

Use the Euler-Fermat theorem (Wikipedia).

Exercise 7

Prove that

\[ n^{n^{n^{n}}} – n^{n^{n}} \equiv 0 \pmod{9} \]

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

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} \]

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


[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.)


Leave a comment!