(a) Prove that if $am + bn = c$, then $hcf(m,n)|c$
(b) Prove that if $am + bn = 1$, then $hcf(m,(n) = 1$
(c) Prove that $m/hcf(m,n)$ and $n/hcf(m,n)$ are coprime.
Question on recent review homework related to coprimes. I know that for a and b to be coprime means $hcf(a,b) = 1$. Further, integers $s$ and $t$ exist such that $as + bt = 1$.
With this information, should I be able to answer these? Please help with getting started.
On
There are successive immediate corollaries. Let $\ d = {\rm hcf}(m,n) = \gcd(m,n)$
$(a)\ \ $ By definition $\,d\,$ is a common divisor of $\,m,n\,$ so $\,d\mid m,n\,\Rightarrow\,d\mid am\!+\!bn\,$ for all $\,a,b\in\Bbb Z.$
$(b)\ \ $ Special case $\, c = 1\,$ of $\,(a).$ Similarly $\,\gcd(a,b) = 1.$
$(c)\ \ $ By Bezout $\, am+bn = d\ $ so $\ (a/d)m + (b/d) n = 1.\ $ Now apply $\,(b).$
I will use the notation $\gcd$ instead of $\text{hcf}$, since $\gcd$ is considered more standard. Further, let $\gcd(m,n) = d$. By definition of $\gcd$, we have $m=dm_1$ and $n=dn_1$, where $m_1, n_1 \in \mathbb{Z}$.
$1$. Hence, $c=am+bn = adm_1 + bdn_1 = d(am_1 + bn_1)$. This means $d \vert c$.
$2$. This follows immediately from part $1$, since we have $d \vert 1$ and since $d>0$, we conclude that $d=\gcd(m,n)=1$.
$3$. We need to prove that $\dfrac{m}d$ (i.e., $m_1$) and $\dfrac{n}d$ (i.e., $n_1$) are co-prime. Let $k \in \mathbb{Z}^+$ be the largest common factor of $m_1$ and $n_1$, i.e., $m_1 = km_2$ and $n_1 = kn_2$, where $m_2,n_2 \in \mathbb{Z}$. We then have $m=dkm_2$ and $n=dkn_2$. Hence, $dk$ is a common factor of $m$ and $n$. Since $d$ is the $\gcd$ of $m$ and $n$, we have $$dk \leq d \implies k \leq 1 \implies k = 1$$ Hence, $\dfrac{m}d$ (i.e., $m_1$) and $\dfrac{n}d$ (i.e., $n_1$) are co-prime