0
$\begingroup$

Just search for the string Reducing Exponents on this page.
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?

Can some please explain?

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

  • 0
    @Ted Thanks a lot.2012-02-27

2 Answers 2

2

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

1

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