# 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
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}