Find x in the congruence using Fermat's Little Theorem

Printable View

Mar 24th 2009, 08:44 AM
Th3sandm4n

Find x in the congruence using Fermat's Little Theorem

It's supposed to be 2^(11), but don't know how to do it(Speechless)
$2^11 \equiv xmod3$ such that $0<=x<=2$
Find x using Fermat's Little Theorem.

Here is what I have done:
Since 3 is prime, it follows that $(2^11)^2 \equiv 1mod3$ by FLT and since $(2^11,3)=1$ .
So, multiply both sides by $2^11$ we get
$(2^11)^2 \equiv 2^11 * xmod3$
$1 \equiv 2^11 * xmod3$

It is here I'm not sure what to do since not sure how to get something $0<=x<=2$ , or how to isolate the x really.

Thanks
Mar 24th 2009, 08:46 AM
SimonM

$2^{3-1} = 2^2 = 1 \pmod{3}$ by FLT

So $2^{11} = 2^{10+1} = (2^2)^5 \times 2^1 = 1^5 \times 2 = 2 \pmod{3}$
Mar 24th 2009, 08:48 AM
o_O

FLT: If $\gcd (a,p) = 1$ , then $a^{p-1} \equiv 1 \ (\text{mod } p)$

So: $\gcd (2,3) = 1 \ \Rightarrow \ 2^{2} \equiv 1 \ (\text{mod } 3)$

Raise both sides to the power of 5 (to get it as close to 11 as possible): $\left(2^2\right)^{{\color{red}5}} \equiv 1^{{\color{red}5}} \ (\text{mod } 3)$

So we have: $2^{10} \equiv 1 \ (\text{mod } 3)$

Can you finish off?
Mar 24th 2009, 09:15 AM
Th3sandm4n

I see it now :)
Thanks!

All times are GMT -8. The time now is 02:07 PM.

Copyright © 2005-2016 Math Help Forum. All rights reserved.