1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – tc1729 Oct 17 '13 at 5:20
  • $\begingroup$ Thank you, How use Farmat's Little Theorem? $\endgroup$ – china math Oct 17 '13 at 5:21
1
$\begingroup$

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}$$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.