How to prove that $\gcd(a,m) \le \gcd(a,mn)$ for any integer n

Question

I'm trying to show that $\gcd(a,m) \le \gcd(a,mn)$ for any integer n

Taking a classical algebra course and can not seem to figure out how to prove this. I know about Bezout's Identity but don't know how I could apply it to this problem.

Answer 1

This should follow immediately from the fact that if $d|(a,m)$ then $d|(a,mn)$.

Answer 2

The set of common divisors of divisors of $a$ and $m$ is contained in the set of common divisors of $a$ and $mn$

Answer 3

Let me give you a new perspective on GCD.

Expand a number in terms of it's prime factors and their powers... ${p_{1}}^{\alpha}.{p_{2}}^{\beta}{\dots}$ The gcd of two numbers is the intersection of these two sets.

So, let's assume that the $\gcd(a, mn)$is less than the $\gcd(a, m)$. But, all the common factor in between a and m are also there in between a and mn. The only way the $\gcd of (a, mn)$ can be less than $\gcd(a, m)$ is if some of the factors were reduced. But multiplication with a natural number never does this. We conclude that are assumtion is wrong and that the $\gcd(a, mn)$ is greater than or equal to $\gcd(a, m)$ observng that equality holds when a and n are coprime or when $a=m$

Answer 4

Let $d:=\gcd(a,m)$. Then $d|a$ and $d|m$, meaning that there exist $a',m'\in\mathbb{Z}$ such that $a=da'$, $m=dm'$. Then $mn=dm'n$, so by definition $d|mn$. Hence $d|a$ and $d|mn$ and, since $\gcd(a,mn)$ is the greatest number with this property, we get that $d|\gcd(a,mn)$, so in particular $d\leq\gcd(a,mn)$. Note that we get more: we actually get that $\gcd(a,m)$ is a divisor of $\gcd(a,mn)$.