# Help proving the following theorems

• Apr 1st 2014, 08:16 PM
hw333209
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.
• Apr 1st 2014, 09:37 PM
romsek
Re: Help proving the following theorems

2) follows almost immediately from (1)

3) follows immediately from (2)
• Apr 2nd 2014, 05:23 AM
Deveno
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....