Science:Math Exam Resources/Courses/MATH312/December 2008/Question 06 (a)/Statement

The purpose of this problem is to prove the following theorem.

Theorem 1. For all positive integers $\displaystyle a,m$ we have $\displaystyle a^{m}\equiv a^{m-\phi (m)}\mod {m}$

Let $\displaystyle a,m$ be positive integers. For $\displaystyle m=1$, the theorem holds trivially, so we assume from now on that $\displaystyle m>1$ and write its prime-power factorization as $\displaystyle m=p_{1}^{e_{1}}\cdot ...\cdot p_{k}^{e_{k}}$ for different primes $\displaystyle p_{1},...,p_{k}$ and positive integer exponents $\displaystyle e_{1},...,e_{k}$ and some positive integer k. Let $\displaystyle i\in \{1,..,k\}$ and focus on the prime power $\displaystyle p_{i}^{e_{i}}$ in the prime-power factorization of m.

(a) Prove that if $\displaystyle p_{i}\nmid a$ then $\displaystyle p_{i}^{e_{i}}\mid (a^{\phi (m)}-1)$

Hint: Use Euler's theorem and prove/use that $\displaystyle \phi (p_{i}^{e_{i}})\mid \phi (m)$