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

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

show that the integers $3n+1$ and $5n+2, n \in \mathbb{N}$, are relatively prime.

2. 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.

3. 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