If $(a,b) = 1$, then $(n, ab) = 1 \iff (n,a) = 1 = (n,b)$. How to prove it?

84 Views Asked by At

I'm having some trouble proving the question above, most because i'm getting a proof that works even if $(a,b) \neq 1$ and i just can't find my mistake.

Proof: if $(n, ab) = 1$, $\exists x$, $y \in \mathbb{Z}$ such that $x\cdot n + y\cdot ab = 1$, but this means that $x\cdot n + ya \cdot b = 1$ and $x\cdot n + yb\cdot a = 1$ and so $(n,a) = 1$ and $(n,b) = 1$. Now, if $(n,a) = 1 = (n,b)$, $\exists x'$, $x''$, $y'$, $y'' \in \mathbb{Z}$ such that $x'\cdot n + y'\cdot a = 1$ and $x''\cdot n + y''\cdot b = 1 \Rightarrow x'\cdot x''\cdot n^2 + x'\cdot y''\cdot n\cdot b + x''\cdot y'\cdot n\cdot a + y'\cdot y''\cdot a\cdot b = 1 \Rightarrow n\cdot (x'x''n + x'y''b + x''y'a) + y'y''\cdot ab = 1 \Rightarrow (n,ab) = 1$

Note that i did not request that (a,b) = 1 at any time.

1

There are 1 best solutions below

0
On

An alternate proof for the second part $$\gcd(n,a) = 1 \implies \gcd(n,ab) = \gcd(n,b)$$

$\begin{align}\gcd(n,ab)&=\gcd(\gcd(n,nb),ab)\\&=\gcd(n,ab,nb)\\ &=\gcd(n,\gcd(ab,nb))\\&=\gcd(n,b\gcd(a,n))\\ &=\gcd(n,b\times 1)\\&=\gcd(n,b)\\&=1\end{align}$