# Fermat's Little Theorem - Reducing Exponents

In the example it says $7^{147} = ((7^{10})^{14}) \cdot (7^7)$
And since $(7^{10}) \mod 11 = 1$,
$((7^{10})^{14})\cdot(7^7) \mod 11 = (7^7) \mod 11$

How?

Because $(a \cdot b) \mod N \neq (a \mod N) \cdot(b \mod N)$ then how does the
above result occur?

-
You need to reduce mod N all the way. (a*b) mod N = ((a mod N) * (b mod N)) mod N. –  Ted Feb 26 '12 at 19:27
Also I really wish "mod" was never ever ever used to denote a function from $\mathbb N$ to $\mathbb N$. –  Alex Becker Feb 26 '12 at 19:30
@Ted Really, you need to look at equivalence classes rather than elements of $\mathbb N$. –  Alex Becker Feb 26 '12 at 19:30
@BillDubuque Thanks for the link, that's what I wanted. –  dharm0us Feb 27 '12 at 18:30

Here $7$ and $11$ are relatively prime, and also both $a$ and $b$ are powers of $7$.

Fermats little theorem says that if $p$ is a prime number, then for any integer $a$, $a$ and $p − a$ will be evenly divisible by $p$. This can be expressed in the notation of modular arithmetic as follows:

$$a^p \hspace{4pt}\equiv \hspace{4pt} a (mod \hspace{4pt} p )$$ OR

$$a^{(p-1)} \hspace{4pt}\equiv \hspace{4pt} 1 (mod \hspace{4pt} p )$$

Applying that to $a=7$ and $p=11$, to get $7^{10} \hspace{4pt} \equiv \hspace{4pt} 1 (mod \hspace{4pt} 11 )$

Another way to look at $7^{147}$ is by applying $7^{10} \hspace{5pt} 14$ times, one would get $7^{140}$ as $1 (mod \hspace{4pt} 11 )$. What is remaining now is $7^7$ and therefore

$$7^{147} \equiv 7^7 (mod \hspace{4pt} 11 )$$

An even better way to understand this is

$$7^{147}-7^7 = 7^7(7^{140}-1) \equiv 7^7 (mod \hspace{4pt}11)$$

$$\begin{matrix} 7^2 & \equiv & 5 (mod \hspace{4pt}11)\cr 7^3 & \equiv & 2 (mod \hspace{4pt}11)\cr 7^4 & \equiv & 3 (mod \hspace{4pt}11)\cr 7^5 & \equiv & 10 (mod \hspace{4pt}11)\cr 7^6 & \equiv & 4 (mod \hspace{4pt}11)\cr 7^7 & \equiv & 6 (mod \hspace{4pt}11)\cr 7^8 & \equiv & 9 (mod \hspace{4pt}11)\cr 7^9 & \equiv & 8 (mod \hspace{4pt}11)\cr 7^{10} & \equiv & 1 (mod \hspace{4pt}11)\cr 7^{11}& \equiv & 7 (mod \hspace{4pt}11)\cr 7^{12}& \equiv & 7^{2} (mod \hspace{4pt}11)\cr \end{matrix}$$ and if you keep going this way, it cycles back to $7^{147} \equiv 7^{7} \equiv 6 (mod \hspace{4pt} 11)$

-

$$7^{10}\equiv1(\mod 11)$$

So,

$$(7^{10})^{14}\equiv1^{14}(\mod 11)$$

Which is:

$$(7^{10})^{14}\equiv1(\mod 11)$$

Multiplying by $7^7$, we get:

$$(7^{10})^{14}(7^7)\equiv1\cdot 7^7(\mod 11)$$

or:

$$(7^{10})^{14}(7^7)\equiv 7^7(\mod 11)$$

-