Talk:Fundamental theorem of arithmetic

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

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) AliReply

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) AliReply

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)MvHReply

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

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

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

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

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

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

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

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

@Jasper Deng: There's a disagreement on whether highlighting that 2 is prime is necessary for induction proof to work. My point is that since we're basically doing well-founded induction over natural numbers with the divisibility relation, the base case is not 2 specifically, it is every prime. 2 would serve as the base case for every multiple of 2, but for n = 15 for example, we need 3 and 5 as base cases.

If we remove the "2 is prime" base case and try to run the proof on n = 2, we get that "2 is prime, there is nothing more to prove". So n = 2 is a special case of the base case already established, and there is no need to draw special attention to it.

For references, see page 41 of Elementary Number Theory by Rosen, or page 2 of Introduction to the Theory of Numbers by Hardy and Wright. Sheddow (talk) 19:12, 23 August 2024 (UTC)Reply

In strong induction, the induction step simply proves the statement for n whenever it is true for all k with 1 < k < n. Without the base case, the induction step proves nothing.—Anita5192 (talk) 19:24, 23 August 2024 (UTC)Reply

We're technically doing well-founded induction. [2]https://math.stackexchange.com/questions/2792061/understanding-the-definition-of-well-founded-induction The base cases of well-founded induction are the minimal elements, which under divisibility are the primes. If we were doing induction over the naturals under the normal ordering (<), then the base case would be 1 (or 0).

To reiterate, I'm not saying there's no base case. I'm saying the base cases are every prime, so there's no need to draw special attention to 2. If 2 were the only base case, how would you prove that 15 is a product of primes?

And feel free to check out the references I mentioned, they contain a proof of the fundamental theorem of arithmetic without mentioning that 2 is prime. Sheddow (talk) 19:45, 23 August 2024 (UTC)Reply

For n = 15, we would already have proved that 3 and 5 are prime; again beginning with the base case 2.—Anita5192 (talk) 20:24, 23 August 2024 (UTC)Reply

Well-founded induction says that if you want to prove that ${\displaystyle \forall a\in A,P(a)}$  for some proposition ${\displaystyle P(a)}$  it is sufficient to prove that for all ${\displaystyle a\in A}$ 

${\displaystyle (\forall b\in A,b\prec a\implies P(b))\implies P(a)}$ 

Let me give a quick proof. Assume for sake of contradiction that the set ${\displaystyle S=\{s\in A,\neg P(s)\}}$  is non-empty. Then it has a minimal element ${\displaystyle a}$ , ie. if ${\displaystyle k\prec a}$  then ${\displaystyle k\notin S}$ . But this is the same as saying that ${\displaystyle k\prec a\implies P(k)}$ , so we can use the inductive hypothesis to conclude that ${\displaystyle P(a)}$ , which contradicts the fact that ${\displaystyle a\in S}$ , so ${\displaystyle S}$  must be empty.

Whether strong induction requires a base case depends on the exact version you use. If you use the inductive hypothesis

${\displaystyle (\forall b\in {\mathbb {N}},b<a\implies P(b))\implies P(a)}$ 

then you don't need a base case, since it is just well-founded induction with ${\displaystyle <}$ . However, if you use

${\displaystyle (\forall b\in {\mathbb {N}},b\leq a\implies P(b))\implies P(a+1)}$ 

you need a base case, since ${\displaystyle \leq }$  is not a well-ordering.

The idea is basically that when ${\displaystyle \prec }$  is a well-ordering and ${\displaystyle a}$  is a minimal element, then there are no hypotheses in the premise, so you're forced to prove the "base case" ${\displaystyle P(a)}$ . If we use ${\displaystyle \leq }$  there are no minimal elements, so the premise is never empty.

I realized by the way that we don't need to do well-founded induction on the divisibility relation in this case, we can just use the strong induction described above. I'll just give a somewhat formal proof for completeness.

Let ${\displaystyle P(n)}$  be the proposition that ${\displaystyle n}$  can be written as a product of primes.

Let ${\displaystyle n\in {\mathbb {N}}_{\geq 2}}$ . Assume ${\displaystyle \forall k\in {\mathbb {N}}_{\geq 2},k<n\implies P(k)}$ . If ${\displaystyle n}$  is prime then we have ${\displaystyle P(n)}$  trivially. Otherwise there exist ${\displaystyle a,b}$  such that ${\displaystyle n=ab}$  and ${\displaystyle a,b\in {\mathbb {N}}_{\geq 2}}$  and ${\displaystyle a,b<n}$ . Then we can use the inductive hypothesis to conclude ${\displaystyle P(a)}$  and ${\displaystyle P(b)}$ , and since ${\displaystyle n=ab}$  we have ${\displaystyle P(n)}$ . Thus, ${\displaystyle \forall n\in {\mathbb {N}}_{\geq 2},P(n)}$ .

Note that we haven't bypassed the need for a base case; the base cases are just the points where we don't use the inductive hypothesis. You can only use the inductive hypothesis on ${\displaystyle n}$  when there exists an element strictly less than ${\displaystyle n}$ .

Interestingly, this same proof appears here: https://en.wikipedia.org/wiki/Mathematical_induction#Example:_prime_factorization

To be fair, this is a minor issue, the proof works either way. It just peeved me a bit to see what seems like an unnecessary repetition. Sheddow (talk) 16:21, 24 August 2024 (UTC)Reply