Fermat's Little Theorem

[BigNate]

Hello,

Without using a calculator, I have to evaluate 12^49 (mod 15). I believe I need to use Fermat's Little Theorem to solve, but I am struggling. Can someone please help. Here is how I think it starts:

12⁴⁹(mod 15)
12¹⁴ ≡ 1 (mod 15)
12⁴⁹ = 12^14*3+7= .......

This is where I get stuck. Also I'm not even sure if this is correct to this point. Fermat's Little Theorem is a real challenge for me. I appreciate any and all help. Thanks!

 

[ksdhart2]

Fermat's Little Theorem says:

If p is a prime and a is any integer not divisible by p, then a^{p − 1} − 1 is divisible by p.

This is equivalent to the following two statements:

$\displaystyle a^{p-1} \equiv 1 \: \: \text{(mod p)}$ and $\displaystyle a^p \equiv a \: \: \text{(mod p)}$

It looks like you've tried to apply this in the second line of your workings, but this is incorrect, because 15 is not a prime number. In actuality, $\displaystyle 12^{14} \equiv 9 \: \: \text{(mod 15)}$. Because the number you're "modding by" isn't prime, Fermat's Little Theorem probably won't help much here. But some of the principles can still apply. You've correctly identified a possible rewriting of 12⁴⁹, so let's work with that for now:

$\displaystyle 12^{49}=12^{14 \cdot 3 + 7}=(12^{14})^3 \cdot 12^7$

Using a calculator, I determined that $\displaystyle 12^{14} \equiv 9 \: \: \text{(mod 15)}$. But, the problem specifically says not to use a calculator. So, let's apply the exact same tactics as above to break it down further. $\displaystyle 12^{14}=12^{2 \cdot 7}=(12^2)^7$

12² = 144, and this is a small enough value that we can just do the division by hand and find that the remainder is 9. That tells us that $\displaystyle 12^{14} \equiv 9^7 \: \: \text{(mod 15)}$.

Iterating again will leave $\displaystyle 9^{7}=9^{2 \cdot 3 + 1}=(9^2)^3 * 9$. Doing the division by hand shows that $\displaystyle 9^2 = 81 \equiv 6 \: \: \text{(mod 15)}$. This tells us that $\displaystyle 9^{7} \equiv 6^3 \cdot 9 \: \: \text{(mod 15)}$.

As it turns out, $\displaystyle 6^3 = 216 \equiv 6 \: \: \text{(mod 15)}$. This tells us that $\displaystyle 9^{7} \equiv 6 \cdot 9 = 54 \equiv 9 \: \: \text{(mod 15)}$.

This all leaves us with the conclusion that $\displaystyle 12^{49} \equiv 9^3 \cdot 12^7 \equiv 9^2 \cdot 9 \cdot (12^2)^3 \cdot 12 \: \: \text{(mod 15)}$. Try continuing from here and see what you get.

 

[BigNate]

Fermat's Little Theorem says:

12² = 144, and this is a small enough value that we can just do the division by hand and find that the remainder is 9. That tells us that $\displaystyle 12^{14} \equiv 9^7 \: \: \text{(mod 15)}$.
.

Thank you so much for your help and time! I'm trying to continue solving it as you recommended, but have hit a roadblock midway through your explanation. Can you please explain how we determine the remainder is 9? And then, how do we know 9 has an exponent of 7?

Thanks again!

 

[ksdhart2]

Thank you so much for your help and time! I'm trying to continue solving it as you recommended, but have hit a roadblock midway through your explanation. Can you please explain how we determine the remainder is 9? And then, how do we know 9 has an exponent of 7?

Thanks again!

Oh, sure. I found that the remainder is 9 simply by doing the division manually. To find 144 mod 15, I really needed to find the remainder of 144 / 15 = 9.6. I then subtracted. 144 - (15 * 9) = 144 - 135 = 9. Therefore, I know that $\displaystyle 12^2 = 144 \equiv 9 \: \: \text{(mod 15)}$.

From there, it's a matter of making a substitution in the original equation. Because I know that 144 and 9 are congruent under modulo 15, I can freely replace any occurrence of 144 anywhere with 9, and everything will work out. Doing that leaves $\displaystyle 12^{14} = (12^2)^7 = 144^7 \equiv 9^7 \:\: \text{(mod 15)}$

You might also find it helpful to look at Theorems 3.1 and 3.2 on this page from the University of Connecticut, where they provide a proof of why such substitutions are valid. In particular, Example 3.3 may be the most useful because it uses "real" numbers rather than abstract formulae.