Proving $\gcd \left(\frac{a}{\gcd (a,b)},\frac{b}{\gcd (a,b)}\right)=1$

Question

How would you go about proving that $$\gcd \left(\frac{a}{\gcd (a,b)},\frac{b}{\gcd (a,b)}\right)=1$$

for any two integers $a$ and $b$?

Intuitively it is true because when you divide $a$ and $b$ by $\gcd(a,b)$ you cancel out any common factors between them resulting in them becoming coprime. However, how would you prove this rigorously and mathematically?

Answer 1

Very simply it can be done like this: $\gcd(a,b)=d$.

Now we ask can: $\gcd(\frac{a}{d},\frac{b}{d})=e$ for $e>1$?

Well, this implies $e\mid\frac{a}{d},e\mid\frac{b}{d} \Rightarrow em=\frac{a}{d}, en=\frac{b}{d} \Rightarrow dem=a,den=b \Rightarrow de$ is a common divisor of $a,b$ which is greater than $d$, thus a contradiction as $d$ by definition was supposed as the $\gcd$. Hence, $e=1$.

Answer 2

Let $a,b$ have the following prime factorisations:

$$a= \prod_{n=1}^\infty p_n^{\alpha_n} ,b=\prod_{n=1}^\infty p_n^{\beta _n}.$$

(Here $(p_n)$ is the ascending sequence of prime numbers). We then have $$\gcd(a,b)=\prod_{n=1}^\infty p_n^{\min(\alpha_n,\beta_n)}, $$ and consequently $$\frac{a}{\gcd(a,b)}=\prod_{n=1}^\infty p_n^{\alpha_n-\min(\alpha_n,\beta_n)},\frac{b}{\gcd(a,b)}=\prod_{n=1}^\infty p_n^{\beta_n-\min(\alpha_n,\beta_n)}. $$ Now ask yourself, could it be that one of the factors $p_n$ could have a strictly positive exponent, in both of the last products simultaneously?

Answer 3

Assume WLOG that $a, b \geq 1$. Let $$m = \dfrac{a}{\gcd(a,b)},\quad n = \dfrac{b}{\gcd(a,b)},\quad\text{and}\quad c = \gcd(m,n).$$Then $$c \mid m,\quad\text{and}\quad c\mid n.$$This means: $$(c\cdot \gcd(a,b)) \mid a,\quad\text{and}\quad(c\cdot \gcd(a,b)) \mid b.$$ So $$(c\cdot \gcd(a,b)) \mid \gcd(a,b).$$ But $\gcd(a,b) \mid (c\cdot \gcd(a,b))$. Thus: $c\cdot \gcd(a,b) = \gcd(a,b)$, and this means $$c = 1.$$

Answer 4

Let $d=\gcd(a,b)$. Let $a=md$ and $b=nd$. If some $k\gt 1$ divides $m$ and $n$, then $kd$ divides $a$ and $kd$ divides $b$, contradicting the fact that $d$ is the greatest common divisor of $a$ and $b$.

Answer 5

Every other answer is doing part of this, but since you asked for rigorous, here is rigorous:

Let $A$ be the multiset of prime factors of a, $B$ be the multiset of prime factors of $b$. The multiset of prime factors of $1$ is the empty set.

$$\text{GCD}\left(\frac{a}{\text{GCD}(a,b)}, \frac{b}{\text{GCD}(a,b)}\right) = 1$$

Standard conversion to multisets:

$$\bigg(A - (A\cap B)\bigg) \cap \bigg(B - (A \cap B)\bigg) = \{\}$$

Standard conversion to Boolean Algebra ($x \in A$ becomes $A$):

$$\bigg(A \land \lnot (A \land B)\bigg) \land \bigg(B \land \lnot (A \land B)\bigg) = \bot$$

Standard reduction (or you could use truth table): $$\bigg(A \land (\lnot A \lor \lnot B)\bigg) \land \bigg(B \land (\lnot A \lor \lnot B)\bigg) = \bot$$

$$\bigg(A \land \lnot B\bigg) \land \bigg(B \land \lnot A\bigg) = \bot$$ $$\bot = \bot$$ $$\top$$

Answer 6

This is a special case of the GCD distributive law ($4$ proofs of it are below). Namely

$$ \color{#c00}{\bf c} = (a,b) = (a/c,b/c)\color{#c00}{\bf \,c}\overset{\rm\large cancel\ \color{#c00}{\bf c}}\Longrightarrow 1 = (a/c,b/c)\qquad\qquad$$

Or, presented more concisely it is $\ (a/c,b/c) = (a,b)/c = 1$

---

Below are sketches of four proofs of the gcd Distributive Law $\rm\:(ax,bx) = (a,b)x\:$ using various approaches: Bezout's identity, the universal gcd property, unique factorization, and induction.

First we show that the gcd distributive law follows immediately from the fact that, by Bezout, the gcd may be specified by linear equations. Distributivity follows because such linear equations are preserved by scalings. Namely, for naturals $\rm\:a,b,c,x \ne 0$

$\rm\qquad\qquad \phantom{ \iff }\ \ \ \:\! c = (a,b) $

$\rm\qquad\qquad \iff\ \: c\:\ |\ \:a,\:b\ \ \ \ \ \ \&\ \ \ \ c\ =\ na\: +\: kb,\ \ \ $ some $\rm\:n,k\in \mathbb Z$

$\rm\qquad\qquad \iff\ cx\ |\ ax,bx\ \ \ \&\ \ \ cx = nax + kbx,\ \,$ some $\rm\:n,k\in \mathbb Z$

$\rm\qquad\qquad { \iff }\ \ cx = (ax,bx) $

The reader familiar with ideals will note that these equivalences are captured more concisely in the distributive law for ideal multiplication $\rm\:(a,b)(x) = (ax,bx),\:$ when interpreted in a PID or Bezout domain, where the ideal $\rm\:(a,b) = (c)\iff c = gcd(a,b)$

---

Alternatively, more generally, in any integral domain $\rm\:D\:$ we have

Theorem $\rm\ \ (a,b)\ =\ (ax,bx)/x\ \ $ if $\rm\ (ax,bx)\ $ exists in $\rm\:D.$

Proof $\rm\quad\: c\ |\ a,b \iff cx\ |\ ax,bx \iff cx\ |\ (ax,bx) \iff c\ |\ (ax,bx)/x\ \ \ $ QED

The above proof uses the universal definitions of GCD, LCM, which often served to simplify proofs, e.g. see this proof of the GCD * LCM law.

---

Alternatively, comparing powers of primes in unique factorizations, it reduces to the following $$\begin{eqnarray} \min(a+x,\,b+x) &\,=\,& \min(a,b) + x\\ \rm expt\ analog\ of\ \ \ \gcd(a \,* x,\,b \,* x)&=&\rm \gcd(a,b)\,*x\end{eqnarray}\qquad\qquad\ \ $$

The proof is precisely the same as the prior proof, replacing gcd by min, and divides by $\,\le,\,$ and using the universal property of min instead of that of gcd, i.e.

$$\begin{eqnarray} {\rm employing}\quad\ c\le a,b&\iff& c\le \min(a,b)\\ \rm the\ analog\ of\quad\ c\ \, |\, \ a,b&\iff&\rm c\ \,|\,\ \gcd(a,b) \end{eqnarray}$$

Then the above proof translates as below, $\ $ with $\,\ m(x,y) := {\rm min}(x,y)$

$c \le a,b \!\iff\!c\!+\!x \le a\!+\!x,b\!+\!x\!$ $\!\iff\! c\!+\!x \le m(a\!+\!x,b\!+\!x)\!$ $\!\iff\!\! c \le m(a\!+\!x,b\!+\!x)\!-\!x$

---

Theorem $\ \ $ If $\ a,b,x\ $ are positive naturals then $\ (ax,bx) = (a,b)x $

Proof $\ $ By induction on $\color{#0a0}{{\rm size}:= a\!+b}.\,$ If $\,a=b,\,$ then it is true since then both sides $= ax.\,$ Else $\,a\neq b;\,$ wlog, by symmetry, $\,a > b\,$ so $\,(ax,bx) = (ax\!-\!bx,bx) = \color{}{((a\!-\!b)x,bx)}\,$ which has smaller $\rm\color{#0a0}{size}$ $\,(a\!-\!b) + b = a < \color{#0a0}{a\!+b},\,$ therefore $\,((a\!-\!b)x,bx)\!\underset{\rm induct}=\! (a\!-\!b,b)x = (a,b)x$.

Answer 7

Suppose $d \mid \dfrac a{\gcd(a,b)}$ and $d\mid \dfrac b{\gcd(a,b)}$.

Then $nd = \dfrac a {\gcd(a,b)}$ and $md\mid \dfrac b {\gcd(a,b)}$.

So $nd\cdot\gcd(a,b) = a$ and $md\cdot\gcd(a,b) = b$.

So $d\cdot\gcd(a,b)$ is a common divisor of $a$ and $b$.

Since $\gcd(a,b)$, is the greatest of those, we must have $d\not>1$.

Answer 8

A Bezout-centric approach. Let $d=\text{gcd}(a,b)$. Then, there are integers $m$ and $n$ such that $d=ma+nb$. But then $m$ and $n$ are also integers such that $$ 1=m\left(\frac{a}{d}\right)+n\left(\frac{b}{d}\right) $$ so $\text{gcd}(\frac{a}{d},\frac{b}{d})=1$.