16
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ By rigorous you mean finding $m,n\in \mathbb{Z}$ scuh that $**m+**n=1$? $\endgroup$
    – user87543
    Commented Apr 14, 2014 at 5:47
  • 1
    $\begingroup$ Related: math.stackexchange.com/questions/202397 $\endgroup$ Commented Feb 21, 2015 at 16:32
  • $\begingroup$ Hint $\ 1<d\mid a,b \Rightarrow cd\mid ca,cb,\,$ so $\,c\,$ is not a greatest common divisor of $\, ca,cb\ \ $ $\endgroup$ Commented Mar 13, 2023 at 23:38

9 Answers 9

9
$\begingroup$

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$.

$\endgroup$
5
  • $\begingroup$ I apologize, I was posting the exact same solution at the time, so I will upvote this. $\endgroup$
    – Mr.Fry
    Commented Apr 14, 2014 at 6:08
  • $\begingroup$ No problem, yes, exactly the same idea. So if upvoting is appropriate for one, it is appropriate for the other. $\endgroup$ Commented Apr 14, 2014 at 6:20
  • 1
    $\begingroup$ Is it also possible to prove that $$\gcd \left(\frac{a}{\gcd (a,b)},b\right)=1$$ in the same manner? I let $$d=\gcd (a,b)$$ and then $$a=\text{md}$$ and $$b=\text{nd}$$ and then let $$\gcd (m,\text{nd})=e$$ but I am stuck on how to proceed. $\endgroup$
    – 1110101001
    Commented Apr 14, 2014 at 18:21
  • 2
    $\begingroup$ No, because it is not true. Let $a=4$ and $b=2$. The gcd is $2$. Thus $\frac{a}{\gcd(a,b)}=2$, and this is not relatively prime to $2$. This is the simplest counterexample. There are many more. $\endgroup$ Commented Apr 14, 2014 at 18:35
  • $\begingroup$ For a direct proof (instead of by contradiction), see DeepSea's answer. $\endgroup$ Commented Jul 23, 2023 at 16:15
6
$\begingroup$

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$.

$\endgroup$
4
  • 1
    $\begingroup$ don't frame this as a contradiction. "hence e = 1". Much better conclusion. $\endgroup$
    – djechlin
    Commented Nov 30, 2014 at 5:07
  • 2
    $\begingroup$ Let's not argue semantics. And this post is very old and correct as well. $\endgroup$
    – Mr.Fry
    Commented Nov 30, 2014 at 7:22
  • 2
    $\begingroup$ This is all true. It's better not to needlessly say "we assume for the sake of contradiction..." and conclude with "a contradiction!" when none of that was necessary. The proofs are cleaner and avoids unnecessarily mental baggage tracking extra false hypotheses that are never invoked. $\endgroup$
    – djechlin
    Commented Nov 30, 2014 at 14:16
  • $\begingroup$ I fully agree with djechlin. For a direct proof (instead of by contradiction), see DeepSea's answer. $\endgroup$ Commented Jul 23, 2023 at 16:16
5
$\begingroup$

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$.

$\endgroup$
5
  • $\begingroup$ In your second proof how do you prove the mentioned theorem? Specifically where is it shown that $(a, b) = (ax,bx)/x$? $\endgroup$ Commented Sep 24, 2019 at 20:57
  • $\begingroup$ @Michael The proof shows $\, c\mid (a,b)\iff c\mid (ax,bx)/x =:d\, $ so $\, d\mid (a,b)\mid d\,$ so they are equal up to a unit factor (so they are equal in $\Bbb Z\,$ if normalized to be positive as usual). $\endgroup$ Commented Sep 24, 2019 at 22:06
  • $\begingroup$ I don't understand this. How do you conclude that $d$ divides $(a,b)$? $\endgroup$ Commented Sep 25, 2019 at 6:36
  • $\begingroup$ Is $c = (a,b)$ in the second proof as well? $\endgroup$ Commented Sep 25, 2019 at 7:27
  • $\begingroup$ @Michael We use $\,m = n\,$ if they have the same divisors: if for all $\,c\,$ we have $\,c\mid m\iff c\mid n\,$ then taking $\,c=m\,$ implies $\,m\mid n,\,$ and taking $\,c=n\,$ impies $\,n\mid m.\,$ Thus $\,|m| \le |n| \le |m|\,$ so $\,|m| = |n|,\,$ so $\,m=n\,$ being both $> 0\,$ (or $\,m$ & $n$ are associates in more general domains). $\endgroup$ Commented Sep 25, 2019 at 12:49
3
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ eek, unique prime factorization? so heavyweight. $\endgroup$
    – djechlin
    Commented Nov 30, 2014 at 5:08
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
1
1
$\begingroup$

Let $\gcd(a,b)=d$. Then $\exists r,s \in \mathbb Z$ s.t. $d=ra+sb$. Since $\gcd(p,q)=1 \iff \exists m,n \in \mathbb Z$ s.t. $mp+nq=1$, we have from $1=r\frac{a}{d}+s\frac{b}{d}$ that $\gcd(\frac{a}{d},\frac{b}{d})=1$.

Note: $d=ra+sb \nrightarrow \gcd(a,b)=d$, but $mp+nq=1 \rightarrow \gcd(p,q)=1$

$\endgroup$
1
  • $\begingroup$ This is the same as the first proof in my answer $4$ years prior. $\endgroup$ Commented Mar 13, 2023 at 23:43
1
$\begingroup$

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.$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .