# Thread: Finding remainder in non-prime congruence

1. ## Finding remainder in non-prime congruence

Find $r \in Z$ such that $0 \leq r \leq 4096$ and $2^{4096} \equiv r \,(mod \,4097)$ Why does this prove that $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, $r=1$ if 2 and 4097 are relatively prime. They are, so $2^{4096}\equiv1\,\bmod{4097}.$

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

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

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