# Showing that $a^5$ and $a$ have the same last digit using Euler's Theorem.

To show that, in base 10, $a^5$ and $a$ have the same final digit it is sufficient to prove that $$a^5 \equiv a \bmod 10$$

Provided that $a$ and $10$ are coprime then Euler's Theorem proves the result: $$a^{\phi(10)} \equiv 1 \bmod 10$$ where $\phi(10) = \phi(2\cdot 5) = \phi(2)\cdot \phi(5) = 1\cdot 4 = 4$, and hence $$a^4 \equiv 1 \bmod 10 \implies a^5 \equiv a \bmod 10$$

The problem I have is: What if $a$ an $10$ are not coprime?

I have proven the result by going through all of the remainders one-by-one, e.g. if $a \equiv 5 \bmod 10$ then $a^5 \equiv 3125 \bmod 10 \equiv 5 \bmod 10$, etc.

I would like a more general proof, using Euler's Theorem if possible. Checking the remainders isn't practical for larger numbers, e.g. $\bmod 1000$.

• Have you heard about the Chinese remainder theorem? – Arthur Aug 29 '16 at 16:14
• @Arthur Yes: $\mathbb Z/10\mathbb Z \cong \mathbb Z/2\mathbb Z \times \mathbb Z/5\mathbb Z$ where $[a]_{10} \longmapsto ([a]_2,[a]_5)$. – Fly by Night Aug 29 '16 at 16:15
• Another solution is done using induction. – gambler101 Aug 29 '16 at 16:17

## 2 Answers

It's special case $\ p^i = 2,\ q^j = 5,\ \phi = 4,\ k=1\$ of the following generalization of Euler $\!\rm\color{blue}{(E)}$.

Theorem $\ \ n^{\large k+\phi}\equiv n^{\large k}\pmod{p^i q^j}\ \$ assuming that $\ \color{#0a0}{\phi(p^i),\phi(q^j)\mid \phi},\,$ $\, i,j \le k,\,\ p\ne q.\ \ \$

Proof $\ \ p\nmid n\,\Rightarrow\, {\rm mod\ }p^i\!:\ n^{ \phi}\equiv 1\,\Rightarrow\, n^{k + \phi}\equiv n^k,\,$ by $\ n^{\Large \color{#0a0}\phi} = (n^{\color{#0a0}{\Large \phi(p^{ i})}})^{\large \color{#0a0}m}\overset{\color{blue}{\rm (E)}}\equiv 1^{\large m}\equiv 1.$

$\qquad\quad\ \color{#c00}{p\mid n}\,\Rightarrow\, {\rm mod\ }p^i\!:\ n^k\equiv 0\,\equiv\, n^{k + \phi}\$ by $\ n^k = n^{k-i} \color{#c00}n^i = n^{k-i} (\color{#c00}{p\ell})^i$ and $\,k\ge i.$

So $\ p^i\mid n^{k+\phi}\!-n^k.\,$ By symmetry $\,q^j$ divides it too, so their lcm $= p^iq^j\,$ divides it too. $\$ QED

Remark $\$ Obviously the proof immediately extends to an arbitrary number of primes. This leads the way to Carmichael's Lambda function, a generalization of Euler's phi function.

• the coloring is cool. – Thomas Aug 29 '16 at 16:24

What if $a$ and $10$ are not co-prime. then $(2|a)$ or $(5|a)$ or $(10|a).$

$2$ divides $a$ and $10$ does not divide $a.$

Then we have these $4$ elements $\{2,4,6,8\}$

And these form a group. It is cyclical of order $4.$

$a^4\equiv e \pmod{10}\\ a^5\equiv a\pmod{10}$

The identity element of this group turns out to be $6.$

$5$ divides $a$ and $10$ does not divide $a.$

$\forall n, a^n \equiv 5 \pmod {10}$

$10$ divides $a$

$\forall n, a^n \equiv 0 \pmod {10}$

More generally, for any modulo, the integers will fall into to cyclical groups, and the order of those groups will divide $\phi$

• I don't see that in what you have posted. So, then, what is your question? – Doug M Aug 29 '16 at 16:26
• So in the more general case, any integer falls into a cyclic group who's order divides $\phi.$ Another way to look at it is to look at the cosets of $z \cdot G$ where $G$ is the group formed by the integers co-prime to $G.$ and $z$ is any integer, and what groups these cosets form. – Doug M Aug 29 '16 at 16:35