Use Fermat's Theorem to prove 10001 is composite

Question

I need to use Fermat's Theorem to prove that 10001 is not prime. I understand that I just need to find a counterexample where $a^{10000}$ mod 10001 = 1 mod 10001 does not hold true, but this seems kind of difficult with such large numbers. Any ideas?

Answer 1

Fermat pseudoprimes to any given base are really very rare, so you might as well just launch in with $2$ and hope for the best. This is a bit tedious but perfectly doable by repeated squaring: $$10000 = 2^{13}+2^{10}+2^9+2^8+2^4$$ so you just need to keep on squaring $2$ (modulo $10001$) thirteen times.

Answer 2

This is a bit of a cheat, but another theorem of Fermat's says that $10001$ cannot be prime because it has two different representations as a sum of two squares:

$$10001=100^2+1^2=65^2+76^2$$

The "cheat" here is that, while $100^2+1^2$ is easy enough to spot, finding the other sum of two squares involved almost as much work as searching for the factors themselves would have taken.

Answer 3

Another method, also based on Fermat's little theorem, is the following.

First notice $$10001=10^4+1=\frac{10^8-1}{10^4-1}$$

So finding a prime factor of $10^8-1$ that is not also a factor of $10^4-1$ is enough. The prime factors of $10^4-1$ are easy to determine even by hand calculation : $3,11,101$ Another prime dividing $10^8-1$ must be of the form $8k+1$

This is because the smallest positive integer $k$ with $\ 10^k\equiv 1\mod q\ $ (the order of $10$ modulo $q$) is $8$ and Fermat's little theorem gives $\ 10^{q-1}\equiv 1\mod q\ $ which shows $8\mid q-1$. So, we only need to verify the primes of the form $8k+1$. The first three are $17,41,73$

$73$ turns out to divide $10001$ and proves that $10001$ is composite.

For a bit larger numbers (but not too large) of a special form this method should be superior to the direct calculation of the power.

Answer 4

For 5-digit size of numbers you can still use Fermat's factorisation method and a difference of two squares. If your number $10001$ has got minimum of two factors, they won't be in such a great distance between each other. In this case it happened that only $5$ squares beginning from $100$ needed to be examined:

$105^2-32^2=11025-1024=10001$

So your solution is that $10001$ is a composite number with two prime factors:

$(105+32)\cdot(105-32)=137 \cdot 73=10001$

For very large numbers there is another method, however to long to describe in here, which results in:

$10001= 3\cdot3333+2=\sum (5403+3333+1263)+2$

In this 3-term arithmetic progression the difference between terms can be expressed:

$d=2\cdot x\cdot y=2\cdot1035=2\cdot23\cdot45$

... where $x$ and $y$ are variables of two prime numbers. Plugin them along with a leading coefficient number $3$ results in:

$(3\cdot23+4)(3\cdot45+2)=73\cdot137=10001$