HW1, Chapter 0, Problem 19, MA453, Fall 2008, Prof. Walther
Problem Statement
Could somebody please state the problem?
Discussion
Proof by contradiction.
Assume that there are only a finite number of prime numbers $ p_1,p_2,......,p_n $ . Then by using the fact from exercise 18 (Let $ p_1,p_2,....,p_n $ be primes. Then $ p_1p_2.....p_n +1 $ is divisible by none of these primes), $ p_1p_2....p_n +1 $ is not divisible by any prime. This means $ p_1p_2...p_n +1 $ (which is larger than our initial conditions) is itself prime. This contradicts the assumption that $ p_1,p_2,...p_n $ is the list of all primes.
--Angela Akcooper 20:09, 6 September 2008 (UTC)
Angela, there is an inaccuracy in your proof at the moment. You state that "This means $ p_1p_2...p_n +1 $ (which is larger than our initial conditions) is itself prime." This is not necessarilly true. If it were, we wouldn't have such troubles finding large primes. What would make your proof accurate is to say the following: "This means" that our chosen number $ p_1p_2...p_n +1 $ is either prime, or has no prime factorization. However, by the Fundamental Theorem of Arithmetic, every number has a prime factorization, or is itself prime. In either case, at least one prime was not in the supposed finite list of all primes. The key to the contradiction is that $ p_1p_2...p_n +1 $ contains primes in its factorization that we haven't listed in our finite set of primes, not that it is necessarilly itself prime.
--Josh Magner
