# Indirect proof of Infinate number of primes

• Mar 19th 2006, 07:41 AM
Lazarath
Indirect proof of Infinate number of primes
IN class we derived the following expressionto express "There are an infinate number of primes" using predicates prime(x) : x is a prime and g(x, y): x > y

There exists a "z" in N, prime(z) and [for all "x" in N , (prime(x) --> there exists a "y" in N, (prime(y) and g( y, x)))]

I believe they want me to prove this using the contrapositive

any hints?

Laz
• Mar 19th 2006, 10:31 AM
ThePerfectHacker
Quote:

Originally Posted by Lazarath
IN class we derived the following expressionto express "There are an infinate number of primes" using predicates prime(x) : x is a prime and g(x, y): x > y

There exists a "z" in N, prime(z) and [for all "x" in N , (prime(x) --> there exists a "y" in N, (prime(y) and g( y, x)))]

I believe they want me to prove this using the contrapositive

any hints?

Laz

I do not know what your are asking but there is an elegant indirect proof of infinitude of primes that I know; it comes from Euclid. Assume, that there are finitely many primes, $\displaystyle S=\{p_1,p_2,...p_n\}$. Now form a number,
$\displaystyle N=p_1\cdot p_2\cdot ...\cdot p_n+1$.
Buy the fundamental theorem of arithmetic this number $\displaystyle N$ factors into primes number and thus is divisible by a prime number. But non of these prime numbers from $\displaystyle S$ divide $\displaystyle N$. Because if $\displaystyle p_k|N$ then $\displaystyle p_k|(p_1\cdot ...\cdot p_k\cdot ...\cdot p_n+1)$ but since $\displaystyle p_k|p_1\cdot ...\cdot p_k\cdot ...\cdot p_n$ then
$\displaystyle p_k|1$ which is not possible. Thus, there cannot be finitely many prime numbers.

$\displaystyle \mathbb{Q}.\mathcal{E}.D$