Hacker News new | past | comments | ask | show | jobs | submit login

I haven't looked at any proofs for the FTA. Could somebody point out if I made any mistakes on the one I've arrived at?

[1] Proof by induction that if a positive integer has a prime factorization, then it is unique.

We're inducting over Z_N, where Z_N is the set of all positive integers with at least one known prime factorization using exactly N number of primes. Call this factorization Pn = p_1 * p_2 * ... p_n

For every case, split into proof by cases and contradiction: suppose there is an element Z in set Z_N had another factorization Fn.

- If Fn has the same number of factors as Pn, divide both sides by p_i. Since Fn / p_i must be an integer, Fn must contain p_i, or else one of its factors f_i actually isn't prime by Euclid's Lemma.

- If Fn has k more factors than Pn, then divide Pn by (f_1 * f_2 * ... * f_n). Then (f_n+1 * ... * f_n+k) = X for some composite integer X > 1. Thus Fn = X * (f_1 * f_2 * ... * f_n) = (p_1 * p_2 * ... * p_n) = Pn. Since (p_1 * p_2 * ... * p_n)/Z must be an integer, Z must divide into one of the factors p_i by Euclid's lemma, which is impossible since they are prime by definition.

- Similar argument to above if Pn has more factors.

[2] Proof by contradiction: Every positive integer Y greater than one has a prime factorization.

Suppose not. We know Y = Y * 1. So Y must be composite in order for it to not have a prime factorization. Hence, we know that Y = a * b, (a, b > 1). At least one of the two must be composite or else Y has a prime factorization, so let's say (a) is composite. Then a = c * d (c, d > 1). Then at least one of the two factors must be non prime or else we've found the prime factorization for Y. Repeat ad infinitum to show that if Y does not have a prime factorization, then it must be the product of an infinite number of composite factors, with every factor great than 1. Hence contradiction.

So every positive integer greater than 1 has a prime factorization, and it must be unique.




"If Fn has the same number of factors as Pn, divide both sides by p_i. Since Fn / p_i must be an integer, Fn must contain p_i, or else one of its factors f_i actually isn't prime by Euclid's Lemma."

You would have to prove that first. https://en.m.wikipedia.org/wiki/Euclid%27s_lemma:

"This property is the key[4] in the proof of the fundamental theorem of arithmetic

[4] In general, to show that a domain is a unique factorization domain, it suffices to prove Euclid's lemma and ACCP."

(https://en.m.wikipedia.org/wiki/Ascending_chain_condition_on... looks more intimidating than Euclid's lemma to me, but may be easier to prove.)


Got it. I was trying to do a proof while avoiding abstract algebra as much as possible, given how rusty I am with it.

Thanks for the feedback, and additional things to take a look at!




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: