Chapter 5 Number Theory

Discrete Mathematics

CHAPTER 5

Let $a, n$ be positive integers with $a, n \geq 2$ . Show that for $a^{n} - 1$ to be prime, we need $a = 2$ and $n$ to be prime.

Let p be an odd prime and let $q = \frac{p - 1}{2}$ . Use Wilson' s Theorem to prove that
$(q!)^{2} + (- 1)^{q} \equiv 0 \mod p$

Prove that: $\sum_{k | n} d (k)^{3} = {(\sum_{k | n} d (k))}^{2}$ .

Prove that $d (n)$ is odd if and only if $n$ is a square.

Show that $ϕ (d) | ϕ (n)$ whenever $d | n$ .

Find the power of $5$ in the prime factorization of $2015!$

Solution

Solution of 1 :

Since $a^{n} - 1 = (a - 1) (a^{n - 1} + a^{n - 2} + \dots + a + 1)$ and $a - 1 > 1$ if $a > 2$ , it follows that $a^{n} - 1$ can only be prime if $a = 2$ . Consider $2^{n} - 1$ . If $n = k l$ with $k, l \geq 2$ , then
$2^{n} - 1 = 2^{k l} - 1 = (2^{k} - 1) (2^{k (l - 1)} + \dots + 2^{k} + 1) -is composite.$
So for $2^{n} - 1$ to be prime, we need $n$ to be prime.

Solution of :

$\begin{aligned} (p - 1)! & = 1 \cdot 2 \dots q \cdot (q + 1) \dots (p - 1) \\ = q! (p - 1) (p - 2) \dots (q + 1) \equiv q! (- 1) (- 2) \dots (- q) \mod p \\ = (- 1)^{q} (q!)^{2} . \end{aligned}$
But by Wilson' s Theorem, $(p - 1)! \equiv - 1 \mod p$ . Hence $(q!)^{2} \equiv (- 1)^{q} (p - 1)! \equiv - (- 1)^{1} \mod p$ ;

i.e. $(q!)^{2} + (- 1)^{q} \equiv 0 \mod p$ .

Solution of :

By multiplicativity, the result folllows if we can show that for $p$ prime and $k \geq m \geq 0$ (integers) we have $ϕ (p^{m}) | ϕ (p^{k})$ . For $m = 0$ this is immediate, while for $m \geq 1$ ,
$\frac{ϕ (p^{k})}{ϕ (p^{m})} = \frac{p^{k} (1 - \frac{1}{p})}{p^{m} (1 - \frac{1}{p})} = p^{k - m}, a positive integer.$

Solution of 6:

Writing $2015! = 2^{a} 3^{b} 5^{c} \dots$ , we have
$c = \sum_{k \geq 1} [\frac{2015}{5^{k}}] = [\frac{2015}{5}] + [\frac{2015}{25}] + [\frac{2015}{125}] + [\frac{2015}{625}] = 403 + 80 + 16 + 3 = 502$