# How to prove a number is not a prime number (without a computer)

Show that $$5994937829$$ is not prime number

How can I use math methods to prove it, and I know that this be proven using computer. But I can use only math methods to solve it.

• If it is prime, Fermat's Little Theorem must hold, so perhaps you can use that to derive a contradiction. EDIT: See the answer by T. Bongers. – tc1729 Oct 17 '13 at 5:20
• Thank you, How use Farmat's Little Theorem? – china math Oct 17 '13 at 5:21

If $p = 5994937829$ were prime, then Fermat's little theorem implies that

$$a^p \equiv a \pmod{p}$$

for all $a$. But this does not hold, since

$$2^p \equiv 1030766071 \pmod{p}$$

• why $2^p\equiv 1030766071$? – china math Oct 17 '13 at 5:25
• @chinamath This can be easily computed by successive squaring, for example - I linked to WA, and it should show up now. – user61527 Oct 17 '13 at 5:26
• No,I hope don't use any computer to prove this – china math Oct 17 '13 at 5:27
• @chinamath Using successive squaring, the residue $2^p$ can be computed by hand in a few minutes. – user61527 Oct 17 '13 at 5:27
• this maybe let $A=5994937829, B=10^{180004}+ 248797842×10^{89998} + 1$,then we easy find $A=77377\times 77477$ – china math Oct 17 '13 at 5:29