Find x in the congruence using Fermat's Little Theorem

**Th3sandm4n** · March 24th 2009, 08:44 AM

It's supposed to be 2^(11), but don't know how to do it

$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

**SimonM** · March 24th 2009, 08:46 AM

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

**o_O** · March 24th 2009, 08:48 AM

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?

**Th3sandm4n** · March 24th 2009, 09:15 AM

I see it now

Thanks!

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

LinkBack

Thread Tools

Display

Find x in the congruence using Fermat's Little Theorem

Similar Math Help Forum Discussions

abstract algebra [primitive root mod n, euler theorem, fermat theorem]

How do you find the last digit of a number using Fermat's Little Theorem

Congruence Proof (Application of Fermat's Theorem I believe)

Congruence Fermat's little theorem help

Find remainder with congruence theorem

Search Tags