Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
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
1  
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
1  
@Ted Really, you need to look at equivalence classes rather than elements of $\mathbb N$. –  Alex Becker Feb 26 '12 at 19:30
1  
See also the answers to this question. –  Bill Dubuque Feb 26 '12 at 20:10
1  
@BillDubuque Thanks for the link, that's what I wanted. –  dharm0us Feb 27 '12 at 18:30

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.