11
$\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$
2
4
$\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$
3
  • $\begingroup$ don't frame this as a contradiction. "hence e = 1". Much better conclusion. $\endgroup$ – djechlin Nov 30 '14 at 5:07
  • 1
    $\begingroup$ Let's not argue semantics. And this post is very old and correct as well. $\endgroup$ – Mr.Fry Nov 30 '14 at 7:22
  • 1
    $\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 Nov 30 '14 at 14:16
7
$\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$
4
  • $\begingroup$ I apologize, I was posting the exact same solution at the time, so I will upvote this. $\endgroup$ – Mr.Fry Apr 14 '14 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$ – André Nicolas Apr 14 '14 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 Apr 14 '14 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$ – André Nicolas Apr 14 '14 at 18:35
4
$\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$ – Michael Munta Sep 24 '19 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$ – Bill Dubuque Sep 24 '19 at 22:06
  • $\begingroup$ I don't understand this. How do you conclude that $d$ divides $(a,b)$? $\endgroup$ – Michael Munta Sep 25 '19 at 6:36
  • $\begingroup$ Is $c = (a,b)$ in the second proof as well? $\endgroup$ – Michael Munta Sep 25 '19 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$ – Bill Dubuque Sep 25 '19 at 12:49
2
$\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 Nov 30 '14 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$

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$
0
$\begingroup$

Assume WLOG that $a, b \geq 1$. Let $m = \dfrac{a}{\gcd(a,b)}$, and $n = \dfrac{b}{\gcd(a,b)}$, and let $c = \gcd(m,n)$. Then $c \mid m$, and $c \mid n$. This means: $(c\cdot \gcd(a,b)) \mid a$, and $(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$
-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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.