Congruence with FLT

• May 6th 2010, 12:43 PM
SCRandom
Congruence with FLT
The congruence $\displaystyle 2^{52532} \equiv 1 \bmod{52633}$ is true. Can you conclude that $\displaystyle 52633$ is a prime number?

So would the answer be that since $\displaystyle 2^{52532} \equiv 1 \bmod{52633}$ is in the format for FLT then $\displaystyle 52633$ must be prime right?
• May 6th 2010, 02:26 PM
tonio
Quote:

Originally Posted by SCRandom
The congruence $\displaystyle 2^{52532} \equiv 1 \bmod{52633}$ is true. Can you conclude that $\displaystyle 52633$ is a prime number?

Of course not: why would anyone conclude such a thing?? Of course, it's pretty easy to check directly that $\displaystyle 7\mid 52633$ , but even without this

we couldn't conclude that: for example, $\displaystyle 2^4=\!\!\!\pmod{15}$...can we conclude 15 is prime? $\displaystyle 2^6=1\!\!\!\pmod 9$...is 9 a prime?

About what you wrote below: " ...is in the format of FLT..." do you mean Fermat's Little Theorem? What is in this format??

Tonio

So would the answer be that since $\displaystyle 2^{52532} \equiv 1 \bmod{52633}$ is in the format for FLT then $\displaystyle 52633$ must be prime right?

.
• May 6th 2010, 04:41 PM
chiph588@
Quote:

Originally Posted by SCRandom
The congruence $\displaystyle 2^{52532} \equiv 1 \bmod{52633}$ is true. Can you conclude that $\displaystyle 52633$ is a prime number?

So would the answer be that since $\displaystyle 2^{52532} \equiv 1 \bmod{52633}$ is in the format for FLT then $\displaystyle 52633$ must be prime right?

I think you meant to say $\displaystyle 2^{52632} \equiv 1 \bmod{52633}$, as $\displaystyle 2^{52532} \not\equiv 1 \bmod{52633}$.

This doesn't mean $\displaystyle 52633$ is prime. flt says if $\displaystyle p$ is prime and $\displaystyle (a,p)=1$, then $\displaystyle a^{p-1}\equiv 1\bmod{p}$. The converse however is not true.

Carmichael number - Wikipedia, the free encyclopedia