Finding Large Bases with Large Exponents

Question

I'm given the question to find:

$151 678 213 ^{115431217}\pmod{10}$

I know that 10 is not prime, so I can't use fermats theoreom. So I've attempted using eulers totient function

I know that: $a^{\phi(n)} = 1\pmod n$

Since this is true, this is what I've tried:

$\phi(10) = 4$

$a^4 = 1\pmod {10}$

But what do I do now? I have a large base and a large exponent, and I'm not sure how to continue from here, any help would be much appreciated,

Answer 1

$151678213 \equiv 3$ $mod$ $10$

so

$151678213^{115431217} \equiv 3^{115431217}$

A number ending with $3$ and raised to the power $n$ taken $mod$ $10$ shows a periodic pattern : $1,3,9,7,1...,$ so we just have to take the exponent mod 4 to determine the last digit.

$115431217 \equiv 1$ $mod$ $4$ since $17\equiv 1$ $mod$ $4$

$151678213^{115431217} \equiv 3^{1} \equiv 3$ $mod$ $10$

Note : the periodicity argument can be generalized to non coprime numbers :

$a^b \equiv a^{k}$ $mod$ $m$ with $b \equiv k$ $mod$ $\phi(m)$ and $k\geqslant M$, where $M$ denotes the highest prime power in common with a and m. For example, 10 and 3 share no prime factors, so M=0, but 10 and 4 yields M=1 (they have $2^1$ in common)

Answer 2

If $a = b$ modulo $n$, then $a^k = b^k$ modulo $n$ as well.

So we can replace 151678213 by 3, because these are equal modulo 10.

Then $\phi(10) = (5-1)(2-1) = 4$, so we can reduce the exponent modulo 4, and have the same result, as $3^\phi(n) = 1 $ modulo 10, so we peel off all 4's in the exponent.

As 115431217 equals 1 modulo 4, we have that the result is just $3^1$, so 3.