# Math Help - Help proving the following theorems

1. ## Help proving the following theorems

1. For all natural numbers n, gcd (n, n +1) = 1
2. Let k be a natural number. Then there exists a natural number n (which will be much larger than k) such that no natural number less than k and greater than 1 divides n.
3. Let k be a na be a natural number. Then there exists a prime number larger than k.

2. ## Re: Help proving the following theorems

2) follows almost immediately from (1)

3) follows immediately from (2)

3. ## Re: Help proving the following theorems

Suppose n = dk, and n+1 = dm.

We have: 1 = (n+1) - n = dm - dk = d(m - k).

Since n+1 > n, dm > dk, so m > k. Thus d, m-k > 0 are both positive divisors of 1.

The only possibility is, therefore, that d = 1, and m-k = 1.

Since ANY common divisor of n and n+1 is equal to 1, the greatest such divisor is (of necessity) 1.

If you use the Bezout identity definition: that gcd(a,b) = min({ra+sb > 0: r,s integers}), we see that: (1)(n+1) + (-1)(n) = 1, so that it is immediate that gcd(n,n+1) = 1 (since this is the smallest positive integer).

For (2) we can use "Euclid's trick":

consider n = (1*2*....*k)+1.

Every number less than k divides n-1 = 1*2*...*k, but if a natural number r divides n-1, and divides n, we have r divides gcd(n-1,n). Now apply part(1) (using "n-1" in place of "n").

To prove (3) assume the contrary, that there is no prime number larger than k. Now use the same trick as in part (2), to show that the number we used there is not divisible by any prime, and thus....