Talk:Fundamental theorem of arithmetic

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: B Class Top Priority  Field: Number theory

This may be a simplification of the proof: Assume N=p1.p2...pn = q1.q2...qm is the smallest number with two prime factorizations. Assume q1 < p1. (p1-q1).p2...pn = q1.(q2...qm - p2...pn) is smaller than N, hence has unique factorization. q1 must then be a factor of p1-q1. So p1-q1=k.q1 for some integer k. Thus p1=(k+1)q1, which contradicts p1 being prime.

The simpler proof above (about uniqueness) is neat. Anyone willing to put that in the article (I'm no wiki-savvy)?

Also, I cannot follow the final step in the uniqueness part in the article ("Proof by infinite descent"). Once I have k = rq2...qn / p1, it seems clear that p1 cannot divide q2...qn since every qj is different from p1, so p1 must divide r, which is false since r < p1 (for a proof that p1 cannot divide q2...qn, inductively apply the result that if d divides ab and GCD(a,d) = 1, then d divides b). So it seems the last step of the proof in the article is useless (and anyway I cannot understand that, but maybe I'm dumber than average).

I think using · as a multiplication operator in this article is a bad idea. It's not recognisable to lay people. CGS 16:45, 21 Oct 2003 (UTC).

Except that the use of dot is uncluttered, consistent, and used by mathematicians as it is easier to write than cross. If you are worried by inconsistency with rest of wiki, then think of it as elegant variation, cf. Fowler Stan 23:49, 24 Feb 2004 (UTC)

Contents

[edit] Joke: There are no Uninteresting Numbers

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 principly 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) PS: More thorough analysis of the Interesting Number Paradox

[edit] Applications

The 5th and 6th lines of this paragraph are absolutely obscure

---

I second. Except I would venture to say that this entire section is poorly worded. I was unable to understand what was being said until I read it over and over and over again AND read some other references elsewhere.

I replaced now at some places in this paragraph 'factor' by 'divisor' (prime and non-prime) to perhaps diminish the confusions between a divisor and a prime factor. Hopefully this helps. Bob.v.R 17:07, 15 September 2005 (UTC)

[edit] changeing the wording

How about changing the wording from

and there are no other such factorizations of 6936 or 1200 into prime numbers, except for reorderings of the above factors.

to

and there are no other possible factorizations of 6936 or 1200 into prime numbers, if we ignore the ordering of the factors.

[edit] Paragraph sounds funny

Suppose there were a positive integer which can not be written as a product of primes. Then there must be a smallest such number: let's call it n. This number n cannot be 1, because of our convention above. It cannot be a prime number either, since any prime number is a product of a single prime, itself. So it must be a composite number. Thus n = ab where both a and b are positive integers smaller than n. >>>Since n was the smallest number for which the theorem fails, both a and b can be written as products of primes.<<< But then n = ab can be written as a product of primes as well, a contradiction.

There is something wrong with the paragraph above.

Since n is the smallest number which can not be written as a product of primes then both a nd b cannot be written as a product of primes. BUT didn't we say n is the smallest number which can not be written as a product of primes and the number n , a and b are positive integers. This means a is smaller than n and b is smaller than n. If a cannot be written as a product of primes and a is smaller than n then n CANNOT be the smallest number which can not be written as a product of primes. Hence a contradiction.

I prefer the first version. The first sentence of the second version jumps a step.

Charles Matthews 10:19, 29 Nov 2004 (UTC)

I think the original poster misunderstands the nature of the proof. It is simply not true that "n is smallest number which cannot be written as product of primes" implies "a and b cannot be written as a product of primes". In fact, it is just the opposite, by our choice of n. We are using well-ordering, and then showing that the existence of such a least n always leads to a contradiction. Revolver 20:33, 29 Nov 2004 (UTC)

[edit] Proof by infinite descent

The unicity proof given as "by infinite descent" uses the division algorithm but not the Euclidean algorithm (much less its generalisation Bézout's lemma). In this way, it's more elementary (you need fewer facts about division, or if you prefer, you need not consider the consequences of the division algorithm in as much depth).

Who first came up with that argument?

—Toby Bartels 09:35, 26 July 2006 (UTC)

[edit] One

Might one say that the set of prime factors of one is the empty set? Thus, one is not prime because prime numbers are those where the set of factors has a cardinality of 1.

Several sources I've seen only state the Fundamental Theorem of Arithmetic for integers strictly greater than 1. Of course, I understand the argument about 1 being an empty product of primes, and I do admit that this convention makes the statement of the Fundamental Theorem of Arithmetic a lot cleaner. Nevertheless, I think it's worthwhile at least to mention that there are two prevalent conventions. In other words, I propose we leave in the explanation of 1 being the empty product, but that we also state that the result is often stated only for integers greater than 1. I don't mind making the change myself, but I wanted some kind of discussion first. For some odd reason, these small trivialities produce huge controversy and I don't want to step on anyone's toes. VectorPosse 06:32, 3 March 2007 (UTC)

The article as it is right now looks ok to me. The statement that 1 is the empty product is sufficient to avoid confusion. Some references indeed only state the Fundamental Theorem of Arithmetic for integers > 1 and just don't bother with 1. But there is no controversy as long as they do not claim that 1 is not representable as a product of primes. After all 0 would be the real exception. 85.0.100.1 09:18, 3 March 2007 (UTC)
I definitely see your point. I guess I'm just trying to answer the inevitable question that arises when a non-mathematically trained person (surely a person to whom this article ought to be directed) wonders why their textbook says n > 1 and this article says n = 1 too. I suppose they could click on Empty product, but I think this concept is a bit advanced for, say, a junior high student. Also, I'm concerned with the page Integer factorization. It makes no mention of empty product, so to find out why there's a difference between their textbook and the statement made on that page, they would have to click through Fundamental theorem of arithmetic and then on to Empty product. VectorPosse 10:49, 3 March 2007 (UTC)
This discussion started because someone claimed on the Integer factorization page that 1 does not have a prime factorization, which was incorrect. A link to the Empty product rule could possibly help to make this page clearer. Excluding the factorization of 1 from the Fundamental theorem of arithmetic would be a bad idea because it leads to other confusions. E.g., try computing GCDs by factoring the numbers first. What is the GCD of two integers that have no prime factor in common? How do you explain gcd(1,n) = 1? Junior high school is also the time when students are typically faced with a0 = 1. While some might be confused by a claim that the empty product is 1 they should at least be able to understand that paradoxically looking definitions exist. 85.2.101.149 12:10, 3 March 2007 (UTC)
To make sure I'm being clear: I do not wish to remove n = 1 from any statement anywhere. I just want to acknowledge in the text that such a discrepancy does occur, and explain why n = 1 is okay despite what many textbooks say. (Or rather, what many textbooks fail to mention.) VectorPosse 12:20, 3 March 2007 (UTC)
I do think VectorPosse has got the right approach here. When there is disagreement among the sources we should document the disagreement not try to resolve it one way or the other. If might also be worth noting that 1 was consider prime a hundred years back, and that for most purposes it does not really matter which convention is chosen. --Salix alba (talk) 15:06, 3 March 2007 (UTC)
I mostly agree with VectorPosse too, though I'd give slightly different reasoning. We need to keep in mind that Wikipedia is a reference work, not a teaching tool. So I'm a little uncomfortable with trying to think of questions the reader might have. That line of thinking tends to lead to chatty, discursive writing not appropriate to an encyclopedia. But he's completely right that it's not our role to choose between commonly used conventions based on what we think is the more reasonable of them. Nor should we evade our responsibility to report the conventions by arguing that the n>1 sources don't explicitly say that it isn't also true for n equal to one. --Trovatore 17:25, 3 March 2007 (UTC)
While this debate is fascinating, the article contained a fatal flaw in the statement. I have fixed that, in a manner I hope is satisfactory and self-explanatory. (See paragraph three.) In the process, I added a reference to the incomparable Hardy & Wright, simultaneously introducing use of the lovely new {{Citation}} template and {{Harv}} references (which I find far superior to prior alternatives), per WP:CITET. Actually, I take advantage of the convenient {{Harvtxt}} template. Still, I have compromised, in that I strongly prefer Hardy & Wright's "positive integer" over the ambiguous "natural number", which my favorite authors (such as Mac Lane) begin at zero. (Since we already have Z+, why bother to have N without 0?) A tempting variation is Michael Artin's "every nonzero integer", with the form c×p1×⋯×pk, c = ±1, k ≥ 0; but this seems less common. --KSmrqT 00:39, 4 March 2007 (UTC)
If the theorem had been phrased as: "Every positive integer is the product of a unique multiset of primes", not only would the issue with the factorization of 1 have been skirted, but also the issue of the meaning of "unique product". After all, 6 = 2 × 3, but we also have that 6 = 3 × 2, so how unique is the product?  --LambiamTalk 06:31, 4 March 2007 (UTC)
Uniqueness is covered here by "Because multiplication is commutative, the order of factors is irrelevant." Hardy & Wright first introduce a standard form,
n = p_1^{a_1}p_2^{a_2} \cdots p_k^{a_k} \qquad (a_1 > 0, a_2 > 0, \dots, p_1 < p_2 < \cdots) . \,\!
Then their Fundamental Theorem reads
Theorem 2 (The fundamental theorem of arithmetic). The standard form of n is unique; apart from rearrangement of factors, n can be expressed as a product of primes in one way only.
However phrased, this requires less machinery than the introduction of multisets (also known as "bags"). I trust you concur with their elimination of an unnecessary distinction between composite and prime numbers, since both factor uniquely. --KSmrqT 08:36, 4 March 2007 (UTC)

[edit] seems inconsistent

The 'fundamental theorem of arithmetic' states "every natural number greater than 1 can be written as a unique product of prime numbers". If 'product' implies multiplication, what are the factors of a prime number? The typical statement "a prime has no divisors other than 1 and itself", is contradictory because '1' is not considered prime, (if 1 is not prime then the 'ftoa' is not correct), and redundant because all natural numbers >1 are divisible by 1 and therefore this is not a qualifying condition. If the set M is all natural numbers>1, i.e. multiples of 1, then the primes are a subset P of M and can be defined as 'multiples of 1 only". Since 1 is not included in M it cannot be considered a prime.This gives a reason and not a convenience. The set M - P is C, the composites. The 'ftoa" could be restated "all composite natural numbers can be written as a unique product of prime numbers. phyti64.24.176.115 19:38, 19 March 2007 (UTC)

You are misinterpreting the word "product". A product need not have two or more numbers in it. Think of product as a list of numbers: if there is more than one number in the list, then you multiply them together. But if there's only one number, then the "product" consists of only that number. So a prime number can be written uniquely as a "list" of prime factors, namely the "list" containing just that prime number. This avoids questions about one. (See the discussion higher up on this page for the interpretation of the FTOA for the number one.) VectorPosse 00:55, 20 March 2007 (UTC)

[edit] Merge from Abnormal number?

Abnormal number has almost no content and I think it would fit better as a short comment in the proof section here. http://mathworld.wolfram.com/AbnormalNumber.html says "Hardy and Wright (1979) prove the fundamental theorem of arithmetic by showing that no abnormal numbers exist". PrimeHunter 15:16, 22 May 2007 (UTC)

[edit] Proof by infinite descent

I rewrote some of this proof with the aim of greater clarity. (I had a little difficulty following the old version, probably because of my old age and exhausted brain cells:) ) I also thought that, since this is a purely number-theoretic result, it would be nice to offer a proof that doesn't require any fractions (as the original version did) and sticks purely to natural numbers. I hope that others find it easy to follow! This is my first venture into mathematical proofs on Wikipedia, so please forgive me if I've violated any policies or guidelines. Cheers.... Grover cleveland (talk) 05:19, 14 March 2008 (UTC)