# Showing that the last digit of $a$ and $a^{13}$ are the same

For $a \in \mathbb N$, show that the last digit of $a$ and $a^{13}$ are the same.

For example: $2^{13} = 8,192$
$7^{13} = 96,889,010,407$

-
Did you want to say: For $a\in\mathbb{N}$, show that the last digit of $a$ and $a^{13}$ are the same? Because the $13$th root of some numbers might not even have a "last digit" (i.e. be irrational). –  Jesko Hüttenhain Jul 20 '12 at 9:28
Please state the question in the body of the post. –  Did Jul 20 '12 at 9:48

To rephrase the question, you want to show that $a^{13}\equiv a\pmod{10}$, or both $a^{13}\equiv a\pmod2$ and $a^{13}\equiv a\pmod5$. We can do this through the use of Fermat's Little Theorem.

Let's do the case for 5. If $a\equiv 0\pmod5$, then $a^{13}\equiv0^{13}\equiv0\equiv a\pmod5$. Otherwise, we have $a^4\equiv1\pmod5$. So we have $a^{13}=(a^4)^3a\equiv1^3\times a\equiv a\pmod5$.

The case for 2 is similar if you need to prove that an odd number to an integer power is odd and an even number to an integer power is even.

-

Step 1: show that the last digit of $n^{13}$ depends only on the last digit of $n$.
Step 2: check that it's true for $n=0,1,\dots,9$.

-
How does this help? Is there a hidden hint? –  draks ... Jul 20 '12 at 12:58
@draks, no, nothing is hidden. You show that all that matters is the last digit of $n$, and then you look at all 10 possibilities for the last digit of $n$. –  Gerry Myerson Jul 21 '12 at 5:31

If the last digits of a and $a^{n+1}$ where n>1 are same, then 10 |( $a^{n+1}-a)=a(a^n-1)$

<=> 2|$a(a^n-1)$ and 5|$a(a^n-1)$

2 always divides a(a-1) which divides $a(a^n-1)$.

By Fermat's little theorem, 5|$(a^5-a)$ for all integer a.

$(a^5-a) = a(a^4-1)$ divides $a(a^{4k}-1)$ where k is any non-negative integer.

So,the last digits of a and $a^{4k+1}$ will be same. (Here k=3)

-

The last digit of $a^2$ in the set $\{1,2,3,4,5,0\}$ is $\{1, 4, 9, 6, 5, 0\}$ (due to redundancy, I omit $6\le a\le 9$). Then for $a^4$ we get $\{1,6,1,6,5,0\}$, the same for $a^8,a^{12}$ and so forth...

Now multiply $a^4$ once more to get $$\{1,6,1,6,5,0\}\cdot\{1,2,3,4,5,10\}= \{1\cdot 1\; ,6\cdot2\; ,3\cdot1\; ,4\cdot 6\; ,5\cdot 5\; ,0\cdot 10 \}_{\bmod 10} =\{1,2,3,4,5,0\}$$ (think of $\cdot$ as Hadamard product) so you already get your last digit back for $a^5$.

-

Hint: Show that $\varphi(10)=4$ (where $\varphi$ is the Euler totient function) and apply Euler's theorem.

-
OK, but Euler as usually presented applies only to bases prime to the modulus. –  Gerry Myerson Jul 20 '12 at 9:30
Note that working mod 5, $(2n)^4 \equiv 1$ (for n not divisible by 5) so that $(2n)^{12} \equiv 1 \mod 5$ which sorts out the even numbers ($2n \times(5m+1) = 10nm + 2n$). You don't need any heavy machinery to deal with odd or even multiples of 5. –  Mark Bennet Jul 20 '12 at 10:12

Hint $\$ Modular arithmetic using little Fermat-Euler is easiest. Alternatively, directly, note

$$\rm (a+1)^5 - (a+1)\ =\ a^5-a\ +\ \color{#C00}{10}\, \frac{a(a+1)}2\, (a^2+a+1)$$

Hence, by induction $\rm\:\color{#C00}{10}\:|\:a^5-a\,\$ so $\rm\:10\:|\:(a^5 - a)\, (a^8 + a^4 + 1)\, =\, a^{13}-a.\ \$ QED

Remark $\$ More generally we have the following Fermat-Euler-Carmichael

Theorem $\$ For naturals $\rm\: k,m>1$

$\rm\qquad m\ |\ a^k-a\$ for all $\rm\:a\in\mathbb N\ \iff\ m\:$ is squarefree and prime $\rm\: p\:|\:m\: \Rightarrow\: p\!-\!1\ |\ k\!-\!1$

Thus for $\rm\: m = 2\cdot 5,\,$ this yields $\rm\: 10\:|\:a^k-a,\ all\ a\iff 2\!-\!1,5\!-\!1\:|\:k\!-\!1\iff 4\:|\:k\!-\!1$

For related results see some of my prior posts.

-

Claim: For all integers $a$ we have $10|a^5-a$.

This follows from Fermat Little Theorem, but can also be proven elementary.

Proof of the claim

$$a^5-a=a(a-1)(a+1)(a^2+1) \,.$$

Now, one of $a$ or $a+1$ is even thus $a^5-a$ is divisible by $2$.

Also

$$a^5-a=a(a-1)(a+1)(a^2-4+5)=a(a-1)(a+1)(a^2-4)+5a(a-1)(a+1)$$ $$a^5-a=(a-2)(a-1)a(a+1)(a+2)+5a(a-1)(a+1)$$

The product of 5 consecutive integers is always divisible by 5, hence so is $a^5-a$.

This proves the claim.

Proof of your exercise $$a^{13}-a=a^{13}-a^9+a^9-a^5+a^5-a=(a^5-a)(a^8+a^4+1) \,.$$

-