Talk:Proofs of Fermat's little theorem

[Untitled]

In the first proof, we can allow a to be relatively prime to p, and we should, since that's the statement of the theorem. Furthermore, the step where we "divide out" (p-1)! has to justified. Normally, you cannot just divide if you work in modular arithmetic; here you can, because p and (p-1)! are coprime, but that has to be justified similar to the proof of the Lemma. 141.140.6.48 04:33 Oct 1, 2002 (UTC)

The first proof should be adapted so that it proves the same form of the theorem as the other proofs, the one that's also given on Fermat's little theorem. There is no need to restrict a to be between 1 and p-1. AxelBoldt 18:59 Oct 6, 2002 (UTC)

I am little confused about the second proof by induction. I have no backgorund in number theory there for I may be asking a wrong question. I would appreciate if anybody cares to explain to me. In the second proof it seems to me that the requirement of a,p being co-prime is not necessary and we can also prove it for cases for a,p not being co prime. Where am I making the mistake? -souvik

The second proof proves the first form of the theorem (a^p = a (mod p), which holds whether or not p and a are co-prime. The other proofs prove a^p-1 = 1 (mod p). Proving the first for all a and proving the second for a and p co-prime is equivalent, as the first part of the page says. Andre Engels 14:35 3 Jun 2003 (UTC)

big rewrite

This page is being rewritten at Proofs of Fermat's little theorem/Rewrite. Dmharvey Talk 4 July 2005 00:00 (UTC)

hi there guardian of light

i just noticed you are doing some edits to Proofs of Fermat's little theorem. Please join me at Proofs of Fermat's little theorem/Rewrite. I have been working on upgrading this page substantially. I had just started rewriting the proof that you appear to have been working on today (but it's in a real draft state at the moment and horribly incomplete). I have already done substantial work on the "combinatorial" "bracelets" proof. Let us continue this discussion at the relevant talk page. In particular, I think the proof that you were working on needs to be addressed at a lower-level audience, using far less notation, since it is certainly a result that could be made more accessible. Dmharvey Talk 2 July 2005 15:31 (UTC)

I agree that it is important to work collectively on this, but the notation is important. I think if we put up a word explanation after each step and the appropriate links to the meanings of the notation then it will be overall best.

Agree notation is important. (See KSmrq's edits concerning the unicode congruence symbol, IMO they're a real improvement on the previous inline TeX.)

However, we have to remember who our audience is for this article: mainly introductory number theory students, like someone taking a course say in a second or third year undergraduate program. It should be aimed there or lower. Therefore, I don't think it's good to have $\exists$ symbols floating around, and it's important to keep the mathematical vernacular to a minimum. That was my main aim in this rewrite. The only real change in content was replacing the fundamental theorem of arithmetic by Euclid's lemma, I can see there's potentially a debate there. Dmharvey Talk 5 July 2005 11:43 (UTC)

Reverting

A number of edits were made to replace wiki markup with TeX, for the sole purpose (apparently) of replacing an equal sign ("=") with a congruence sign ("≡"). This is not necessary, since we can directly insert the Unicode character. Therefore I have backed out those changes, inserted the Unicode, and made a few stylistic edits elsewhere.

However, given that this article is undergoing extensive rewriting elsewhere (as noted by that editor), it would seem wise to discuss any substantive changes here on the talk page, to achieve the best composite result. As this is a theorem that gets used a great deal, it would be nice to have it written up well. KSmrq

Response

I edited it with LaTeX for a purpose, though I probably should have explained it.

The main reason is readability. Much of what was done was to ensure that all mathematical parts are easily read. Another reason is that as it is a mathematical page, use of the math tags should be common. Whenever I read something on a mathematical page I like to have the size of the notation easy to read and that comes easy with LaTeX and is overall a more professional looking style for mathematical display.

At the same time, the text for the Unicode and normal "sup" tags looks rather messy in places.

I do however agree that the use of the $\exists$ symbol may be taking it a bit too far. Still, some of the notation such as $x\in \mathbb {N}$ should be something that anyone who is capable of understanding the theorem SHOULD know, though I take no position on exactly how many DO know this. As such I move that that be allowed to remain and that at least some of the math tags be restored in places where the style looks messy without it.

I also move that the minus sign just be put in as such. The use of the code for it is just confusing for an editor and it makes less sense overall IMO.

Now I must say that ${1 \over 3}$ is a bit much in terms of vertical alignment, so 1/3 would be best for that and other display style and overall neatness issues.

Guardian of Light 5 July 2005 14:07 (UTC)

Hmmm, there seem to be several different issues going on here, some to do with markup, others to do with audience.

First, are you familiar with Wikipedia:How_to_write_a_Wikipedia_article_on_Mathematics#Typesetting of mathematical formulas? I generally agree with the discussion there. However, I do think that eventually (i.e. when MathML or something similar is widely implemented), it will be appropriate to use LaTeX inline the way you were doing. I desperately wish that were the present state of affairs, but unfortunately it's not.

Regarding audience. I've taught people at this level before, and although I sympathise with your statement that they SHOULD know the notation, unfortunately in general they do not, and I think it's more important to make the topic at hand accessible rather than convince readers of the need to learn new notation. Nothing turns people off more than unfamiliar notation. More importantly however is an issue of style. Mathematical writing is not strings of symbols, and it doesn't always make it easier to read if it's written that way. I spend many hours each week reading maths papers in academic journals, and it is just as common to see "If x is an integer" rather than "if x \in Z", even though presumably the audience in that case knows the notation. Dmharvey Talk 5 July 2005 14:43 (UTC)

The page Wikipedia:How_to_write_a_Wikipedia_article_on_Mathematics also mentions preference on WP for using "for all" instead of $\forall$ and similarly for others. Dmharvey Talk 5 July 2005 14:45 (UTC)

---

At the present time our technology imposes awkward choices. Using a Mozilla browser, I can view and edit Unicode characters without entity codes. On my finished page, there is a noticeable difference between a hyphen ("-") and a minus sign ("−"), and the latter is more readable in formulae. This is not universally true, because the appearance of a character depends on the font selected (among other things). This may differ from the screen font when the page is printed! Even so, a benefit of Unicode is that it allows us to say exactly what we mean, which is a Good Thing; a hyphen is not a minus, any more than "equal to" is the same as "congruent to".

As for TeX versus HTML versus Wiki markup, just be glad we're not typing MathML markup (which is shockingly bloated). For pages outside Wikipedia a concise alternative is ASCIIMathML, which has the same ease-of-editing spirit as Wiki markup. Until then, note that templates for sup and sub can help. For example:

• ''a''{{subst:sup| ''p''−1}} ≡ 1 (mod ''p'')

produces

• a ^p−1 ≡ 1 (mod p)

As for symbols versus words, the edit that changed "then" to a right arrow made the lemma almost completely unreadable for me, and I've got a lot of that fabled "mathematical maturity". It adds confusion, not clarity; and, as noted above, it contravenes the Wikipedia guidelines.

KSmrq 2005 July 5 18:04 (UTC)

displayed equations in TeX

This is a continuation of comments I made above.

I disagree with KSmrq's edits that change the "displayed" equations to HTML. For example, in the intro I think it should be

$a^{p}\equiv a{\pmod {p}}\,\!$

rather than

a^p ≡ a (mod p)

I think we should only use HTML for inline equations where the PNG solution doesn't line up properly. Dmharvey Talk 5 July 2005 14:51 (UTC)

I agree with Dmharvey. Oleg Alexandrov 5 July 2005 15:55 (UTC)

As do I Guardian of Light 5 July 2005 19:12 (UTC)

---

Although MediaWiki currently offers minimal help, my goals are readability, portability, and (to a much lesser degree) economy of bandwidth. Without MathML support, say, trying to get nice-looking mathematics here is going to involve compromises. Every TeX-set formula adds an image to the page bandwidth load, and is typographically inconsistent with the body text. For integrals, binomial coefficients, and the like, it clearly improves displayed equations. For displayed a ^p ≡ a (mod p), it's not so clear. I have no strong objection to displayed TeX, but lean the other way. With my browser and settings, the changes in size and font are jolting. (But MathML pages look lovely. Sigh.) A detail that seems to help for me is to include a space before the superscript, to avoid italic collisions; I did not try to do that when I edited for conguence symbols.

Anyway, let's not spend too much time on such formatting details; the content of the page is still a mess! KSmrq 2005 July 5 18:04 (UTC)

Certainly I agree that content is the focus here. It sounds like as long as people's browsers do significantly different things, us editors will disagree on the optimal choice of markup. One day, when MathML or something similar becomes mainstream, I look forward to participating in WikiProject:Rewrite Every Single Equation on Wikipedia :-) Dmharvey Talk 5 July 2005 18:56 (UTC)

Though I do agree that it adds to the bandwidth somewhat, it can be made to not be excessive. Some lines such as f(x_n+1) is extremely awkward and takes a lot of coding whereas $f(x_{n+1})\,$ is so much faster and better rendered. I ask you return the page to the way it was after my last edit, and I will personally remove the excessive TeX tags until we are able to further discuss this issue here on the talk board.Guardian of Light 5 July 2005 19:12 (UTC)

I realized I might step on your toes by backing out your edits, and let me here and now apologize if doing so offended you. I'm sure your intent is to contribute to a better page, as you see it. So is mine. Bold edits are part of the Wiki experience; so are bold mistakes. And, so are differences of opinion about which is which! :-)

By my count, f(x_n+1) takes 27 characters, and $f(x_{n+1})\,$ takes 25 — a difference that hardly justifies the phrases extremely awkward and a lot of coding. As for much faster and better rendered, that's at best subjective, and I disagree. An alternative is to omit the "\," sequence that seems to be forcing creation of an image. For 23 characters and (in my browser) inline display, we can use $f(x_{n+1})$. As another test, the congruence of the theorem is either a ^p−1 ≡ 1 (mod p), for 37 characters (and inline), or $a^{p-1}\equiv 1{\pmod {p}}$, for 36 characters (and also inline for me). But I have to say, the Wiki markup gives me more readable results.

However, I have five objections to reverting to your edit.

1. The page was broken when I found it, displaying a Wiki parsing error!
2. It's time that would be better spent helping Dmharvey with his complete rewrite.
3. Changes like replacing "exists" and "then" with symbols need to be backed out.
4. For me and my browser, the readability before your changes is superior to that afterwards.
5. I incorporated a number of additional improvements to the content that had nothing to do with TeX versus Wiki markup.

Anyway, given that we expect the whole page will soon be replaced with a superior version, let's not waste any more time on the current page — and certainly not in TeX/Wiki edit wars.

To that end, should all the proofs carry over? The first proof using dynamical systems refers to rounding errors (!), and the second includes a request for review and cleanup (and I have done neither). Also, the base-n counting proof seems excessively … enthusiastic!, shall we say. Dmharvey's work on the bracelet proof is a huge improvement, with pictures even. That leaves the first three proofs, which all have their problems, including some handwaving. Also I see that the binomial proof ends with a last piece of dubious notation I thought I'd eradicated, but somehow didn't.

I rather like having a variety of proofs from different perspectives. Still, they must be made clear and correct, if not complete. (And omissions should be noted.) KSmrq 2005 July 6 02:33 (UTC)

I'd say no offense taken. I understand completely. I'll work on the direct one in terms of ease of understanding. However as to rendering, I guess I'll come back to that issue when the time is right. Until then, content is the biggest issue.Guardian of Light 6 July 2005 13:10 (UTC)

My plan is to keep the "direct proof", the "proof by induction", the "bracelet proof", the second "dynamical systems" proof, and the "group theory" proof. I have already written up the "direct" one, the "bracelet" one and the "group theory" one. I'm not going to do the first dynamical systems one because it is basically subsumed by the second one. The "base-n" digits one is actually identical to the "bracelets" one, using different notation, so I'm leaving it out too.

I'm working on the dynamical systems one currently. Please go ahead and do the induction one if you want to help. What I had in mind is to expand a bit on why the relevant binomial coefficients are divisible by p. Dmharvey Talk 6 July 2005 13:04 (UTC)

What Content should we fix first?

I think the content is another huge issue to deal with here as has been graciously stated by others already. What should we focus on cleaning up first?Guardian of Light 5 July 2005 19:20 (UTC)

As far as I'm concerned, all the action is taking place at Proofs of Fermat's little theorem/Rewrite. You're welcome to join me there. When that's up to scratch, I'm just going to copy it wholesale over to Proofs of Fermat's little theorem. Dmharvey Talk 5 July 2005 19:34 (UTC)

big rewrite complete

The rewrite is "complete" in the sense that I judge the quality to be sufficient to make it back to the main article.

I hereby declare Proofs of Fermat's little theorem/Rewrite to be an inactive page. All editing should now take place here instead.

Please go ahead and make it even more complete. Thanks. Dmharvey Talk 7 July 2005 17:27 (UTC)

Well done! The illustrations alone are a big improvement.

Since the edit history of the copied page won't appear here, I'm going to tweak my minor contribution (a rewrite of the binomial proof) back to counting from 0, not because I care that much but in part so it's visibly connected to me, if anybody wants to complain. Doesn't everybody count 0, 1, 2, 3, … ?  ;-)

I'm also going to try shrinking the "dynamical system" images, as an experiment. ;-) KSmrq 2005 July 8 00:49 (UTC)

Yeah, my images really are a piece of !@#$!. Have fun with them. Dmharvey Talk 8 July 2005 01:34 (UTC)

The nice thing about this experiment is that the images remain unaltered; just request them at a smaller size in the Wiki markup. This works for shrinking, but not necessarily for expanding. Of some interest is the fact that the server resamples the image and sends it at the requested size; it does not send the full-size original to let the browser resize it, which would probably look terrible and massively waste bandwidth. Some resampling algorithms are pretty bad, but this seems more careful; at least, these images scale down without ugly artifacts. For now, we can't upload SVG files, so I'm interested in putting a high-resolution version of some images (for other articles) in Commons, but requesting a smaller version in the article.

Truth to tell, I found the whole dynamical systems approach opaque until you added the images. My only concern was that they were so large they'd fill most of a small (640×480) screen, overwhelming the text.

While I was at it, I also removed uses of the template for subscripts, going back to the preferred HTML markup. For me it makes no visible difference on the page; I'd be curious to know if it affects you.

I hope you're happy with your work. To me, it looks much more like mathematics, and seems more accessible to less experienced readers. KSmrq 2005 July 8 03:58 (UTC)

Well if it were the main article I would agree, but a proof page seems more fit to be formal.Guardian of Light 8 July 2005 14:24 (UTC)

You are of course quite welcome to add a "formal" proof (although precisely what it would look like I'm not sure). However, I think you would do a great disservice to the intended audience of this page if you reduced the comprehensibility of the existing material for that audience. Just because it's a "proof", doesn't mean that the audience is any different. Dmharvey Talk 8 July 2005 15:57 (UTC)

No, sorry I was badly communicating. I meant to convey that I agree with the current style and that it has just the right amount of formality in it as well as a great deal of understandability.Guardian of Light 8 July 2005 16:16 (UTC)

Unfortunately I've just realised that the running example is complete nonsense. Now I'll have to go and fix it. Dmharvey Talk 8 July 2005 12:55 (UTC)

OK, well not complete nonsense. I had a and p the wrong way around. I've fixed it. Unfortunately this means p is rather small. But the smallest "interesting" case appears to be for 4^3 = 4 (mod 3), and I don't think 64 diagonal lines are going to be legible! Dmharvey Talk 8 July 2005 13:00 (UTC)

proof using a Field

The new proof, "Proof using a field", isn't that really the same thing as the proof by binomial theorem discussed earlier in the article? Dmharvey Talk 21:41, 17 October 2005 (UTC)

To me it seems that in fact the methods used in those paragraphs are basically different. What is now called 'by binomial theorem' is in fact a proof by induction. What is a called 'using a field' makes indeed use of the fact that a finite field has a characteristic. Bob.v.R 01:05, 27 October 2005 (UTC)

True, but your proof uses induction hidden in the line

$a^{p}=(1+1+...+1)^{p}=1^{p}+1^{p}+...+1^{p}=1+1+...+1=a\,\!$

and uses the identity $(x+y)^{p}=x^{p}+y^{p}$ (in F_p) without proof. Its proof is in fact what is already written down in the binomial theorem version on this page. Dmharvey Talk 01:59, 27 October 2005 (UTC)

It is not 'my proof', I didn't put it there, but only made a small edit to it. And at the moment indeed I tend to agree with you that those proofs are basically the same; the counting of 1's has not really to do with the characteristic of the field, but merely with the number 'a'. Bob.v.R 10:18, 28 October 2005 (UTC)

My apologies, I had misread the edit history. Dmharvey Talk 01:54, 29 October 2005 (UTC)

if u learn more about linear algebra u will find the proof using a field is the easiest proof

I agree that the proof using a field is a nice proof. What exactly about linear algebra do I need to learn to see why it is the easiest proof? Dmharvey 12:52, 30 November 2005 (UTC)

how about learn some basic field propositions?

OK. Which field propositions do you mean? Dmharvey 12:32, 9 December 2005 (UTC)

on the justification of using a prime

The example given is 2x2=5x2 (mod 6) which is all well and good, but six isn't even relatively prime to two, so I'd recommend a different example. If I can think of one in the next four minutes I'll do it myself, otherwise I have to leave and will probably forget.

Never mind, I'm an idiot. I seem to have forgotten division by a relative prime is well defined in modular arithmetic (I have been working WAY to hard if I've forgotten that). Still I think something concerning this fact should be mentioned in the article under why division using modular arithmetic is only justified when dividing by numbers relatively prime to the modulo.Guardian of Light 17:53, 22 December 2005 (UTC)

Group theory proof

I'm pretty sure that the group theory proof requires that every element of the group generate a cyclic subgroup. This should probably either be mentioned or proven.

Error in dynamical system proof

Lemma 1 proves that there are $n$ fixed points, not $n+1$: the fixed point 1 is counted twice. The proof still works given this correction since $(a^{p}+1)-(a+1)=a^{p}-a$. —The preceding unsigned comment was added by 203.173.167.211 (talk) 04:37, 7 April 2007 (UTC).

Two bracelet proofs

While my last math class was high school math, it seems to me that the bracelet proof is included twice, once without illustrations, and once with. If I'm wrong, and these are two distinct proofs, then I think this needs to be clarified. Otherwise, I'd say, keep the one with pictures.

-- trlkly 12:35, 1 June 2007 (UTC)

dynamical system proof : do we need T_n(1) ?

I'm too tired now to fully check the details, but it looks to me like that the fact that T_n is defined at 1 is inessential; and since it's a special case, the proof would be simpler without it. That is, I suggest T_n to be defined on the half-closed interval [0,1) only. The count of fixed points will decrease by 1 but the proof should withstand it. Am i too optimistic ? --FvdP 18:14, 12 June 2007 (UTC)

I agree with you; the inclusion of 1 is an ugliness there doesn't seem any reason for. -Chinju (talk) 05:26, 24 February 2013 (UTC)

Although I realize now that this makes the equivalence to the necklace-counting proof clearer! -Chinju (talk) 07:40, 27 February 2013 (UTC)

First authors of the proofs?

Please mention the first author who was the first person to come up with such an idea for each of the proofs offered.

just another one

I bounced this one off on IRC@ freenode, perhaps a more rigor oriented proof is:

a^p mod p = (1+1+1..a times)^p mod p which can be expanded using the Multinomial_theorem

now since each term but the ones which are of the form 1^p have "p" in the numerator and p is prime, the terms of the form 1^p will not be divisible by p,while the rest will be divisble by p

so a^p mod p = (1^p+1^p ..a times) mod p = a mod p

Similar to what DmHarvey wrote above, but the multinomial expansion is well known and can be rigorously proven

Questionable step

The article states:

"We can prove the cancellation law easily using Euclid's lemma, which states that if a prime p divides a product rs (where r and s are integers), then either p divides r or p divides s."

But this is a questionable "proof", since most developments of number theory define the concept of prime in a ring by precisely this property: "An element p is prime if whenever p divides a product rs, then p divides r and/or p divides s."

For this reason, it would probably be better to use a different means of completing this proof.Daqu (talk) 00:24, 31 December 2007 (UTC)

gap in first proof

I am not a mathematician. I just read the first proof out of curiosity. I followed everything except where it says "One can use the following rule to work out how many friends a given string S has: If S is built up of several copies of the string T, and T cannot itself be broken down further into repeating strings, then the number of friends of S (including S itself) is equal to the length of T." There is no argument given why this rule always works, and I cannot prove to my satisfaction that it does (although I trust that it does). —Preceding unsigned comment added by 2.120.138.129 (talk) 09:19, 22 March 2011 (UTC)

Proof by Counting Necklaces

I cannot understand how it was proved that if p is prime, each string will have p friends. The statement

"If S is built up of several copies of the string T, and T cannot itself be broken down further into repeating strings, then the number of friends of S (including S itself) is equal to the length of T. "

does not say anything about this being the only way a string can have less than p friends. Please give a proof of this. I cannot think of any.

First Proof

In the first proof, it is important to demonstrate why the proof works for prime exponents and only for primes, the exponent being prime indeed a very important part of the statement of Fermat's little theorem. User:Wcherowi reverted my edit that highlights this important point, perhaps they think that demonstrating why the proof works when the exponent is prime and why it fails when it is not a prime is not important/is "extraneous" - they should explain themselves here. 203.187.238.154 (talk) 07:57, 28 June 2020 (UTC)

On Wikipedia talk pages new comments are placed at the bottom of the page (unlike other places on the web) so I have taken the liberty of moving your comment here.--Bill Cherowitzo (talk) 18:39, 28 June 2020 (UTC)

You wrote this:

There aren't any others, because ABB is exactly 3 symbols long (ie the string is periodic with period 3) and 3 (the period) divides 12, the total length of the string. This is also the reason why the above proof doesn't work if the length of the string is not a prime number.

Starting with your parenthetical remark, while true, it is unrelated to the sentence you have attached it to, and the fact that 3 divides 12 is true for any period of any periodic string and says nothing about the current situation - hence, it is extraneous information. Finally, in the last sentence you have not given any reason for why the proof would fail! Consider, ABBAABBAABBA a string of length 12 which is periodic of period 4 (namely, ABBA). By what little reasoning you have given, i.e., 4 divides 12, the proof should work! This is really unacceptable editing, and I will revert it again.--Bill Cherowitzo (talk) 19:04, 28 June 2020 (UTC)

Okay, but it seems important to demonstrate why the proof necessarily works for primes, and doesn't necessarily work for composite exponents! Someone should add that to the proof.2409:4041:2E9A:C695:5576:7A71:1DDA:EC9 (talk) 07:03, 29 June 2020 (UTC)

Also, "the proof doesn't work for composite exponents" means that there is some composite exponent for which it doesn't work, for a proof is only a proof if it works for ALL values. So your example is extraneous. 2409:4041:2E9A:C695:5576:7A71:1DDA:EC9 (talk) 10:14, 29 June 2020 (UTC)

The explanation of why this only works for primes is contained in the next section (Completing the proof). In the section under consideration, there is nothing essential about primeness. The statement is valid no matter what the length of the small string. The only place in this example that being a prime comes into play is the statement that ABB can not be decomposed into smaller repetitive sequences (because 3 is prime, which is not explicitly stated). The example I gave you shows that this is the case.--Bill Cherowitzo (talk) 17:59, 29 June 2020 (UTC)

But I had stated nothing about the period being of prime length, only the whole string! Anyway, thanks for clarifying. 203.187.238.225 (talk) 18:59, 29 June 2020 (UTC)

Proof by geometric series

I don't understand the last proof in this article. Why is the sum in the first line divisible by p? KarlFrei (talk) 13:31, 24 June 2022 (UTC)