0
$\begingroup$

This question already has an answer here:

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,

$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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

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

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

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.

$\endgroup$
  • $\begingroup$ What rule/formula is this applying? And so we have 3^ (that exponent) mod 10, do I have to apply another rule here? $\endgroup$ – dgdgrd Apr 17 '16 at 17:55
  • $\begingroup$ 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. $\endgroup$ – Henno Brandsma Apr 17 '16 at 17:58
  • $\begingroup$ 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. $\endgroup$ – dgdgrd Apr 17 '16 at 18:13

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