Results 1 to 7 of 7

Math Help - Relatively Prime

  1. #1
    Senior Member Sampras's Avatar
    Joined
    May 2009
    Posts
    301

    Relatively Prime

    Show that  5n+3 and  7n+4 are relatively prime for all  n .

    So we can find integers  x and  y such that  (5n+3)x + (7n+4)y = 1 for all  n . But I don't think this would be a very efficient way of doing this because you have to check it for all  n .

    Maybe we could to the following: Show that  7n+4 has a multiplicative inverse modulo  5n+3 ? So show that there exists an integer  y such that  (7n+4)y \equiv 1 (\text{mod} \ (5n+3)) ?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by Sampras View Post
    Show that  5n+3 and  7n+4 are relatively prime for all  n .

    So we can find integers  x and  y such that  (5n+3)x + (7n+4)y = 1 for all  n . But I don't think this would be a very efficient way of doing this because you have to check it for all  n .

    Maybe we could to the following: Show that  7n+4 has a multiplicative inverse modulo  5n+3 ? So show that there exists an integer  y such that  (7n+4)y \equiv 1 (\text{mod} \ (5n+3)) ?
    Have you come across the Euclidean algorithm?

    By hand, it is possible, but generally quite tedious (methinks this example, however, is rigged to work...). You want to get rid of your 5n and 7n with your choices of x and y, so can you perhaps think of a way of choosing them such that 5n*x+7n*y = 0? Then plugging in these x and y we, mircaulously, get our answer!...
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member Sampras's Avatar
    Joined
    May 2009
    Posts
    301
     x = 5 , and  y = -5 .
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Quote Originally Posted by Sampras View Post
     x = 5 , and  y = -5 .
    Uh ?

    5(5)+7(-5)=-10\neq 0

    5n*x+7n*y = 0
    Factor by n : n(5x+7y)=0
    Now fix x, for example x=7... can you find a value for y such that it works ?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Sampras View Post
    Show that  5n+3 and  7n+4 are relatively prime for all  n .

    So we can find integers  x and  y such that  (5n+3)x + (7n+4)y = 1 for all  n . But I don't think this would be a very efficient way of doing this because you have to check it for all  n .

    Maybe we could to the following: Show that  7n+4 has a multiplicative inverse modulo  5n+3 ? So show that there exists an integer  y such that  (7n+4)y \equiv 1 (\text{mod} \ (5n+3)) ?
    Let d be a divisor then 5n\equiv -3(\bmod d) and 7n\equiv -4(\bmod d). Therefore, 35n\equiv -21(\bmod d) and 35n\equiv -20(\bmod d) so -21\equiv -20(\bmod d) which means d|1.
    Thus, (5n+3,7n+4)=1 for all n.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member Sampras's Avatar
    Joined
    May 2009
    Posts
    301
    Quote Originally Posted by Moo View Post
    Uh ?

    5(5)+7(-5)=-10\neq 0


    Factor by n : n(5x+7y)=0
    Now fix x, for example x=7... can you find a value for y such that it works ?
     n(5x+7y) = 0 . Fix  x = 7 . Then  n(35+7y) = 0 . So  y = -35/7 = - 5 . Or in general,  y = 5x_{0}/7 .
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member TheAbstractionist's Avatar
    Joined
    Apr 2009
    Posts
    328
    Thanks
    1
    Quote Originally Posted by Sampras View Post
     x = \color{red}7\color{black} , and  y = -5 .
    Fixed your typo. That should work now.

    (5n+3)(7)+(7n+4)(-5)\ =\ 1
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: October 22nd 2011, 12:37 PM
  2. Replies: 1
    Last Post: June 19th 2011, 12:56 PM
  3. Replies: 3
    Last Post: February 17th 2011, 07:51 AM
  4. why is a prime squared + itself + 1 also a prime
    Posted in the Number Theory Forum
    Replies: 11
    Last Post: November 19th 2010, 07:03 PM
  5. Replies: 6
    Last Post: August 27th 2010, 11:44 PM

Search Tags


/mathhelpforum @mathhelpforum