Talk:Wilson's theorem

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated Start-class, Mid-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
Start Class
Mid Importance
 Field: Number theory

Very old comments[edit]

The reference to John Wilson on this page is not to the correct John Wilson. See the MacTutor History of Mathematics archive.

Sorry, I meant making Gauss thm purty, not Euler. Revolver

In the applications section it states that calculating factorials is hard. if you go to factorial it states that you can calculate factorials O(N*(ln(N)*ln(ln(N)))^2). that doesn't sound hard, it's polynomial. This is of utmost importance because I believe I have found a quick factoring algorithm. Ozone 08:53, 28 December 2005 (UTC)

Get in line :) Almost everyone with any mathematical inclination has at some point thought that they have solved factoring.
Anyways, an efficient factoring algorithm needs to be polylogarithmic in 'n', because n is insanely large. A polynomial time algorithm is useless (and in fact trial division is a polynomial time algorithm). A common error. Arvindn 09:57, 28 December 2005 (UTC)
H'mmm thanks, I knew it wouldn't work. I'll state my method anyhow:
  • Get value
  • Square root
  • round down to nearest integer
  • get factorial
  • caclulate GCD(original value, factorial)
  • the result is one of the factors of the semiprime.
Well, the method works for semiprimes (except in the case that the value is the square of a prime number, when it returns the number rather than a nontrivial factor). It also can work for numbers other than semiprimes, but the factor it finds in that case is never prime. As an improvement you could test if numbers in this range divide the number rather than taking their product; this way you don't need nearly as much memory and can break out early if you find a small factor. Of course this is then trial division... CRGreathouse (t | c) 23:23, 28 July 2007 (UTC)

"just if"?[edit]

In mathematics, Wilson's Theorem states that p is a prime number just if
(p-1)!\ \equiv\ -1\ (\mbox{mod}\ p)
(see factorial and modular arithmetic for the notation). There is a converse result.

"Just if" could mean "only if". It could also mean "precisely if", i.e. "if and only if". Given this vagueness, what does the last sentence mean, about the "converse result". Michael Hardy 22:35, 7 April 2006 (UTC)

I changed that to 'iff.' He Who Is 19:41, 1 May 2006 (UTC)

And now I've deleted the part about the converse result, since that makes no sense when it says "if and only if". Michael Hardy 20:45, 1 May 2006 (UTC)

Ibn al-Haytham[edit]

It appears that al-Haytham discovered a version of the CRT rather than Wilson's theorem as such; also, if he did apply it to primes rather than congruences (do we have another source on this?), it would be described in modern terms as a conjecture, as he didn't have a proof. However I think that it's probably best to mention him and let the reader decide the significance rather than delete it. How do others feel?

CRGreathouse (t | c) 23:23, 28 July 2007 (UTC)

Are the proofs presented in the article circular?[edit]

Do they use results that in fact come from Wilson's theorem? Should a proof that does not use group theory be presented?--Jrm2007 (talk) 07:41, 18 July 2008 (UTC)

The proofs are not circular. For the first proof, the only non-trivial dependence is the fact that multiplication modulo p forms a group (i.e., the fact that inverses are present). This follows trivially from p being prime. Misof (talk) 22:13, 13 December 2009 (UTC)

A question about the ‘Converse‘ part[edit]

I think the equation

log n/log q ≤ n/q − 1 

does not hold for n = 2 q SettingMoon (talk) 20:21, 15 August 2008 (UTC)SettingMoon

converse section...[edit]

Isn't this actually the contrapositive of the forward direction? I.e., not the converse (can an "if and only if" statement have a converse, since that covers both directions?)

tacotank10 (talk) 07:12, 27 February 2009 (UTC)

Agreed. I edited the section to make it clear that this is not the converse of the statement (which does not make much sense for an implication). This is a proper generalization. I also provided a much simpler proof than the one with logarithms. Misof (talk) 22:08, 13 December 2009 (UTC)

A simple generalization - a flaw[edit]

The "simple generalisation" is misstated - since it is not in the form of a congruence, the "−1" should be replaced by "n − 1". If it is restated as congruence i.e.

\forall n\in\mathbb{N}:
(n-1)! \equiv 
-1 \pmod n & \gets n \text{ is prime}
2 \pmod n & \gets n=4
0 \pmod n & \text{otherwise}

or as I suggested as

\forall n\in\mathbb{N}:
(n-1)! ~\bmod~ n = 
n-1 & \gets n \text{ is prime}
2 & \gets n=4
0 & \text{otherwise}

it breaks down at n = 1 either way, as the top and bottom cases collapse into one. Quondum (talk) 20:17, 5 August 2011 (UTC)

I have now modified the article to match the first fork above, though the exclusion of n=1 is clumsily stated. Quondum (talk) 18:34, 11 August 2011 (UTC)

Finite abelian group generalization[edit]

The article currently says,

This further generalizes to the fact that in any finite abelian group, either the product of all elements is the identity, or there is precisely one element a of order 2. In the latter case, the product of all elements equals a.

While this is strictly true, as stated the possibility that there is precisely one element a of order 2 and that the product of all elements is still identity is not discounted. This actually cannot occur. That is, "or" has been used when "xor" was probably meant (and is in fact true). Applying the fundamental theorem of finite abelian groups and doing some mundane calculations, one finds that the group contains a unique element of order 2 if and only if the Sylow 2-subgroup is cyclic (of order > 1); if it is cyclic, the product of the group's elements is the unique order 2 element, and otherwise the product is the identity.

The statement is unsourced right now anyway, but perhaps a source can be found for this stronger version. I haven't edited the article since it's OR. (talk) 08:42, 19 March 2012 (UTC)

I would think this follows immediately from the fact that the order of the identity element is never 2. When I first read this I disambiguated to 'xor' on this basis. I think that 'xor' is also implied adequately by "either ... or". — Quondum 15:49, 19 March 2012 (UTC)
Oh yes, of course the 'xor' can be quickly deduced from the 'or' case (though even that is OR). The Sylow 2-subgroup information I mentioned is really the content of my refinement. I don't agree about "either ... or" implying 'xor'; usually "either ... or ... but not both" is used for 'xor'. (talk) 09:20, 20 March 2012 (UTC)
Perhaps you can simply reword it to make it clearer that the cases are exclusive – I doubt you'll get much objection unless you make it too verbose. If you have sources for any alternative arguments (and I'm not going to pretend that I'm familiar with Sylow p-subgroups) of merit in this context, you could add these as a footnote. — Quondum 12:30, 20 March 2012 (UTC)
"either ... or else"? AlexFekken (talk) 12:30, 21 March 2012 (UTC)
I've simply added "(but not both)" to the page. As for my refinement, unfortunately I couldn't even find the original statement in my algebra books. It's almost perfect for an exercise problem.... (talk) 15:14, 21 March 2012 (UTC)