bump....

(Can someone fix the LaTeX for me please, I'm not allowed) According to Bézout's identity, the greatest common divisor of a and b is a linear combination of them: gcd(a,b)=ax+by Let x, y, x', y' and z' be integers such that: gcd(a+kb, c)=(a+kb)x+cy gcd(a, b, c)=ax'+by'+cz' Then: gcd(a+kb, c)=gcd(a, b, c) (a+kb)x+cy=ax'+by'+cz' k=\frac{ax'+by'+cz'-ax-cy}{bx} This means we can assure that there exists an integer k which satisfies the proposition.

How are we sure that the fraction can be an integer?

pretela wrote: According to Bézout's identity, the greatest common divisor of $a$ and $b$ is a linear combination of them: $gcd(a, b)=ax+by$ Let $x, y, x', y' and z'$ be integers such that: $gcd(a+kb, c)=(a+kb)x+cy$ $gcd(a, b, c)=ax'+by'+cz'$ Then: $gcd(a+kb, c)=gcd(a, b, c)$ $(a+kb)x+cy=ax'+by'+cz'$ $k=\frac{ax'+by'+cz'-ax-cy}{bx}$ This means we can assure that there exists an integer $k$ which satisfies the proposition.

(Can someone fix the LaTeX for me please, I'm not allowed) Yes, you are right. This solution don't assure that k is always an integer k=\frac{ax'+by'+cz'-ax-cy}{bx}=(\underbrace{\frac{ax'+by'+cz'}{ax+cy+kbc}}_{integer}-\underbrace{\frac{ax+cy}{ax+cy+kbc}}_{?})\underbrace{\frac{ax+cy+kbx}{bx}}_{?} Actually, I did not pay enough attention to the fact that k must be integer when I wrote this. I'm sorry :/

It's fine, but you can use a different approach

Hint

pretela wrote: (Can someone fix the LaTeX for me please, I'm not allowed) Yes, you are right. This solution don't assure that k is always an integer $k=\frac{ax'+by'+cz'-ax-cy}{bx}=(\underbrace{\frac{ax'+by'+cz'}{ax+cy+kbc}}_{integer}-\underbrace{\frac{ax+cy}{ax+cy+kbc}}_{?})\underbrace{\frac{ax+cy+kbx}{bx}}_{?}$ Actually, I did not pay enough attention to the fact that k must be integer when I wrote this. I'm sorry :/

bump this