1
$\begingroup$

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$.

$\endgroup$
  • 2
    $\begingroup$ Have you heard about the Chinese remainder theorem? $\endgroup$ – Arthur Aug 29 '16 at 16:14
  • $\begingroup$ @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)$. $\endgroup$ – Fly by Night Aug 29 '16 at 16:15
  • $\begingroup$ Another solution is done using induction. $\endgroup$ – gambler101 Aug 29 '16 at 16:17
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ the coloring is cool. $\endgroup$ – Thomas Aug 29 '16 at 16:24
0
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ I don't see that in what you have posted. So, then, what is your question? $\endgroup$ – Doug M Aug 29 '16 at 16:26
  • $\begingroup$ 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. $\endgroup$ – Doug M Aug 29 '16 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.