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

**magus** · Apr 12th 2011, 02:32 PM

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.

**Moo** · Apr 12th 2011, 03:07 PM

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!

**magus** · Apr 12th 2011, 04:41 PM

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*

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

LinkBack

Thread Tools

Display

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

Search Tags