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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: