Results 1 to 4 of 4

Math Help - coprime

  1. #1
    Member
    Joined
    Sep 2008
    Posts
    166

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jan 2009
    Posts
    715
    Quote Originally Posted by dori1123 View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,541
    Thanks
    1394
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Quote Originally Posted by dori1123 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Coprime elements
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: January 14th 2011, 04:00 AM
  2. [SOLVED] Coprime Polynomials
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: January 2nd 2011, 02:39 PM
  3. coprime question!
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 20th 2010, 10:15 AM
  4. Coprime
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 19th 2009, 10:32 AM
  5. Coprime polynomials
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: November 24th 2008, 01:48 AM

Search Tags


/mathhelpforum @mathhelpforum