Krdytkyu

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?

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^kequiv 1mod q $ (the order of $10$ modulo $q$) is $8$ and Fermat's little theorem gives $ 10^{q-1}equiv 1mod q $ which shows $8mid 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.

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.

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.

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= 3cdot3333+2=sum (5403+3333+1263)+2$

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

$d=2cdot xcdot y=2cdot1035=2cdot23cdot45$

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

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