Science:Math Exam Resources/Courses/MATH312/December 2009/Question 06 (b)/Solution 1

The stated problem is equivalent to showing that $\displaystyle 0\equiv a^{4n+1}-a\mod {10}$ which is equivalent to showing that 10 divides $\displaystyle a(a^{4n}-1)$.

To do this, we break this into cases. Since we are looking modulo 10, we only have to discuss the cases when $\displaystyle a\in \{0,1,2,3,4,5,6,7,8,9\}$ since all numbers reduce to one of these modulo 10. We proceed as suggested by the hints.

Case 1: $\displaystyle a=0$. This case clearly satisfies $\displaystyle a\equiv a^{4n+1}\mod {10}$ by a simple substitution. We suppose that a is positive.

Case 2: $\displaystyle 2\mid a$. In this case, notice that clearly 2 divides $\displaystyle a(a^{4n}-1)$ so it suffices to show that 5 divides $\displaystyle a^{4n}-1$. Notice that 5 does not divide a and so $\displaystyle \gcd(a,5)=1$. Thus Euler's Theorem applies giving us that

$\displaystyle 1\equiv a^{\phi (5)}\equiv a^{4}\mod {5}$.

Hence

$\displaystyle a^{4n}-1\equiv (a^{4})^{n}-1\equiv 1^{n}-1\equiv 0\mod {5}$

Thus, 5 divides $\displaystyle a^{4n}-1$ and so 10 divides $\displaystyle a(a^{4n}-1)$.

Case 3: $\displaystyle a=5$. In this case, notice that clearly 5 divides $\displaystyle a(a^{4n}-1)$ so it suffices to show that 2 divides $\displaystyle a^{4n}-1$. This last number is even since $\displaystyle a^{4n}=5^{4n}$ is odd. Thus 10 divides $\displaystyle a(a^{4n}-1)$.

Case 4: $\displaystyle 2\nmid a$ and $\displaystyle a\neq 5$. In this case, $\displaystyle \gcd(a,10)=1$. Thus Euler's Theorem applies giving us that

$\displaystyle 1\equiv a^{\phi (10)}\equiv a^{\phi (2)\phi (5)}\equiv a^{(1)(4)}\equiv a^{4}\mod {10}$.

Hence

$\displaystyle a(a^{4n}-1)\equiv a((a^{4})^{n}-1)\equiv a(1^{n}-1)\equiv 0\mod {10}$

Thus 10 divides $\displaystyle a(a^{4n}-1)$ completing the proof.