Monday, November 2, 2015

elementary number theory - Let $a,m,n in mathbf{N}$. Show that if $gcd(m,n)=1$, then $gcd(a,mn)=gcd(a,m)cdotgcd(a,n)$.




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?


Answer



$\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)$$


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...