Talk:Wilson's theorem

From Wikipedia, the free encyclopedia

WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: Start Class Mid Priority  Field: Number theory
Please update this rating as the article progresses, or if the rating is inaccurate. Please also add comments to suggest improvements to the article.


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

Apparently, someone who didn't understand the second proof thought it was incorrect. I'll reinstate it. Revolver 06:02, 23 May 2005 (UTC)

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)

[edit] "just if"?

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)

[edit] Ibn al-Haytham

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)