4
$\begingroup$

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$
7
  • 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, 2018 at 9:39
  • 1
    $\begingroup$ So the answer 4 is correct? $\endgroup$ Oct 27, 2018 at 9:43
  • 1
    $\begingroup$ yes the answer $4$ is correct $\endgroup$
    – ab123
    Oct 27, 2018 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$ Oct 27, 2018 at 9:51
  • $\begingroup$ Alpha failing on such a "basic" computation is more than unlikely. Even the Windows calculator returns $4$ ! (by chance ?) $\endgroup$
    – user65203
    Oct 27, 2018 at 11:03

5 Answers 5

9
$\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$
0
5
$\begingroup$

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

$\endgroup$
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$
1
  • $\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$ Oct 27, 2018 at 18:50
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$
3
  • $\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$ Oct 27, 2018 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$ Oct 27, 2018 at 19:07
  • $\begingroup$ @BillDubuque A useful and interesting perspective as usual! $\endgroup$ Oct 27, 2018 at 20:51

Not the answer you're looking for? Browse other questions tagged .