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 $a, m$ we have $a^{m} \equiv a^{m - ϕ (m)} mod m$

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

(c) Prove that $p_{i}^{e_{i}} ∣ (a^{n} - a^{m - ϕ (m)})$

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