What is $26^{32}\bmod 12$? [duplicate]

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

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.

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

$\smash[t]{\text{The middle equality uses}\,\ \overbrace{ab\ \bmod ac\ =\,\ a\ (\,b\ \bmod\ c)}}\, =\,$ $\!\bmod\!$ Distributive Law, and we also used $\!\bmod 12\!:^{\phantom{|^{|^{|^|}}}}\!\!\!\! \color{#0a0}{26\equiv 2}\Rightarrow\, \color{#0a0}{26}^{N}\!\equiv \color{#0a0}2^N\,$ by the Power Rule; similarly for $\,\color{#c00}{{2}^N}^{\phantom{|^{|^{|}}}}\!\!\!\!\!\equiv (\color{#c00}{-1})^N\!\pmod{\!3}$

Or $\ \color{#c00}{4^{\large n}\equiv 4}\pmod{\!12},\,$ since it is true $\!\bmod 3$ & $4\!:$ $\,1^{\large n}\!\equiv 1\,$ & $\,0^{\large n}\!\equiv 0,\,$ and $\,(3,4)=1$

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

The $\!\bmod\!$ Distributive Law allows us to do this induction purely arithmetically, by cancelling out a factor to reduce it to the trivial induction $\,\color{#c00}1^n\equiv 1.\,$ Let's examine closely how it performs this.

Generally if $\,a^2\equiv a\pmod{\!n}\,$ then $\,n\mid a(a\!-\!1)\,$ thus $\, n = cm,\ c\mid a,\ \color{#c00}{m\mid a\!-\!1},\,$ hence

$$ a^{1+n}\bmod cm = c\overbrace{((a/c) a^n\bmod m)}^{\textstyle \color{#c00}{a}^n\equiv\color{#c00}1^n\!\pmod{\!m}} = c(a/c) = a\qquad$$

therefore $\bmod n\!:\,\ a^2\equiv a\,\Rightarrow\, a^{1+n}\equiv a,\,$ proved using only the trivial induction $\,\color{#c00}1^n\equiv 1$

Or $\ \color{#c00}{a^{\large n}\equiv a}\pmod{\!(a\!-\!1)a},\,$ since it is true mod $\,a\!-\!1\,$ & $\,a\!:$ $\,1^{\large n}\!\equiv 1\,$ & $\,0^{\large n}\!\equiv 0,\,$ so it's also true $\!\bmod {\rm lcm}(a\!-\!1,a) = (a\!-\!1)a\,$ by CCRT, so the congruence persists $\!\bmod n\!=\!ac\mid (a\!-\!1)a$

Or using the Factor Theorem: $\,c\mid a,\ m\mid a\!-\!1\mid a^{n-1}\!-1\,\Rightarrow\, n=cm\mid a(a^{n-1}\!-1)$

It is instructive to examine the relationship between the various methods.

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 our first method using the mod Distributive Law is more general since the base is generally not idempotent in such exponentiation problems (in fact the $\!\bmod\!$ Distributive Law is essentially an operational form of CRT = Chinese Remainder Theorem - which yields a general way of solving this and related problems).

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

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