Fermats Little Theorem and Eulers Theorem

Powers in Modular Arithmetic

In the last topic we dealt with linear congruences like $ax\equiv c(\mathrm{mod}n)$. The natural next step is congruences involving higher powers of $x$, such as $x^2\equiv c(\mathrm{mod}n)$; but before we can say anything about those, we need to understand how powers behave in ${\mathbb{Z}}_n$ in the first place.

Consider the powers of every element of ${\mathbb{Z}}_7$:

Notice how much structure is hiding in here:

• In every row except $0^k$, a $1$ eventually appears.
• Column $6$ is (almost) all $1$'s, and column $7$ is identical to column $1$; raising to the power $7$ does nothing in ${\mathbb{Z}}_7$.
• The first $1$ in each row appears in column $1,2,3$ or $6$; always a divisor of $6$.
• The cycle of entries in row $x^k$ is the reverse of the cycle in row $(x^{-1}{)}^k$.
• Going down the rows, the entries of column $2$ cycle with length $3$, and the entries of column $3$ cycle with length $2$.

Running the same experiment in ${\mathbb{Z}}_{11}$ tells the same story: column $10$ is (almost) all $1$'s, column $11$ repeats column $1$, and the first $1$ of each row lands in column $1,2,5$ or $10$ — again, always a divisor of $10$.

So in ${\mathbb{Z}}_p$ it looks like $a^{p-1}=1$ for every $a\ne 0$, and $a^p=a$ for absolutely every $a$. This is not a coincidence.

Fermat's Little Theorem

Basically, modulo a prime, raising to the power $p$ is invisible, and every residue that is not a multiple of $p$ resets to $1$ after exactly $p-1$ steps; this is precisely the "column $6$ is all $1$'s, column $7$ copies column $1$" pattern from the tables. For $p\nmid a$ the two forms are equivalent (multiply the second by $a$ to get the first), but they are not interchangeable in general. The second form requires $p\nmid a$; if $p\mid a$ then $a\equiv 0(\mathrm{mod}p)$ and no power of it will ever be $1$.

Proof.
If $p\mid a$, then $a\equiv 0(\mathrm{mod}p)$, so $a^p\equiv 0\equiv a(\mathrm{mod}p)$ and the first form holds trivially.
So suppose that $p\nmid a$, and consider the $p-1$ numbers

$$a,2a,3a,\dots ,(p-1)a(\mathrm{mod}p).$$

None of these is $0$ modulo $p$; if $p\mid ia$ then, since $p$ is prime, $p\mid i$ or $p\mid a$, and both are impossible for $1\le i\le p-1$. They are also pairwise distinct modulo $p$; if $ia\equiv ja(\mathrm{mod}p)$ then $p\mid (i-j)a$, and since $p\nmid a$ we must have $p\mid i-j$, which forces $i=j$ as $|i-j|\le p-2<p$.

So the list above is just $1,2,\dots ,p-1$ rearranged. Multiplying everything together,

$$\begin{array}{rl}a\cdot 2a\cdot 3a\cdots (p-1)a& \equiv 1\cdot 2\cdot 3\cdots (p-1)(\mathrm{mod}p),\\ a^{p-1}(p-1)!& \equiv (p-1)!(\mathrm{mod}p).\end{array}$$

Since $p$ is prime, it divides none of $1,2,\dots ,p-1$, so $\gcd ((p-1)!,p)=1$ and $(p-1)!$ is a unit modulo $p$; cancelling it from both sides gives

$$a^{p-1}\equiv 1(\mathrm{mod}p).■$$

To see the rearrangement step in action, take $p=7$ and $a=3$;

$$\{3,6,9,12,15,18\}\equiv \{3,6,2,5,1,4\}(\mathrm{mod}7),$$

which really is $\{1,2,3,4,5,6\}$ shuffled.

Example. Find $50^{97}\mathrm{mod}97$.
Here $97$ is prime, so the first form of Fermat's Little Theorem applies to every integer with no coprimality check needed;

$$\begin{array}{rl}50^{97}& \equiv 50(\mathrm{mod}97).\end{array}$$

Therefore, $50^{97}\mathrm{mod}97=50$; the exponent matching the modulus means we get the answer for free.

Example. Find $99^{100}\mathrm{mod}101$, and hence find $99^{909}\mathrm{mod}101$.
Since $101$ is prime and $101\nmid 99$, the second form gives

$$99^{100}\equiv 1(\mathrm{mod}101),$$

so $99^{100}\mathrm{mod}101=1$. For the second power, we peel off as many blocks of $100$ from the exponent as possible; each block collapses to $1$. Writing $909=9\cdot 100+9$ and noticing that $99\equiv -2(\mathrm{mod}101)$,

$$\begin{array}{rl}99^{909}& ={\left(99^{100}\right)}^9\cdot 99^9\\ & \equiv 1^9\cdot 99^9(\mathrm{mod}101)\\ & \equiv (-2{)}^9(\mathrm{mod}101)\\ & \equiv -512(\mathrm{mod}101)\\ & \equiv -512+6\cdot 101(\mathrm{mod}101)\\ & \equiv 94(\mathrm{mod}101).\end{array}$$

Therefore, $99^{909}\mathrm{mod}101=94$. Notice how switching $99$ for $-2$ turned an impossible-looking power into something you can do by hand.

Reducing Exponents Modulo a Prime

The "peel off blocks of $p-1$" trick from the last example is worth stating as a theorem in its own right.

Proof. By the division theorem, write $k=q(p-1)+r$ where $r=k\mathrm{mod}(p-1)$, so $0\le r<p-1$. Then

$$\begin{array}{rl}{a}^k& =a^{q(p-1)+r}\\ & ={\left(a^{p-1}\right)}^q\cdot a^r\\ & \equiv 1^q\cdot a^r(\mathrm{mod}p),\text{ (by Fermat’s Little Theorem, as }p\nmid a\text{)}\\ & \equiv a^r(\mathrm{mod}p).■\end{array}$$

Basically, when working modulo a prime $p$, the bases live in ${\mathbb{Z}}_p$ but the exponents live in ${\mathbb{Z}}_{p-1}$. It is important to remember that exponents get reduced modulo $p-1$, not modulo $p$; reducing an exponent mod $p$ is the classic exam mistake.

$$\boxed{p\nmid a⟹a^k\equiv a^{k\mathrm{mod}(p-1)}(\mathrm{mod}p).}$$

Example. Find $3^{1000}\mathrm{mod}7$.
Here $7$ is prime and $7\nmid 3$, so exponents can be reduced modulo $7-1=6$;

$$\begin{array}{rl}1000& =6\cdot 166+4,\\ 3^{1000}& \equiv 3^4(\mathrm{mod}7)\\ & \equiv 81(\mathrm{mod}7)\\ & \equiv 81-77(\mathrm{mod}7)\\ & \equiv 4(\mathrm{mod}7).\end{array}$$

Therefore, $3^{1000}\mathrm{mod}7=4$.

Powers in Non-Prime Moduli

Fermat's Little Theorem is strictly about prime moduli. To see what breaks otherwise, here is the power table for ${\mathbb{Z}}_9$:

We can observe some familiar patterns, and one new pathology:

• A $1$ eventually appears in every row except $0^k$, $3^k$ and $6^k$.
• Column $6$ is mostly $1$'s, and column $7$ is similar to column $1$.
• The first $1$ in each row appears in column $1,2,3$ or $6$.
• The rows for $3$ and $6$ collapse to $0$ and never recover.

The rows that die are exactly the elements sharing a factor with $9$; indeed $3^2=9\equiv 0$, and once you hit $0$ you stay there. The rows that do return to $1$ are exactly the units of ${\mathbb{Z}}_9$, and there are $6$ of them — which explains why column $6$ plays the role that column $p-1$ played in the prime tables. What we need is a function that counts these "good" elements for an arbitrary modulus.

Euler's Totient Function

Recall from Modular Rings and Units that $a\in {\mathbb{Z}}_n^{\ast }⟺\gcd (a,n)=1$; so $\varphi (n)$ is exactly the number of units in ${\mathbb{Z}}_n$,

$$\boxed{\varphi (n)=|{\mathbb{Z}}_n^{\ast }|.}$$

Basically, $\varphi (n)$ counts how many residues mod $n$ you are allowed to divide by; equivalently, how many rows of the power table will eventually return to $1$.

Example. Find the following values.

• $\varphi (7)=6$; since $7$ is prime, all of $1,2,3,4,5,6$ are coprime with it.
• $\varphi (9)=6$; we only delete the multiples of $3$, leaving $\{1,2,4,5,7,8\}$ — matching the six "surviving" rows in the ${\mathbb{Z}}_9$ table above.
• $\varphi (12)=4$; the survivors are $\{1,5,7,11\}$.
• $\varphi (15)=8$; the survivors are $\{1,2,4,7,8,11,13,14\}$.
• For any prime number $p$, we have $\varphi (p)=p-1$; every one of $1,2,\dots ,p-1$ is coprime with $p$.

Notice that the $p-1$ in Fermat's Little Theorem was really $\varphi (p)$ in disguise; this is the observation that Euler generalised.

Totients of Prime Powers

Computing $\varphi (n)$ straight from the definition means checking a gcd for every single $a\le n$, which is hopeless for large $n$. The following two results reduce the whole computation to knowing the prime factorisation of $n$.

Proof. The only prime factor of $p^k$ is $p$, so $\gcd (a,p^k)>1$ if and only if $p\mid a$. Hence we take all $p^k$ integers in $1,2,\dots ,p^k$ and delete the multiples of $p$, which are

$$p,2p,3p,\dots ,p^{k-1}\cdot p;$$

there are exactly $p^{k-1}$ of them. Everything remaining is coprime with $p^k$, so $\varphi (p^k)=p^k-p^{k-1}$. $■$

Basically, exactly $1$ in every $p$ consecutive integers is a multiple of $p$, so a prime power keeps a $\left(1-\frac{1}{p}\right)$ share of its residues as units.

Example. Find $\varphi (8)$ and $\varphi (125)$.

$$\begin{array}{rl}\varphi (8)=\varphi (2^3)& =2^3-2^2\\ & =8-4\\ & =4,\\ \varphi (125)=\varphi (5^3)& =5^3-5^2\\ & =125-25\\ & =100.\end{array}$$

As a sanity check for the first one, the odd residues $\{1,3,5,7\}$ are precisely the units of ${\mathbb{Z}}_8$; there are indeed $4$ of them. Therefore, $\varphi (8)=4$ and $\varphi (125)=100$.

The Totient is Multiplicative

Proof. First, notice that $\gcd (a,mn)=1$ if and only if $\gcd (a,m)=1$ and $\gcd (a,n)=1$; any prime dividing both $a$ and $mn$ must divide $m$ or $n$, and conversely any common prime factor of $a$ and $m$ (or $n$) also divides $mn$.

Now write the integers $1,2,\dots ,mn$ in a grid with $m$ columns, so that column $c$ contains

$$c,m+c,2m+c,\dots ,(n-1)m+c.$$

Every entry of column $c$ is congruent to $c$ modulo $m$; so the columns containing numbers coprime with $m$ are exactly the columns with $\gcd (c,m)=1$, and there are $\varphi (m)$ of these.

Fix one such column and reduce its $n$ entries modulo $n$. They are pairwise distinct; if $im+c\equiv jm+c(\mathrm{mod}n)$ then $n\mid (i-j)m$, and since $\gcd (m,n)=1$ we get $n\mid i-j$, forcing $i=j$ as $|i-j|<n$. So the $n$ entries of the column hit every residue modulo $n$ exactly once, and hence exactly $\varphi (n)$ of them are coprime with $n$.

Counting: $\varphi (m)$ good columns, each contributing $\varphi (n)$ entries coprime with both $m$ and $n$; i.e. coprime with $mn$. Therefore $\varphi (mn)=\varphi (m)\varphi (n)$. $■$

To see this concretely with $m=3$ and $n=4$, lay out $1$ to $12$:

Column $3$ is dead (everything shares the factor $3$), while columns $1$ and $2$ each contain every residue mod $4$ once, hence $\varphi (4)=2$ units each. That gives $\varphi (3)\varphi (4)=2\cdot 2=4$ units in total, and indeed ${\mathbb{Z}}_{12}^{\ast }=\{1,5,7,11\}$.

It is important to note that $\varphi$ is only multiplicative when $\gcd (m,n)=1$; for instance $\varphi (4)=2$ but $\varphi (2)\varphi (2)=1\cdot 1=1$. Always split $n$ into coprime pieces (i.e. into distinct prime powers), never arbitrary factors.

Example. Find $\varphi (360)$.
Factorising and splitting into pairwise coprime prime powers,

$$\begin{array}{rl}360& =2^3\cdot 3^2\cdot 5,\\ \varphi (360)& =\varphi (2^3)\varphi (3^2)\varphi (5)\\ & =(2^3-2^2)(3^2-3)(5-1)\\ & =4\cdot 6\cdot 4\\ & =96.\end{array}$$

Therefore, $\varphi (360)=96$; there are $96$ units in ${\mathbb{Z}}_{360}$.

Combining the two theorems gives a one-line formula:

Basically, each distinct prime factor independently deletes its own $\frac{1}{p}$ share of the residues. Notice that the exponents in the factorisation never appear in the product; only which primes divide $n$ matters, with the exponents hiding inside the leading factor of $n$.

Example. Find $\varphi (1000)$.

$$\begin{array}{rl}1000& =2^3\cdot 5^3,\\ \varphi (1000)& =1000\left(1-\frac{1}{2}\right)\left(1-\frac{1}{5}\right)\\ & =1000\cdot \frac{1}{2}\cdot \frac{4}{5}\\ & =400.\end{array}$$

Therefore, $\varphi (1000)=400$.

Euler's Theorem

We can now generalise Fermat's Little Theorem to any modulus, with $\varphi (n)$ stepping into the role of $p-1$.

Setting $n=p$ prime recovers Fermat's Little Theorem exactly, since $\varphi (p)=p-1$ and $\gcd (a,p)=1$ is the same condition as $p\nmid a$. Basically, the units of ${\mathbb{Z}}_n$ all return to $1$ after $\varphi (n)$ steps — which is why column $6$ worked in the ${\mathbb{Z}}_9$ table ($\varphi (9)=6$) even though $9$ is not prime. Unlike Fermat's Little Theorem, there is no "first form" here: if $\gcd (a,n)\ne 1$ then Euler's Theorem says nothing at all about $a$.

The proof is the same permutation trick as before, but run over the units instead of over all nonzero residues.

Proof. Let $r_1,r_2,\dots ,r_{\varphi (n)}$ be the elements of ${\mathbb{Z}}_n^{\ast }$; by definition of $\varphi$ there are exactly $\varphi (n)$ of them. Since $\gcd (a,n)=1$, $a$ is itself a unit, and products of units are units, so each $a{r}_i\in {\mathbb{Z}}_n^{\ast }$. Moreover the $a{r}_i$ are pairwise distinct in ${\mathbb{Z}}_n$; if $a{r}_i\equiv a{r}_j(\mathrm{mod}n)$, multiplying both sides by $a^{-1}$ (which exists as $a$ is a unit) gives $r_i\equiv r_j$, so $i=j$. Hence $a{r}_1,a{r}_2,\dots ,a{r}_{\varphi (n)}$ is just $r_1,r_2,\dots ,r_{\varphi (n)}$ rearranged. Multiplying everything together,

$$\begin{array}{rl}(a{r}_1)(a{r}_2)\cdots (a{r}_{\varphi (n)})& \equiv r_1{r}_2\cdots r_{\varphi (n)}(\mathrm{mod}n),\\ a^{\varphi (n)}R& \equiv R(\mathrm{mod}n),\text{ (where }R=r_1{r}_2\cdots r_{\varphi (n)}\text{)}.\end{array}$$

Since $R$ is a product of units, it is itself a unit; multiplying both sides by $R^{-1}$ gives

$$a^{\varphi (n)}\equiv 1(\mathrm{mod}n).■$$

For a concrete instance of the shuffle, take $n=15$ and $a=7$; the units of ${\mathbb{Z}}_{15}$ are $\{1,2,4,7,8,11,13,14\}$, and multiplying each by $7$ gives

$$\{7,14,13,4,11,2,1,8\}(\mathrm{mod}15),$$

the same set shuffled.

Example. Find $7^{89}\mathrm{mod}15$.
First, $\gcd (7,15)=1$, so Euler's Theorem applies, and

$$\varphi (15)=\varphi (3)\varphi (5)=2\cdot 4=8,$$

so $7^8\equiv 1(\mathrm{mod}15)$. Reducing the exponent,

$$\begin{array}{rl}89& =8\cdot 11+1,\\ 7^{89}& ={\left(7^8\right)}^{11}\cdot 7^1\\ & \equiv 1^{11}\cdot 7(\mathrm{mod}15)\\ & \equiv 7(\mathrm{mod}15).\end{array}$$

Therefore, $7^{89}\mathrm{mod}15=7$.

Example. Find $5^{44}\mathrm{mod}18$ and $5^{77}\mathrm{mod}18$.
Here $\gcd (5,18)=1$ and

$$\varphi (18)=\varphi (2)\varphi (9)=1\cdot 6=6,$$

so $5^6\equiv 1(\mathrm{mod}18)$ and exponents can be reduced modulo $6$. For the first power, $44=6\cdot 7+2$, so

$$\begin{array}{rl}{5}^{44}& \equiv 5^2(\mathrm{mod}18)\\ & \equiv 25(\mathrm{mod}18)\\ & \equiv 7(\mathrm{mod}18).\end{array}$$

For the second, $77=6\cdot 12+5$, so $5^{77}\equiv 5^5(\mathrm{mod}18)$. Rather than grinding out $5^5=3125$, notice that $5^3=125=126-1\equiv -1(\mathrm{mod}18)$;

$$\begin{array}{rl}{5}^{77}& \equiv 5^5(\mathrm{mod}18)\\ & \equiv 5^3\cdot 5^2(\mathrm{mod}18)\\ & \equiv (-1)\cdot 7(\mathrm{mod}18)\\ & \equiv -7(\mathrm{mod}18)\\ & \equiv 11(\mathrm{mod}18).\end{array}$$

Therefore, $5^{44}\mathrm{mod}18=7$ and $5^{77}\mathrm{mod}18=11$. Spotting a power congruent to $-1$ is one of the best shortcuts available; it halves the effective cycle length.

Example. Find $2^{100}\mathrm{mod}12$.
The tempting move is: $\varphi (12)=4$ and $100\equiv 0(\mathrm{mod}4)$, "so" $2^{100}\equiv 2^0=1(\mathrm{mod}12)$. This is wrong; $\gcd (2,12)=2\ne 1$, so Euler's Theorem does not apply and you are not allowed to reduce the exponent. Indeed every positive power of $2$ is even, so none of them can possibly be congruent to $1$ modulo $12$.

The correct approach is to split $12$ into coprime pieces, $12=4\cdot 3$, and study each separately;

$$\begin{array}{rl}{2}^{100}& \equiv 0(\mathrm{mod}4),\text{ (since }4=2^2\mid 2^{100}\text{)},\\ 2^{100}& \equiv (-1{)}^{100}(\mathrm{mod}3)\\ & \equiv 1(\mathrm{mod}3).\end{array}$$

Now we need the unique $x$ with $0\le x<12$ satisfying $x\equiv 0(\mathrm{mod}4)$ and $x\equiv 1(\mathrm{mod}3)$; checking the candidates $0,4,8$, only $x=4$ works. Therefore, $2^{100}\mathrm{mod}12=4$. Notice that Euler was still useful on the coprime piece (as $\gcd (2,3)=1$); the trick is to quarantine the shared factor first.

Finding Inverses with Euler's Theorem

Euler's Theorem also hands us a formula for inverses. Since

$$a\cdot a^{\varphi (n)-1}=a^{\varphi (n)}\equiv 1(\mathrm{mod}n),$$

we immediately get

$$\boxed{\gcd (a,n)=1⟹a^{-1}\equiv a^{\varphi (n)-1}(\mathrm{mod}n).}$$

This is an alternative to the extended Euclidean algorithm from Bezouts Identity and the Extended Euclidean Algorithm; it is usually slower by hand, but it is a one-line formula, which makes it useful in proofs (and in RSA-style computations later).

Example. Use Euler's Theorem to find $7^{-1}$ in ${\mathbb{Z}}_{30}$.
We have $\gcd (7,30)=1$ and

$$\varphi (30)=\varphi (2)\varphi (3)\varphi (5)=1\cdot 2\cdot 4=8,$$

so $7^{-1}\equiv 7^7(\mathrm{mod}30)$. Computing by squaring,

$$\begin{array}{rl}{7}^2& =49\equiv 19(\mathrm{mod}30),\\ 7^4& \equiv 19^2(\mathrm{mod}30)\\ & \equiv 361(\mathrm{mod}30)\\ & \equiv 1(\mathrm{mod}30),\\ 7^7& =7^4\cdot 7^2\cdot 7\\ & \equiv 1\cdot 19\cdot 7(\mathrm{mod}30)\\ & \equiv 133(\mathrm{mod}30)\\ & \equiv 13(\mathrm{mod}30).\end{array}$$

Check: $7\cdot 13=91=3\cdot 30+1\equiv 1(\mathrm{mod}30)$. Therefore, $7^{-1}=13$ in ${\mathbb{Z}}_{30}$.

Reducing Exponents in General

Just as with primes, the real day-to-day use of Euler's Theorem is collapsing huge exponents.

Proof. By the division theorem, write $k=q\varphi (n)+r$ where $r=k\mathrm{mod}\varphi (n)$, so $0\le r<\varphi (n)$. Then

$$\begin{array}{rl}{a}^k& =a^{q\varphi (n)+r}\\ & ={\left(a^{\varphi (n)}\right)}^q\cdot a^r\\ & \equiv 1^q\cdot a^r(\mathrm{mod}n),\text{ (by Euler’s Theorem, as }\gcd (a,n)=1\text{)}\\ & \equiv a^r(\mathrm{mod}n).■\end{array}$$

So when $\gcd (a,n)=1$, bases live in ${\mathbb{Z}}_n$ but exponents live in ${\mathbb{Z}}_{\varphi (n)}$;

$$\boxed{\gcd (a,n)=1⟹a^k\equiv a^{k\mathrm{mod}\varphi (n)}(\mathrm{mod}n).}$$

Exponents are reduced modulo $\varphi (n)$, never modulo $n$ itself.

Example. Find $2^{3^{100}}\mathrm{mod}11$.
This is a tower of powers, so we work from the outside in. The outer modulus $11$ is prime with $\gcd (2,11)=1$, so the exponent $3^{100}$ only matters modulo $\varphi (11)=10$. That turns the problem into finding $3^{100}\mathrm{mod}10$; and since $\gcd (3,10)=1$ with $\varphi (10)=\varphi (2)\varphi (5)=4$, that exponent only matters modulo $4$;

$$\begin{array}{rl}100& \equiv 0(\mathrm{mod}4),\\ 3^{100}& \equiv 3^0(\mathrm{mod}10)\\ & \equiv 1(\mathrm{mod}10),\\ 2^{3^{100}}& \equiv 2^1(\mathrm{mod}11)\\ & \equiv 2(\mathrm{mod}11).\end{array}$$

Therefore, $2^{3^{100}}\mathrm{mod}11=2$. Notice how each layer of the tower drops down one level: powers mod $11$ are governed by $\varphi (11)=10$, and powers mod $10$ are governed by $\varphi (10)=4$.

Fast Modular Exponentiation

Reducing the exponent with Euler's Theorem is only half the job; the reduced exponent can still be uncomfortably large (anything up to $\varphi (n)-1$), and multiplying one factor at a time takes forever. The fix is repeated squaring: square the base over and over, reducing modulo $n$ at every step, to obtain

$$a^1,a^2,a^4,a^8,a^{16},\dots (\mathrm{mod}n),$$

and then multiply together the powers matching the binary expansion of the exponent. This needs roughly ${\log }_{2}k$ multiplications instead of $k$, and because we reduce mod $n$ after every squaring, the numbers involved never get big.

Example. Find the last two digits of $3^{1234}$.
The last two digits of a number are exactly its remainder mod $100$, so we want $3^{1234}\mathrm{mod}100$. First reduce the exponent using the totient function: $\gcd (3,100)=1$ and

$$\varphi (100)=\varphi (4)\varphi (25)=2\cdot 20=40,$$

and since $1234=30\cdot 40+34$, we have $3^{1234}\equiv 3^{34}(\mathrm{mod}100)$. Now $34=32+2$, so we build up by repeated squaring;

$$\begin{array}{rl}{3}^2& =9,\\ 3^4& =9^2=81,\\ 3^8& =81^2=6561\equiv 61(\mathrm{mod}100),\\ 3^{16}& \equiv 61^2(\mathrm{mod}100)\\ & \equiv 3721(\mathrm{mod}100)\\ & \equiv 21(\mathrm{mod}100),\\ 3^{32}& \equiv 21^2(\mathrm{mod}100)\\ & \equiv 441(\mathrm{mod}100)\\ & \equiv 41(\mathrm{mod}100),\\ 3^{34}& =3^{32}\cdot 3^2\\ & \equiv 41\cdot 9(\mathrm{mod}100)\\ & \equiv 369(\mathrm{mod}100)\\ & \equiv 69(\mathrm{mod}100).\end{array}$$

Therefore, the last two digits of $3^{1234}$ are $69$.

For any "huge power mod $n$" question, the routine is always the same: check $\gcd (a,n)$ first (if it is not $1$, split $n$ into coprime pieces and quarantine the shared factor); factorise $n$ to compute $\varphi (n)$; reduce the exponent modulo $\varphi (n)$ — or modulo $p-1$ when $n$ is prime; and finish off whatever exponent remains with repeated squaring, keeping an eye out for a handy $-1$ along the way.