Prove that n and (n+1) must be relatively prime?

Question

how do i go about proving the following:
let n be a positive integer. prove that n and (n+1) must be relatively prime. help!

Answer 1

A standard technique is "Proof by contradiction". There, you assume that the opposite is true, and then show that this leads to some nonsense.
In your case: Assume that they are NOT relatively prime. Then they must have have a common factor, which we call X, and which is at least 2.
Then n = K times X, for some K >= 1.
And also n+1 = L times X. L must be larger than K (otherwise, L times X = n + 1 would be smaller than n, which is nonsense).
The smallest integral number after K is K + 1. So n + 1 would have to be at least (K+1) times X = K times X + X. But above, we had to assume that X is at least 2 - and therefore, K times X + X is at least 2 more than K times X, which is n ... so ...

Answer 2

one way to do this would be proof by contradiction.

let's assume that n and n+1 are not relatively prime. then there exists an integer x such that:

x divides or xln and
x divides n+1 or xl(n+1)

then by using a theory, x must divide (n+1) - n
but (n+1) - n = 1. If x>1, this is impossible.

So x must be equal to 1.

Hence, n and n+1 are relatively prime.

Answer 3

One way to approach the proof is to assume that n and n + 1 are NOT relatively prime. A contradiction to your assumption should appear pretty quickly. BTW, which class are you taking that this problem came from?

Answer 4

You must know that two integers a and b are relatively prime if and only if there are integers x and y such that ax + by = 1.

You find at least one pair (x,y) which does the job. (There are infinitely many such pairs.)