## Unique factorization

After receiving many questions from students, I recalled that I was myself quite unhappy with the proof that I presented of the unique factorization theorem as well as the theorem on infinitude of primes. As a general principle, it’s good to avoid proofs by contradiction. In fact, in my own research papers, I don’t think I’ve ever given a proof by contradiction.

In Monday’s lecture, I’ll present a more straightforward proof by induction of both theorems.

1. Kunal Patel
Posted October 8, 2008 at 8:41 pm | Permalink | Reply

sir i was just wondering, you know in the proof of the theorem that there are infinitely many prime numbers, doesnt the line p1.p2.p3…..pn +1 provide a simple algorithm for finding prime numbers? albeit, requiring a lot of computing!
vikram mukarji

2. Posted October 8, 2008 at 8:55 pm | Permalink | Reply

Yes, provided you could factor

$p_1p_2\cdots p_n+1.$

Remember, it is not itself a prime number in general. It just has a prime number factor that doesn’t belong to the list. Given a number that’s not a prime, it is exactly the problem of finding a prime number factor that admits no efficient algorithm.

Recall that if you’re satisfied with an inefficient algorithm, then you can keep finding prime numbers by trying to divide numbers one by one.