4
$\begingroup$

Prove that $717$ is not prime using Wilson's Theorem.

Assume $717$ is prime then:

$$716! \equiv -1 \pmod{717}$$

$$ 716 \cdot 715! \equiv -1 \mod{717}$$

$$ 716 \equiv -1 \pmod{717}$$

$$715! = 715 \cdot 714! \equiv -2 \cdot 714 \pmod{717}$$

Still, I dont feel I have enough to get a contradiction? Help?

$\endgroup$
  • 1
    $\begingroup$ I don't see how you can use Wilson's theorem to prove that a number is not prime without disguising computation of a factorization of the number. In this case you are trying to disguise $717=3\cdot239$, so try taking the factorial out to the first $3$ terms. $\endgroup$ – Mario Carneiro Feb 17 '15 at 13:59
  • 6
    $\begingroup$ This is a silly question. It's like "Use Fermat's Last Theorem to prove that $8 + 27 \ne 64$." $\endgroup$ – TonyK Feb 17 '15 at 14:16
  • $\begingroup$ See also here for using Wilson's theorem. $\endgroup$ – Dietrich Burde Feb 17 '15 at 15:57
  • $\begingroup$ @TonyK, explain more please, I am listening $\endgroup$ – Lebes Feb 17 '15 at 17:25
  • 1
    $\begingroup$ Errm, OK: "Assuming Wilson's Theorem, $717$ is divisible by $3$ because $7+1+7=15$." $\endgroup$ – TonyK Feb 17 '15 at 23:59
3
$\begingroup$

$$717\mid 9760496755029770610869447395675086113984057343132061757382342151925641\\ 9275455971314773495702907775026291563950827586900336378458159342677078\\ 5022184766044932222514928686783680807925809243433542915857945929421783\\ 5307048238908992084546959184908182359502237044234483347263334283471612\\ 9708285958225728166193874164093882286585568557635299063799347869228097\\ 1568229218443261304970052163939166467765233582512306591911191981348670\\ 2663568585245019566224949333279099079181925728725083924950348255600895\\ 1141127891459412702371610057016753341274225675436079833167510747019252\\ 9657366321645491563408318838830762107005614360976800500448336833598641\\ 4008806808483195324663092006426690690945289375105480649552172718227627\\ 7258677664195676324565189315249978730729410766498521756206976344345284\\ 3191499031516540874936871231902196461915733570748092868894565528541313\\ 4514035620474766158047574572166266828269813314839352735145285551657374\\ 6907745012097414926206463183535993709920169296374060634672272749951772\\ 9215399481349790716729648575994890699775701868922688637771964484376413\\ 6438369470924871843891222836721683045768631532680329504510911992289807\\ 6604194356028532086828980739618889238592447301455397285599714380092158\\ 9887054956250516301149224895438755151046464412970706490243112044782156\\ 0127148485917013746072079690583286912734936955963268641468501879578477\\ 3606007555355494365933928921763585644829098668458472793277802984658672\\ 6130942087714441899532667092327224830663251094767972789121512144963565\\ 2412240681915683642064079940398108745541151191150024389318502067558482\\ 2373352456553758720000000000000000000000000000000000000000000000000000\\ 0000000000000000000000000000000000000000000000000000000000000000000000\\ 0000000000000000000000000000000000000000000000000000000.$$

Thus...

(This probably isn't what your teacher meant, though.)


Here's a slightly less trivial/tongue-in-cheek interpretation of the question. Suppose we take Wilson's theorem as the definition of a prime, which is to say

Define a natural number $n$ to be prime if $(n-1)!\equiv-1\pmod n$, and composite otherwise.

Now we actually have something to prove. Since $(717-1)!$ is the product of the numbers from $1$ to $716$, $3$ and $239$ show up in the list. Thus $3\cdot 239=717\mid(717-1)!$, so $(717-1)!\equiv 0\pmod{717}$, and thus by our definition $717$ is composite.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Using Wilson theorem, not computer algebra systme. $\endgroup$ – user207868 Feb 17 '15 at 14:07
  • 1
    $\begingroup$ @Leon If you take Wilson's theorem at face value, this is exactly what it suggests you should do (except possibly for simplifying the result in intermediate computations so that the numbers don't get to big). There is a good reason why no one uses Wilson's theorem to test for primality. $\endgroup$ – Mario Carneiro Feb 17 '15 at 14:10
  • 1
    $\begingroup$ This answer is excellent, in that it shows up the flaw in the OP's question. $\endgroup$ – TonyK Feb 17 '15 at 14:13
0
$\begingroup$

Let $717$ be prime

then $716!\equiv -1 mod 717$

we have$ 714 \equiv 0 mod 3$

therefore $ 714! \equiv 0 mod 3$

$714!(715)\equiv 715 mod 3 \equiv 1 mod 3$

Similarly$ 716! \equiv 2 mod 3 \equiv -1 mod 3$

therefore $716!+1=3k$

also we have $716!+1=717k'$

therefore $3k=717k'$

which would imply?

can u do it now?

| cite | improve this answer | |
$\endgroup$
  • 5
    $\begingroup$ You use the fact that $714 \equiv 0$ mod $3$. This is exactly as easy to prove as the fact that $717 \equiv 0$ mod $3$. But then you don't need Wilson's theorem after all! I think the question is flawed. $\endgroup$ – TonyK Feb 17 '15 at 14:12
  • $\begingroup$ yeah i know but just for the sake of argument this does seem to be a way, to arrive at the answer, don't u agree? :) $\endgroup$ – Shobhit Feb 17 '15 at 14:14

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.