Results 1 to 3 of 3

Math Help - (3n+1, 5n+2)=1

  1. #1
    Member
    Joined
    Sep 2008
    Posts
    166

    (3n+1, 5n+2)=1

    show that the integers 3n+1 and 5n+2, n \in \mathbb{N}, are relatively prime.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    Let d = \gcd (3n+1, \ 5n + 2 ) and assume d>1.

    This implies: d \mid 5(3n+1) and d \mid 3(5n+2) \Big( Recall: if d \mid a then d \mid ca for all c \in \mathbb{Z} \Big)

    which means: d \ \ \Big| \ \Big[  3(5n+2) - 5(3n+1) \Big]

    and you should arrive at a contradiction.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    May 2009
    Posts
    36
    Write gcd as a linear combination we have:

    (3n+1)x+(5n+2)y=gcd(3n+1,5n+2) if, and only if x,y are naturals and form the smaller combination.

    let x=-5 and y=3, then:

    gcd(3n+1,5n+2)=-15n-5+15n+6=1
    Follow Math Help Forum on Facebook and Google+


/mathhelpforum @mathhelpforum