# Let $a,m,n \in \mathbf{N}$. Show that if $\gcd(m,n)=1$, then $\gcd(a,mn)=\gcd(a,m)\cdot\gcd(a,n)$. [duplicate]

Let $a,m,n\in\mathbf{N}$. Show that if $\gcd(m,n)=1$, then $\gcd(a,mn)=\gcd(a,m)\cdot\gcd(a,n)$.

Proof:

Let $u,v\in\mathbf{Z}$ such that $\gcd(m,n)=um+vn=1$. Let $b,c\in\mathbf{Z}$ such that $\gcd(m,a)=ab+cm$. Let $d,e\in\mathbf{Z}$ such that $\gcd(a,n)=ad+en$.

So $\gcd(a,m)\cdot\gcd(a,n)=a^2bd+cmen+aben+emad$.

Where do I go from here?

## marked as duplicate by Bill Dubuque elementary-number-theory StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Apr 2 '17 at 15:03

$\gcd(a,m)\cdot \gcd(a,n) = a(abd+ben+emd)+(mn)(ce) \ge \gcd(a,mn)$

Say $\gcd(\gcd(a,m),\gcd(a,n)) = p$ where $p>1$. Then $p|gcd(a,m)$ and $p|gcd(a,n)$. Which means $p|m$ and $p|n$. So $p$ is a common divisor of $m$ and $n$. $\gcd(m,n) \ge p$. But this is impossible since $\gcd(m,n)=1$ and $p>1$. Thus, $p=1$

If $\gcd(a,m) = x$, this means $x|a$ and $x|m$. If $x|m$, then $x|mn$. Thus $x$ is a common divisor of $a$ and $mn$. $x|\gcd(a,mn)$ If $\gcd(a,n) = y$, this means $y|a$ and $y|n$. If $y|n$, then $y|mn$. Thus $y$ is a common divisor of $a$ and $mn$. $y|\gcd(a,mn)$ Because $\gcd(x,y) = 1, xy|\gcd(a,mn)$ So $\gcd(a,m) \cdot \gcd(a,n) \le \gcd(a,mn)$

Therefore, $$\gcd(a,m) \cdot \gcd(a,n) = \gcd(a,mn)$$

• I understand how you conclude that $\gcd(a,m) \cdot \gcd(a,n) \leq \gcd(a,mn)$, but how do you jump from that to $\gcd(a,m) \cdot \gcd(a,n) = \gcd(a,mn)$? – SBS Oct 19 '16 at 13:40

You can also try looking at gcd's in terms of the prime factorizations of the integers, from which the desired result follows readily.

If you know some ring theory: The greatest common divisor of $r,s$ is the smallest positive integer in the ideal $(r,s) := \{ kr+ls \ | \ k,l\in \mathbb{Z} \}.$

We have $$(a,m)(a,n) = (a^2,am,an,mn) = (a,mn)$$

where the last equal followed from $(m,n)=1.$ Reading off the least positive integer from both sides gives the result.