# Thread: Finding remainder in non-prime congruence

1. ## Finding remainder in non-prime congruence

Find $\displaystyle r \in Z$ such that $\displaystyle 0 \leq r \leq 4096$ and $\displaystyle 2^{4096} \equiv r \,(mod \,4097)$ Why does this prove that $\displaystyle 4097$ is not a prime? According to FLT r would be 1 if 4097 where a prime, but now it isn't, so, help appreciated.

2. Originally Posted by knarQ
According to FLT r would be 1 if 4097 where a prime
That’s the wrong statement of Fermat’s little theorem, According to FLT, $\displaystyle r=1$ if 2 and 4097 are relatively prime. They are, so $\displaystyle 2^{4096}\equiv1\,\bmod{4097}.$

However, this alone neither proves nor disproves that 4097 is not prime. For example:

1. Since $\displaystyle 2^2\equiv1\,\bmod3,\ 2^{4096}=(2^2)^{2048}\equiv1\,\bmod3$ and 3 is a prime.
2. Since $\displaystyle 2^4\equiv1\,\bmod{15},\ 2^{4096}=(2^4)^{1024}\equiv1\,\bmod15$ but 15 is not a prime.

Hence, if $\displaystyle 2^{4096}\equiv1\,\bmod n,$ nothing can be deduced about the primeness or otherwise of $\displaystyle n.$ You need more information on $\displaystyle n.$ The question you posted may be part of another question containing some other results about 4097.