1. coprime

Let $\displaystyle n \in \mathbb{N}$. Are $\displaystyle n$ and $\displaystyle n+1$ relatively prime? How about $\displaystyle n$ and $\displaystyle n^2+1$?

My answer is yes, both $\displaystyle (n,n+1)=1$ and $\displaystyle (n, n^2+1)=1$. But is there a way to show these are true?

2. Originally Posted by dori1123
Let $\displaystyle n \in \mathbb{N}$. Are $\displaystyle n$ and $\displaystyle n+1$ relatively prime? How about $\displaystyle n$ and $\displaystyle n^2+1$?

My answer is yes, both $\displaystyle (n,n+1)=1$ and $\displaystyle (n, n^2+1)=1$. But is there a way to show these are true?

Since $\displaystyle (n,n+1) = 1$ and also $\displaystyle (n^2 , n+1) = 1$

we will have $\displaystyle (n^2 + 1 )- (n ) = n + (n-1)^2 = [(n-1)+1] + (n-1)^2$ which doesnt' contain any factor , so $\displaystyle ( n^2+1,n ) = 1$

3. To show that (n, n+1)= 1, suppose it is not. Suppose (n, n+1)= m> 1. Then m is a common factor of n and n+1 and we must have n= mk and n+1= mp for integers k and p. Then n+ 1= mk+ 1= mp so 1= mp-mk= m(p- k). But, since the only factor of 1 is 1 itself, we must have both m and p-k equal to 1 and m= 1 contradicts m> 1.

4. Originally Posted by dori1123
My answer is yes, both $\displaystyle (n,n+1)=1$ and $\displaystyle (n, n^2+1)=1$. But is there a way to show these are true?
If $\displaystyle d$ divides $\displaystyle x$ and $\displaystyle y$ the it divides $\displaystyle ax+by$ for any $\displaystyle a,b\in\mathbb{Z}$ - it is easy to see why, just write $\displaystyle x=k\cdot d$ for some k in $\displaystyle \mathbb{Z}$, and similary for y, then factor out the $\displaystyle d$'s in the sum!-

For for example, if $\displaystyle d$ divides $\displaystyle n$ and $\displaystyle (n^2+1)$ then it divides $\displaystyle (-n)\cdot n + (1)\cdot (n^2+1)=1$

Similarly if a number divides both $\displaystyle n$ and $\displaystyle n+1$ then it divides their difference.