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

The purpose of this problem is to prove the following tThe 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.

(c) Prove that $\displaystyle p_{i}^{e_{i}}\mid (a^{n}-a^{m-\phi (m)})$

Hint: Combine the results of (a) and (b).