1
$\begingroup$

Show that if $a$ and $b$ are relatively prime integers then $gcd(a+kb, b+ka)$ divides $k^2-1$

I am trying to two linear combination of $a+kb$ and $b+ka$

but can't write to as linear combination can you one help...

thank you....

$\endgroup$

2 Answers 2

2
$\begingroup$

If $d,$divides both $a+bk,ak+b$

$d$ must divide $k(a+bk)-(ak+b)=b(k^2-1)$

and $k(ak+b)-(a+bk)=a(k^2-1)$

The idea is to eliminate $a,b$ one by one.

So, $d$ must divide $(a(k^2-1),b(k^2-1))=(k^2-1)(a,b)$

$\endgroup$
0
2
$\begingroup$

Since $a,b$ are relatively prime integers we have $$ax+by=1$$ for some integers $x,y$. Then any common factor of $a+kb$ and $b+ka$ is also a factor of $$(a+kb)(ky-x)+(b+ka)(kx-y)=k^2-1\ .$$

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .