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

• April 12th 2011, 02:32 PM
magus
(10n+3,5n+2)=1
Prove that for any number $n$ $(10n+3,5n+2)=1$

The way I approached it was by linear combinations

$d=m(10n+3)+q(5n+2)$
$=10mn+3m+5qn+2q$
$=5n(2m+q)+3m+2q$

At this point I get stuck. I kind of wish there were some way of saying since it was a linear combination of 5,3, and 2 the gcd of the three must be one.
• April 12th 2011, 03:07 PM
Moo
Hello,

Just note that since 10=5x2, you may want to have a look at (10n+3)-2(5n+2) :) that's a common method : find a linear combination that cancels n and the result will be a multiple of the gcd!
• April 12th 2011, 04:41 PM
magus
Thank you so much. I didn't think of just picking a combination. I always thought I needed to deal with them in the abstract *wavy hands*