Results 1 to 3 of 3

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

  1. #1
    Member
    Joined
    Sep 2008
    Posts
    166

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

    show that the integers $\displaystyle 3n+1$ and $\displaystyle 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,410
    Thanks
    1
    Let $\displaystyle d = \gcd (3n+1, \ 5n + 2 )$ and assume $\displaystyle d>1$.

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

    which means: $\displaystyle 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