3
$\begingroup$

This question already has an answer here:

What is the correct answer to this expression:

$26^{32} \pmod {12}$

When I tried in Wolfram Alpha the answer is $4$, this is also my answer using Fermat's little theorem, but in a calculator the answer is different, $0.$

$\endgroup$

marked as duplicate by Carl Mummert, Lee David Chung Lin, Shailesh, Cesareo, Adrian Keister May 1 at 15:40

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.

  • 8
    $\begingroup$ How can it be $0$? $3$ does not divide $26$, so $12 (= 3 \times 4)$ can't divide $26^{32}$ $\endgroup$ – ab123 Oct 27 '18 at 9:39
  • 1
    $\begingroup$ So the answer 4 is correct? $\endgroup$ – Naruto Uzumaki Oct 27 '18 at 9:43
  • 1
    $\begingroup$ yes the answer $4$ is correct $\endgroup$ – ab123 Oct 27 '18 at 9:46
  • 4
    $\begingroup$ I would suggest that, depending on exactly how you did this on a calculator, at some stage the calculator encountered a very large exponent and truncated the result, throwing off the rest of the calculation. $\endgroup$ – Sam Streeter Oct 27 '18 at 9:51
  • $\begingroup$ Alpha failing on such a "basic" computation is more than unlikely. Even the Windows calculator returns $4$ ! (by chance ?) $\endgroup$ – Yves Daoust Oct 27 '18 at 11:03
7
$\begingroup$

First, note that $26 \equiv 2 \pmod {12}$, so $26^{32} \equiv 2^{32} \pmod {12}$.

Next, note that $2^4 \equiv 16 \equiv 4 \pmod {12}$, so $2^{32} \equiv \left(2^4\right)^8 \equiv 4 ^8 \pmod {12}$, and $4^2 \equiv 4 \pmod {12}$.

Finally, $4^8 \equiv \left(4^2\right)^4 \equiv 4^4 \equiv \left(4^2\right)^2 \equiv 4^2 \equiv 4 \pmod {12}$.

Then we get the result.

There are slicker solutions with just a few results from elementary number theory, but this is a very basic method which should be easy enough to follow.

$\endgroup$
  • $\begingroup$ I elaborated on the algebraic essence in my answer, since for beginners that may not be clear from above. $\endgroup$ – Bill Dubuque Oct 29 '18 at 16:50
2
$\begingroup$

Like

Get the last two digits of $16^{100}$ and $17^{100}$

How to find last two digits of $2^{2016}$

last two digits of $14^{5532}$?

Find the last two digits of $2^{2156789}$

$$26\equiv-1\pmod3$$

$\implies26^{2n}\equiv(-1)^{2n}\equiv1\pmod3$ where $n$ is any integer

$\implies26^{2n+2}\equiv1\cdot26^2\pmod{3\cdot26^2}$

$\implies26^{2n+2}\equiv26^2\pmod{3\cdot2^2}\equiv?$

$\endgroup$
2
$\begingroup$

Note that $26\equiv 2\pmod{12}$, so we can as well compute $r=2^{32}\bmod 12$.

We have $2^{32}=12q+r$, so clearly $r=4s$, so we are reduced to compute $2^{30}\bmod 3$ and now we can apply Fermat’s little theorem: $2^2\equiv 1\pmod 3$; thus $2^{30}\equiv 1=s\pmod{3}$ and therefore $r=4$.

$\endgroup$
  • $\begingroup$ Readers may be interested to know that this factoring out of $4$ can be done efficiently operationally using the mod distributive law (an operational reformulation of CRT) - see my answer. $\endgroup$ – Bill Dubuque Oct 27 '18 at 18:50
2
$\begingroup$

$\smash[b]{\text{Note that }\ \overbrace{\color{#0a0}{26}^{\large 32}\!\bmod 12 = \color{#0a0}2^{\large 32}\!\bmod{12}}^{\Large\ \ \color{#0a0}{26\ \equiv\ 2}\pmod{\!12}} \,=\, 2^{\large 2}\overbrace{(\color{#c00}2^{\large 30}\!\bmod 3) = 4((\color{#c00}{-1})^{\large 30}\!\bmod 3)}^{\Large \color{#c00}{2\ \equiv\ -1}\pmod{\!3}} = 4}$

$\smash[t]{\text{The middle equality uses }\,\ \overbrace{ab\ \bmod ac\ =\ a\ (\,b\ \bmod\ c)}}\, =\,$ mod Distributive Law.


Or $ $ we can notice that $\,\color{#c00}{4^{\large n}\equiv 4}\pmod{\!12},$ since it is true mod $3$ & $4\!:$ $\,1^{\large n}\!\equiv 1\,$ & $\,0^{\large n}\!\equiv 0$

So $\bmod 12\!:\ 26^{\large 32}\!\equiv 2^{\large 32}\!\equiv \color{#c00}{4^{\large 16}\!\equiv 4}.\ $ This is the idea behind Sam's answer.

Remark $ $ Numbers like $4$ above with $a^2=a$ are called idempotents. This implies $\,a^{\large n} = a\,$ for all $n\ge 2$ either as above or by a simple induction $\,a^{\large n+1}\! = a\,a^{\large n} = a\cdot a = a.\,$ Said more conceptually: note $a$ is a fixed point of $\,f(x) = ax\,$ i.e. $\,f(a) = a,\,$ and fixed points always stay fixed on iteration by a simple induction: if $\,\color{#c00}{f^n(a) = a}\,$ then $\,f^{\large n+1}(a) = f(\color{#c00}{f^{\large n}(a)}) = f(\color{#c00}a) = a$.

Idempotents $\!\bmod n$ play a fundament role in factorization of integers (and rings) since they correspond to splittings of $n$ into coprime factors, cf. last paragraph here,. However, the first method is more general since the base is generally not idempotent in such exponentiation problems (in fact the mod Distributive Law is essentially an operational form of CRT = Chinese Remainder Theorem - which yields a general way of solving this and related problems).

$\endgroup$
0
$\begingroup$

Note that $26^{32}$ is clearly divisible by $4$ but not by $3$, so the possible congruence classes modulo $12$ are immediately only (represented by) $4$ and $8$. We have $4\equiv 1 \bmod 3$ and $8\equiv 2 \equiv -1 \bmod 3$, so to distinguish between them we only need to know the answer modulo $3$.

This comes down to $(-1)^{32}=1$ (or we can use little Fermat to the same effect) and the answer is therefore $4$.

$\endgroup$
  • $\begingroup$ Splitting the $12$ into the coprime factors $4$ and $3$ is a technique which is substantially generalised in the Chinese Remainder Theorem. The observations in this case are elementary and don't need complex machinery, but it is there if needed to steer the analysis of more complex cases. $\endgroup$ – Mark Bennet Oct 27 '18 at 10:54
  • $\begingroup$ This implicit factoring out of 4 can be explicitly achieved operationally using the mod distributive law (an operational reformulation of CRT) - see my answer. $\endgroup$ – Bill Dubuque Oct 27 '18 at 19:07
  • $\begingroup$ @BillDubuque A useful and interesting perspective as usual! $\endgroup$ – Mark Bennet Oct 27 '18 at 20:51

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