show that the integers and , are relatively prime.

Follow Math Help Forum on Facebook and Google+

Let and assume . This implies: and Recall: if then for all which means: and you should arrive at a contradiction.

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