Use Fermat's Theorem to prove 10001 is composite 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?
 A: 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.
A: 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.
A: 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.
A: 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$
