Talk:Wilson's theorem

Very old comments

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"?

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

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?

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

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...

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

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 {\begin{cases}-1{\pmod {n}}&\gets n{\text{ is prime}}\\2{\pmod {n}}&\gets n=4\\0{\pmod {n}}&{\text{otherwise}}\end{cases}}$

or as I suggested as

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

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

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. 208.107.152.253 (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'. 208.107.152.253 (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.... 208.107.152.253 (talk) 15:14, 21 March 2012 (UTC)

Obscure notation

The introductory paragraph is needlessly obscure. In particular this

$(n-1)!\ \equiv \ -1{\pmod {n}}$

means nothing to me. If I understand the text correctly it would be better written as

If n is prime then ((x-1)!) mod n = n - 1

50.43.39.82 (talk) 17:28, 7 February 2018 (UTC)

This "obscure" notation is the standard notation for this material and would be expected to be known to a majority of the readers of this page. For those unfamiliar with it, the sentence that follows it describes the relation without the notation. In a subject such as math, you can not expect that all articles will start with no assumptions about the readership. If we wrote all math articles without notational devices we would start getting complaints from the other side, claiming that things could be written much more simply by using ... . Compromises have to be made when writing such articles, and I think that this one does a reasonable job with such a compromise.

Also, I hope that you intended to write:

If n is prime then (n − 1)! = xn − 1, for some integer x.

--Bill Cherowitzo (talk) 18:37, 7 February 2018 (UTC)

Improved my improved statement. I was in a hurry. Since you like the fancy notation, could you at least provide a link to a page that explains it?50.43.39.82 (talk) 18:45, 7 February 2018 (UTC)

 Done --Bill Cherowitzo (talk) 18:57, 7 February 2018 (UTC)

Yes. It's inscrutable jargon.

I'm comparatively well educated in math, but I had a problem with the "fancy" notation too. It's jargon no matter how "standard" it is. Jargon is specifically disfavored by WP policy and is unencyclopedic. There's no such thing as a "technical article" in WP, WP is not a repository for math papers. Rather, it's our duty to be clear to lay readers. Being fancy and pedantic can never be justified as "compromise". Any math notation beyond maybe middle school or high school should at least link to something that explains what it means. For example, "(m mod n)" is explained, but "(mod n)" by itself is not. And, what's that "triple equals" sign, eh? I remember something like that as "is defined as", but that makes no sense here. 98.217.10.176 (talk) 16:28, 19 August 2019 (UTC)

The relevant link is to modular arithmetic; it appears earlier in the same sentence as the equation does, and explicitly indicates that it's the link you should click on to understand the notation. Moreover, the preceding sentence already explains the statement in a non-jargon, non-notation way. There are problems with accessibility of some mathematics articles on Wikipedia, but the first two sentences of this article are not a good example of that problem. (Possibly it is also worth noting that this status quo resulted from the earlier discussion 18 months ago.) --JBL (talk) 16:32, 19 August 2019 (UTC)

Whoops. I failed to click through that modular arithmetic link. I had only relied on the new-fangled popup that appears when you hover over a link. My bad there. Also, it looks like the term "technical article" is used, though not in the sense of separating them from accessibility by lay readers: https://en.wikipedia.org/wiki/Wikipedia:Make_technical_articles_understandable . The dates of "status quo" were obvious by the date stamps on the previous discussions. 98.217.10.176 (talk) 16:54, 19 August 2019 (UTC)

Adding more generalizations

Regarding the generalization of Wilson's theorem stated in the Wilson prime article, it seems to be quite important to mention it on this page too. What do you think ? Lancelot Chardonnet (talk) 14:31, 26 December 2020 (UTC)Lancelot

Wiki Education assignment: Number Theory I

This article was the subject of a Wiki Education Foundation-supported course assignment, between 22 August 2022 and 12 December 2022. Further details are available on the course page. Student editor(s): HUco2024 (article contribs).

— Assignment last updated by HUco2024 (talk) 16:42, 12 December 2022 (UTC)

cryptic reference

note 7. "Gauss, DA, art. 78" is ungoogleable and should contain a link 128.237.82.1 (talk) 05:41, 8 March 2024 (UTC)

It's to one of the two translations of Disquisitiones Arithmeticae found in the references section of this article. --JBL (talk) 17:47, 8 March 2024 (UTC)

variant

Hello people. I have noticed also that $(p-2)!\equiv _{p}1$ for prime p, and not for composite p. Is this true generally and is it worth discussing? 63.40.186.52 (talk) 22:08, 13 April 2024 (UTC)

This is an essentially trivial consequence of Wilson's theorem (becauce p - 1 = -1 is a unit modulo p) and is mentioned in passing in the third proof. To discuss it at greater length, we should have sources to base the discussion on. --JBL (talk) 21:18, 15 April 2024 (UTC)

Hello. I only brought it up because its marginally simpler. You have literally one fewer multiplication on the left hand side. On the right hand side you have a simple 1, not a p-1. There is no -1 in modulus, so even the necessary subtraction is avoided. I know its trivial and insignificant, but its an observation nonetheless. It might actually be a useful fact to someone implementing Wilson at the very edge of integer sizes that their hardware can handle. 63.40.186.52 (talk) 01:18, 17 April 2024 (UTC)

Lagrange's theorem

1) Lagrange's theorem, which consists concerns all polynomials, is not needed (contrary to what is stated in the article). Yes, the shortcut uses the same proof strategy, but not the generality of Lagrange's theorem. We only care about $X^{2}-1$, which can be dealt with in a single sentence, and if Lagrange's theorem was to not hold for some other polynomials, the shortcut would still work.

Besides, a claim like "some theorem is needed" is not a mathematical claim (prove it, and good luck), Not to mention the fact that no source is provided.

2) One cannot censor the fact that proving Lagrange's theorem is not required. My final edit only consists of that mention below the proof, there is no reason to not make the proof accessible to less advanced students (and relying on less results). Trashyyy (talk) 16:12, 4 July 2024 (UTC)

Perhaps it would make sense to say very briefly that only a special case of Lagrange's theorem is needed? Russ Woodroofe (talk) 18:42, 4 July 2024 (UTC)

I think this is what I've done. Trashyyy (talk) 18:51, 4 July 2024 (UTC)

Hi Trashyyy, thanks for opening a discussion here, and welcome to Wikipedia. Here are a few independent thoughts:

• The sentence you keep changing doesn't say that every possible proof of Wilson's theorem uses Lagrange's theorem, it says that all the proofs in the Wikipedia article use it. So the parts of your comments about the necessity of use seem beside the point.
• I agree with you that Lagrange's theorem is not actually needed in full generality in the first proof, only in its application to the particular case $X^{2}-1$. I also agree with you that it is possible in this case to rely on other facts (like Euclid's lemma). I am open in principle to making this change, but I'm not sure I understand why this substitution is an improvement. You allude to it briefly in your point (2); perhaps you could say a bit more about why you think it would be better? (I would be more convinced if this could circumvent the mention of finite fields entirely in this proof, but maybe that is asking too much.) I found your rewritten version of the proof to be very unclear, but if we agree to swap reliance on Lagrange for reliance on Euclid, I would be happy to workshop it with you.
• There is another issue with the introductory paragraph of the section, which is that it doesn't appear to apply to the third proof (using Sylow's theorems) at all. Quite possibly this paragraph should be scrapped in favor of something totally different, that actually describes all three proofs.
• There is a separate issue that none of these proofs seems to be sourced at all. It would be wonderful if, instead of relying entirely on arguments among ourselves, we could rely on some references to quality textbooks or similar. If you had any in mind, that would be lovely.

Thanks again for beginning the discussion here. --JBL (talk) 20:09, 4 July 2024 (UTC)

I was thinking along the lines perhaps of adding a parenthetical note after the introduction of Lagrange's theorem "(although a special case with an easier proof suffices)". The text feels a little overloaded already. An alternative would be to remove the gloss on Lagrange's theorem, and replace with e.g. "Lagrange's theorem, or at least the n=2 case thereof, is needed for all the proofs." Of course, Wikipedia is WP:NOTTEXTBOOK. Russ Woodroofe (talk) 20:50, 4 July 2024 (UTC)

Regarding the claim that Wikipedia is not textbook, the page you referred too would actually lead us to move the proofs to the Wikiversity, as done here (in French sorry, see the source superscript 5).

We could then freely consider the two levels of proof (see one of my replies to even circumvent the mentioning of fields). Trashyyy (talk) 21:46, 4 July 2024 (UTC)

If you create the appropriate page in the Wikiversity (which I don't know how to do), then I can move/write the proofs of the theorem to the Wikiversity. Trashyyy (talk) 21:48, 4 July 2024 (UTC)

• If what you mean is "used" instead of "needed" (which, otherwise is a vague statement that needs to be proved), so let's write "use" (what I originally did in my edit).

• It is an improvement for a reader that knows Euclide's lemma (one of the first theorems in arithmetics) but not Lagrange's theorem, in which case a single sentence avoids diving into the proof of a second theorem (Lagrange's).

The idea of Lagrange's theorem may be what lies behind, and is worth mentioning, but I think it is also worth mentioning that we can go faster in this particular case (what we usually do in mathematics).

So yes, a parenthetical note can suffice, without changing the initial proof, but this is what I've already done. So stop censoring that kind of information (JBL) and acting as if it was an idea resulting from this discussion (Russ Woodroofe). Trashyyy (talk) 20:59, 4 July 2024 (UTC)

I think that the first paragraph is a bit vacuous anyway. "We use the fact that $\mathbb {Z} /p\mathbb {Z}$ is a field" at this level of arithmetics (in particular when we use Lagrange's or the Sylow theorems) is not the most relevant claim I've read, I mean this is a basics of modern arithmetics.

Adding to the fact that Lagrange's theorem is not even used in all the proofs, I think we could just delete the paragraph.

The link towards the page "Prime fields" could however be kept and discretely included in the other proofs when it is used. Trashyyy (talk) 21:06, 4 July 2024 (UTC)

I do not see the link between using that $\mathbb {Z} /p\mathbb {Z}$ is a field and the use of Lagrange's theorem by the way. But I can still solve that issue for you if you want: the fact that $\mathbb {Z} /p\mathbb {Z}$ is a field is basically Bézout's identity. Without going as far as advocating the field structure, we can just consider the unicity in Bézout's identity $au+pv=1$ (which holds with the condition $1\leq u<p$ and can be proved without much efforts), which allows to group the factor properly. Trashyyy (talk) 21:33, 4 July 2024 (UTC)

If this argument can justify in your eyes mentioning the $n=2$ shortcut, I write this as another elementary proof (which, really uses elementary tools). Trashyyy (talk) 21:36, 4 July 2024 (UTC)

• factors

Trashyyy (talk) 21:52, 4 July 2024 (UTC)

What is there is a little more expansive than the style I would prefer, but I think it's broadly acceptable (and anyway, that is a different issue). Looking at this again, I would suggest adding at in the Elementary Proof, after "This proves Wilson's theorem," the text "Notice that this proof uses only the easy special case where n=2 in Lagrange's theorem." As JBL has told you, there are several style and other problems with the edits you were pushing. Writing on Wikipedia can be a surprisingly technical enterprise... No one is trying to censor you, and I think that everyone is acting in good faith. Russ Woodroofe (talk) 23:49, 4 July 2024 (UTC)

I adress all the issues you mention and you keep deleting the most simple proof of the whole page.

• you've asked for this second proof,
• you've asked for a mention as a special case / re-formulation: this is done,
• you've asked too much by circumventing the mention of fields: this is done,
• you've criticized the style: this is fixed.

Moreover, as discussed above, the paragraph must be fixed too. Which I've done and you keep deleting.

Tell me why your (constantly changing and non-justified) opinion would prevail over mine (this is a real question). Trashyyy (talk) 15:27, 5 July 2024 (UTC)

Otherwise, let's move this proof to the Wikiversity as I've proposed earlier. Trashyyy (talk) 15:35, 5 July 2024 (UTC)