Is it true that $\gcd(a,b)$ = $\gcd(a,bk)$ for some integer k?

Question

Does it always hold true that $\gcd(a,b)$ = $\gcd(a,bk)$ for some integer k?

I can't necessarily find a counter example.

Answer 1

We have that $$\gcd(a,bk)=\gcd(a,b)$$ if and only if $$\gcd\left(\frac{a}{\gcd(a,b)},k\right)=1.\tag{1}$$

Proof:

(I tend to prefer Bézout identity proofs.)

($\Rightarrow$) If $\gcd(a,b)=\gcd(a,bk),$ then we can solve $ax+(bk)y=\gcd(a,b).$ Diviing by $\gcd(a,b)$ gives us: $$\frac{a}{\gcd(a,b)}x+k\left(y\frac{b}{\gcd(a,b)}\right)=1$$ so $$\gcd\left(\frac{a}{\gcd(a,b)},k\right)=1.$$

($\Leftarrow$) On the other hand, if (1) is true we can solve $$\frac{a}{\gcd(a,b)}X+kY=1.$$ We can also solve $au+by=\gcd(a,b).$ So we have that $$\begin{align}\gcd(a,b)&=aX+k\gcd(a,b)Y\\ &=aX+k(au+bv)Y\\ &=a(x+ku)+bk(vY) \end{align}$$

So $\gcd(a,bk)\mid \gcd(a,b)$. But we trivially have the reverse, so $\gcd(a,b)=\gcd(a,bk).$

---

We can always find $k$ satisfying $(1).$

Answer 2

It's true. Simply let $k$ be any prime that doesn't divide either $a$ or $b$.

Answer 3

Take $k=1$, or take $p$ prime such $p \not|\ a$ and $p \not|\ b$.

Answer 4

Note that: $$\gcd(a,b)=c=\gcd(a,bk) \iff \\ \begin{cases}a=cx,\\ b=cy,\\ \gcd(x,y)=1\end{cases} \quad \text{and} \quad \begin{cases} a=cx, \\ b=cyk,\\ \gcd(x,y)=1, \\\gcd(x,k)=1 \iff \gcd(\frac ac,k)=\gcd(\frac{a}{\gcd(a,b)},k)=1\end{cases}.$$

Answer 5

For some integer yes: it is always true for $k = 1$.

But unless $a|b$, it is also false for some integer: it is never true for $k = \frac a{\gcd(b,a)}>1$. ($bk = b\frac a{\gcd(b,a)} = \frac b{\gcd(b,a)}a$ so $\gcd(a,bk) = a$.)

(Example $\gcd (150,70) = 10$ but $\gcd(150,70*5) = 50$).

...

The real question is which integers is it true for.

Let $\gcd(a,b) = d$ and $a = a'd; b= b'd$. Then $a'$ and $b'$ are relatively prime.

Claim: $\gcd(a,bk) = \gcd(a,b)=d$ if and only if $\gcd(a',k)=\gcd(\frac a{\gcd(a,b)},k) = 1$.

Pf: If $\gcd(a',k)=m$ and $a'=a^!m; k = k'm$ and $a^!$ and $k'$ are relatively prime, so $\gcd(a^!,k'b') = 1$. Then $\gcd(a,bk) = \gcd(a^!md,b'dmk')=dm\gcd(a^!,b'k')= dm*1=dm$. And $dm=d \iff m =1$.