# 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, $S=\{p_1,p_2,...p_n\}$. Now form a number,
$N=p_1\cdot p_2\cdot ...\cdot p_n+1$.
Buy the fundamental theorem of arithmetic this number $N$ factors into primes number and thus is divisible by a prime number. But non of these prime numbers from $S$ divide $N$. Because if $p_k|N$ then $p_k|(p_1\cdot ...\cdot p_k\cdot ...\cdot p_n+1)$ but since $p_k|p_1\cdot ...\cdot p_k\cdot ...\cdot p_n$ then
$p_k|1$ which is not possible. Thus, there cannot be finitely many prime numbers.

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