Suppose that K is an integer between 600000 and 800000 such that gcd(k,271)=gcd(k, 2010)+70.

Find K.

I know the answer should be K=708123 (I tested this in a C program with a for loop), but what are the steps I need to show for this question?

Printable View

- Oct 21st 2010, 12:07 PMSMRFind K in an equation like gcd(K,a)=gcd(K,b)+some constant
Suppose that K is an integer between 600000 and 800000 such that gcd(k,271)=gcd(k, 2010)+70.

Find K.

I know the answer should be K=708123 (I tested this in a C program with a for loop), but what are the steps I need to show for this question? - Oct 21st 2010, 12:15 PMAlso sprach Zarathustra
gcd(a,b)=ax+by

- Oct 21st 2010, 12:24 PMSMR
Okay, so if I write down

gcd(k, 271) = kx+ 271y, how can I proceed from there?