Talk:Fundamental theorem of arithmetic

A graph should have been displayed here but graphs are temporarily disabled. Until they are enabled again, visit the interactive graph at pageviews.wmcloud.org

Archives

1

This page has archives. Sections older than 365 days may be automatically archived by when more than 10 sections are present.

Joke: There are no Uninteresting Numbers[edit]

First, one must consider what numbers actually are interesting: 1 is unity, 2 is the smallest even and smallest prime number, 3 is the smallest odd prime number, 4 is the first whole number that is the square of another integer, 5 is significant in Biology (many vertebrates have some version or form of 5 digits), 6 is the first perfect number, 7 is a historically important number in many religions and mythologies, etc, etc....

Assume that one can eventually find and group all of the Uninteresting numbers. By the principle of Well Ordering, they can be arranged from smallest to largest. Let's look carefully at this group:

The first number that one comes across is the smallest of all the Uninteresting numbers known to exist in the universe. Well, that's interesting....

--Daydreamer302000 16:37, 28 February 2007 (UTC)[reply]

We have an article about the interesting number paradox. PrimeHunter (talk) 10:34, 22 October 2018 (UTC)[reply]

But then the next Uninteresting number is really the smallest, which robs the previous one of all interest. BMJ-pdx (talk) 14:57, 26 July 2021 (UTC)[reply]

Alternate proof is really the same proof[edit]

It looks to me like the only difference is the wording used and the fact that the "alternate" proof assumes Euclid's lemma without proving it.

Since the proof of Euclid's lemma can be found in its own main article, I think it makes sense either to simply reference Euclid's lemma here (removing its proof from this page, and condensing the two uniqueness proofs into one since they're really the same), or to build up the entire proof of unique prime factorization from first principles, with separate sections for the division algorithm, Bézout's identity, etc.

18.189.112.192 (talk) 06:44, 22 December 2011 (UTC)[reply]

I agree, the alternate proof is the same as the main proof but skips steps (including Euclids lemma) to pull "Therefore,p_1q_1|s-p_1q_1" out of nowhere. Further the proofs concludes by stating nothing more than it's initial assumption (that s is the smallst integer with a non-unique factorization) and thus does not prove anything. I have removed the alternate proof. 213.246.84.162 (talk) 11:43, 1 April 2012 (UTC) Ali[reply]

Someone has now added a good alternate proof so this discussion is now mute. 213.246.117.133 (talk) 08:43, 14 May 2012 (UTC) Ali[reply]

I've rewritten the article in an atttempt to make it clearer and less redundant.

Virginia-American (talk) 19:27, 1 July 2012 (UTC)[reply]

The alternate proof is not something one finds in textbooks, it probably violates the original research policy. MvH (talk) 01:20, 6 April 2014 (UTC)MvH[reply]

The Alternate Proof should bee removed. It is "doublicated" material. It seems to be "own work". It is not relevant for an encyclopedia to have multiple proofs.

LMSchmitt 08:49, 30 September 2020 (UTC)[reply]

The 'alternative proof' needs an authoritative reference. The one given here is a version, although less elegant and less concise, of the 'abnormal number' proof given in Hardy and Wright, and which they attribute to F. A. Lindemann (1933). The reference to the Mathworld article on 'abnormal numbers', which has no context in the current article, suggest that the original context has been edited out and perhaps should be replaced. 14.201.149.49 (talk) 07:24, 24 December 2020 (UTC)[reply]

A correct version of this proof, which does not assume Euclid's lemma, appears on p. 45 of Dawson, John W., Bruce S. Babcock, and Steven H. Weintraub. 2015. Why prove it again: alternative proofs in mathematical practice. http://public.ebookcentral.proquest.com/choice/publicfullrecord.aspx?p=3567731. The alternative proof is valuable since the proof of Euclid's Lemma is not, in itself, 'obvious' to most readers. Arguably, the "alternative proof" is the more intuitive one, although it is less commonly seen. (NOTE: in a previous edit I wrote: "As it stands, the 'alternative proof' assumes Euclid's Lemma (" p1 must occur in the factorization of either q1 − p1 or Q.")," thinking that this was an error. However, at that point in the proof, the FTA (and therefore EL) can be assumed true for numbers less than s, so this is not a fault in the proof; it is how the proof is supposed to work! I will simply add the reference. TheNothingNihilates (talk) 16:39, 10 September 2021 (UTC)[reply]

The alternate proof is still wrong. It assumes that p1 must either divide (q1-p1) or Q because each of them is assumed to have a unique factorization. But assuming that p1 is part of it too much of a jump for a proper proof. Pavlix (talk) 11:11, 27 March 2022 (UTC)[reply]

"Each of them is assumed to have a unique factorization": their product is also assumed to have a unique factorization. All these assumptions are parts of the induction hypothesis. So, the proof is correct, since p1 appear explicitly in a factorization of their product. D.Lazard (talk) 13:45, 27 March 2022 (UTC)[reply]

Since about 2005, several years after I retired from teaching at Stanford, I've been maintaining the website Sayings of Chairman Pratt. The third last entry in the section Science and Technology is titled "Number theory" and offers "World's shortest rigorous proof of unique factorization". The proof I gave (for uniqueness) is as follows.

Let the least counterexample be pr = qs with p<q prime and r,s nonempty strings of primes. By leastness no prime occurs on both sides. Moreover p cannot divide q-p. Hence p(r-s) = (q-p)s yields a smaller counterexample.

Although I'd never seen a shorter proof I also didn't expect it to be original. But now that I read this discussion I'm starting to wonder. Vaughan Pratt (talk) 01:48, 14 April 2022 (UTC)[reply]

Or you saw it from a colleague and don't remember. See [1]https://books.google.ca/books?id=XB2nd2ovakIC&lpg=PA574&ots=YS6SH4zuHd&pg=PA574&redir_esc=y#v=onepage&q&f=false 199.85.124.43 (talk) 19:38, 18 July 2023 (UTC)[reply]

Flawed[edit]

Factors are not needed to describe a number's properties and this theorem fails to predict the position of primes. Scrap it — Preceding unsigned comment added by 2601:449:8200:a430:483f:9db0:e740:6d4f (talk • contribs) 09:43, 19 February 2018 (UTC)[reply]
... says who? Please, add comments at the bottom and sign them.

Some, if not most, prefer to keep it, and what is it that one "needs". Factors are useful to many, and what is "predict the position"?. Purgy (talk) 11:20, 19 February 2018 (UTC)[reply]

This theorem is very important to prove that certain sets are countable. For example, that "the set of finite words over a countable alphabet is countable" is easily proven with the help of this theorem. The quoted statement is important in Model Theory. LMSchmitt 09:10, 30 September 2020 (UTC)[reply]

Question about "Elementary proof of uniqueness"[edit]

The proof shows that any integer s has a unique factorization of primes.

At some point the proof introduces an integer t and says:

["t= (q1-p1)(q2....qn) and note that 1 < q2 <= t < s. Therefore t must have a unique factorization..."]

(by the way , it was also mentioned that q1>p1)

(1) Given that we are trying to prove unique factorization and have not proved it at this point in the proof, why can we say at this stage that t has a *unique* factorization?

(2) At this point, its easy to see that t has a *different* factorization than s.

(3) But It seems hard to understand that it has a *unique* factorization.

(4) After all the whole point of the proof is to prove that s has a unique factorization.

(5) At that point of the proof (where t=(q1-p1)(q2....qn)) is introduced, s hasnt yet been proven to have a unique factorization. Is it safe to say at that time then that t has a unique factorization?

Looking again at t=(q1-p1)(q2....qn), what could (q1-p1) be at this point?

It could be a composite number, then we are left with:

t = [some set of primes] (different from s) and how do we know that t is uniquely represented by those set of primes, given that we have not proved this in general yet?

Can anyone help with this? Thanks! Mooingzebra (talk) 20:03, 19 December 2018 (UTC)[reply]

It has been supposed that s is the smallest integer that does not have a unique factorization. Thus, as t < s, it has a unique factorization. D.Lazard (talk) 20:36, 19 December 2018 (UTC)[reply]

Oh! Thanks for the quick response.Mooingzebra (talk) 07:33, 20 December 2018 (UTC)[reply]

Use of "multisets"[edit]

The following is copied from my TP:

The product of a multiset is undefined at best? Well, I meant it to be the product of all the items in the multiset. Seems straightforward enough to me... KarlFrei (talk) 15:40, 14 February 2019 (UTC)

I regret if my edit summary was perceived as offensive. Of course I agree to the intended meaning being straightforward, but nevertheless I think the formulation is not sufficiently rigorous to remain in a WP-article. Furthermore, I agree to the opinion, stated in this discussion that the introduction of multisets (also known as "bags") requires more machinery than the current formulation. Purgy (talk) 11:25, 15 February 2019 (UTC)[reply]

I don't know what "not sufficiently rigorous" could possibly mean in this context; the statement (with the missing words "of primes" added) is completely correct and rigorous. However, I agree that there doesn't seem any compelling reason to add the sentence. --JBL (talk) 16:01, 15 February 2019 (UTC)[reply]

which theorem is this?[edit]

i have a theorem in my textbook which has been derived from the fundamental theorem of Arithmetic. the theorem is as follows" let p be a prime number and a be a positive number integer. if p divides a², then p divides a." which theorem is this?Huzaifa abedeen (talk) 05:33, 30 September 2020 (UTC)[reply]

It is a special case of Euclid's lemma. D.Lazard (talk) 08:41, 30 September 2020 (UTC)[reply]

Unclear reference to Euclid's Lemma[edit]

In the proof of uniqueness is the following phrase "We see p1 divides q1 q2 ... qk, so p1 divides some qi by Euclid's Lemma". However the article on Euclid's Lemma linked to only talks about the case where a prime divides the product of two numbers. While it's not difficult to extend the proof to multiple numbers this should be clearer. — Preceding unsigned comment added by Ximera~enwiki (talk • contribs) 10:38, 13 April 2021 (UTC)[reply]

Name for a number's set of prime factors?[edit]

Isn't there a name for the set comprising a number's prime factors? I see nothing in the various prime/composite-related articles. BMJ-pdx (talk) 15:02, 26 July 2021 (UTC)[reply]

BMJ-pdx, see an answer to the same question in Talk:Greatest common divisor D.Lazard (talk) 15:17, 26 July 2021 (UTC)[reply]

Incorrect statement in generalization to gaussian integers[edit]

It is written

the non-zero, non-unit numbers fall into two classes, primes and composites, and that (except for order), the composites have unique factorization as a product of primes

This is wrong. For example,

(1+i)(2+i) = (1-i)(2i-1).

It is true only if one chooses one representative for each equivalence class of primes modulo the units. Or, one should add "(except for order and factors of units)", or similar. — MFH:Talk 13:04, 7 April 2023 (UTC)[reply]

Fixed. D.Lazard (talk) 15:55, 7 April 2023 (UTC)[reply]

Contradicting/incomplete sources in History section[edit]

The History section states

"While Euclid took the first step on the way to the existence of prime factorization, Kamāl al-Dīn al-Fārisī took the final step and stated for the first time the fundamental theorem of arithmetic."

In this sentence, two sources are cited:

8. A. Goksel Agargun and E. Mehmet Özkan."A Historical survey of the Fundamental Theorem of Arithmetic" (PDF). Historia Mathematica: 209. "One could say that Euclid takes the first step on the way to the existence of prime factorization, and al-Farisi takes the final step by actually proving the existence of a finite prime factorization in his first proposition."

9. Rashed, Roshdi (2002-09-11). Encyclopedia of the History of Arabic Science?. Routledge. p. 385. ISBN 9781134977246. "The famous physicist and mathematician Kamal al-Din al-Farisi compiled a paper in which he set out deliberately to prove the theorem of Ibn Qurra in an algebraic way. This forced him to an understanding of the first arithmetical functions and to a full preparation which led him to state for the first time the fundamental theorem of arithmetic."

The first source however links only to pages 162-173 of "A Historical survey of the Fundamental Theorem of Arithmetic" and on page 172 the authors disagree that al-Farisi stated or proved the uniqueness of prime factorisation:

"In our estimation, al-Farisi neither stated nor proved uniqueness, and it was not his intention to do so."

So the first source disagrees with the second that al-Farisi stated and proved (the entirety of) the FTA. In fact, the authors directly cite and criticise a different work by Rashed, who provided the claim that al-Farisi stated and proved the FTA in the second source. Muisnotforyou (talk) 16:10, 1 February 2024 (UTC)[reply]