Ykhjuy

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?

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.

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.