# Thread: Indirect proof of Infinate number of primes

1. ## 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

2. 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$