# Thread: Find x in the congruence using Fermat's Little Theorem

1. ## 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
$\displaystyle 2^11 \equiv xmod3$ such that $\displaystyle 0<=x<=2$
Find x using Fermat's Little Theorem.

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

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

Thanks

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

So $\displaystyle 2^{11} = 2^{10+1} = (2^2)^5 \times 2^1 = 1^5 \times 2 = 2 \pmod{3}$

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

So: $\displaystyle \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):$\displaystyle \left(2^2\right)^{{\color{red}5}} \equiv 1^{{\color{red}5}} \ (\text{mod } 3)$

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

Can you finish off?

4. I see it now
Thanks!