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\equiv0\mod p
$$
Prove that: $\displaystyle\sum_{k|n}d(k)^3=\left(\sum_{k|n}d(k)\right)^2$.
Prove that $d(n)$ is odd if and only if $n$ is a square.
Show that $\phi(d)|\phi(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} + \cdots + 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 = kl$ with $k, l \geq 2$, then
$$
2^n-1=2^{kl}-1=(2^k-1)(2^{k(l-1)}+\cdots+2^k+1)\quad\text{-is composite.}
$$
So for $2^n - 1$ to be prime, we need $n$ to be prime.
Solution of :
$$
\begin{aligned}
(p-1)!&=1\cdot2\cdots q\cdot(q+1)\cdots(p-1)\\
&=q!(p-1)(p-2)\cdots(q+1)\equiv q!(-1)(-2)\cdots(-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\equiv0\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 $\phi(p^m)|\phi(p^k)$. For $m = 0$ this is immediate, while for $m \geq 1$,
$$
\frac{\phi(p^k)}{\phi(p^m)}=\frac{p^k(1-\frac{1}{p})}{p^m(1-\frac{1}{p})}=p^{k-m}\quad\text{ , a positive integer.}
$$
Solution of 6:
Writing $2015! = 2^a3^b5^c\cdots$, we have
$$
c=\sum_{k\geq1}\left[\frac{2015}{5^k}\right]=\left[\frac{2015}{5}\right]+\left[\frac{2015}{25}\right]+\left[\frac{2015}{125}\right]+\left[\frac{2015}{625}\right]=403+80+16+3=502
$$