coprime

**dori1123** · September 12th 2009, 05:28 PM

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?

**simplependulum** · September 12th 2009, 09:46 PM

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$

**HallsofIvy** · September 13th 2009, 04:19 AM

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.

**PaulRS** · September 13th 2009, 04:45 AM

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.

Thread: coprime

LinkBack

Thread Tools

Display

coprime

Similar Math Help Forum Discussions

Coprime elements

[SOLVED] Coprime Polynomials

coprime question!

Coprime

Coprime polynomials

Search Tags