# Finding Large Bases with Large Exponents [duplicate]

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,

## marked as duplicate by hardmath, gebruiker, Daniel W. Farlow, Leucippus, choco_addictedApr 18 '16 at 1:55

• $\phi(10)$ is not really 3. – Ivan Neretin Apr 17 '16 at 17:37
• Fixed ,typo sorry. – dgdgrd Apr 17 '16 at 17:38
• OK, now consider this: $151\,678\,213^n\equiv3^n\pmod{10}$ – Ivan Neretin Apr 17 '16 at 17:39
• Not a duplicate, 10 is not prime and fermats theorem can't be used. It would help if you actually read my question. – dgdgrd Apr 17 '16 at 17:42
• But Ivan's remark is correct: we can replace 151... by 3 – Henno Brandsma Apr 17 '16 at 17:51

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

• To see the result mod 4, just look at the last 2 digits (as all powers of 100 are 0 mod 4). – Henno Brandsma Apr 17 '16 at 18:07
• @HennoBrandsma Thank you, edited my post so it is shorter. – Evariste Apr 17 '16 at 18:24

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.

• What rule/formula is this applying? And so we have 3^ (that exponent) mod 10, do I have to apply another rule here? – dgdgrd Apr 17 '16 at 17:55
• They're representing the same element in the group $\mathbb{Z}_n$ (all integers modulo $n$). So it's trivial their powers (in that group!) have the same residue as well. – Henno Brandsma Apr 17 '16 at 17:58
• I accepted /u/Evariste answer because it went into more detail on how to do such questions in general, if I could Upvote you I would. As I do appreciate the effort in making this question make sense for me. – dgdgrd Apr 17 '16 at 18:13