# Math Help - coprime

1. ## coprime

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

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

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

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

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

we will have $(n^2 + 1 )- (n ) = n + (n-1)^2 = [(n-1)+1] + (n-1)^2$ which doesnt' contain any factor , so $( 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 $(n,n+1)=1$ and $(n, n^2+1)=1$. But is there a way to show these are true?
If $d$ divides $x$ and $y$ the it divides $ax+by$ for any $a,b\in\mathbb{Z}$ - it is easy to see why, just write $x=k\cdot d$ for some k in $\mathbb{Z}$, and similary for y, then factor out the $d$'s in the sum!-

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

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