Intereting Posts

Ideal of the pullback of a closed subscheme
How does e, or the exponential function, relate to rotation?
Is it possible to divide a circle into $7$ equal “pizza slices” (using geometrical methods)?
Placing stones on vertices of polygon
Evaluating Indefinite Integrals of the form $\int\frac{f(x)}{p(x) \sqrt{q(x)}}\mathrm dx$
First-order nonlinear ordinary differential equation
How many sides does a circle have?
Calculating the total number of surjective functions
Reading the mind of Prof. John Coates (motive behind his statement)
A generalized (MacLaurin's) average for functions
Prove functions defined by sup and inf are continuous
Can the factorial function be written as a sum?
How to find roots of $f(z)=(a+yg(z))^2+g(z)^2=0$?
How do you prove that $\{ Ax \mid x \geq 0 \}$ is closed?
The concept of ordinals

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?

- Doubt regarding divisibility of the expression: $1^{101}+2^{101} \cdot \cdot \cdot +2016^{101}$
- Prove that $(mn)!$ is divisible by $(n!)\cdot(m!)^n$
- Basic Modulo Question
- Sum of GCD(k,n)
- Show that $\gcd\left(\frac{a^n-b^n}{a-b},a-b\right)=\gcd(n d^{n-1},a-b)$
- 3 never divides $n^2+1$

- Prison problem: locking or unlocking every $n$th door for $ n=1,2,3,…$
- If $a$, $a+2$ and $a+4$ are prime numbers then, how can one prove that there is only one solution for $a$?
- Consecutive sets of consecutive numbers which add to the same total
- Prove $\frac{a^3+b^3+c^3}{3}\frac{a^7+b^7+c^7}{7} = \left(\frac{a^5+b^5+c^5}{5}\right)^2$ if $a+b+c=0$
- $\gcd (ca, cb) = \gcd (a, b)c$ if $c > 0$
- Elementary number theory - prerequisites
- The sum of square roots of non-perfect squares is never integer
- Would proof of Legendre's conjecture also prove Riemann's hypothesis?
- How do you find all $n$ such that $\phi(n)|n$
- Show that $5^n$ divides $F_{5^n}$.

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

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

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

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,\,$ $\,(ax,bx) = (ax,ax) = (a)x = (a,b)x\,$ hence it is true. $ $ Else $\,a\neq b;\,$ wlog, by symmetry, $\,a > b\,$ so $\,(ax,bx) = (ax\!-\!bx,bx) = \color{}{((a\!-\!b)x,bx)}\,$ with 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$.

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?

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

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

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

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

- How does one create a partition of unity for a complex manifold?
- Best strategy to pick a lock which opens if at least two of its three decimal digit wheels are dialed correctly?
- Show that $k/(xy-1)$ is not isomorphic to a polynomial ring in one variable.
- Summation formula name
- Examples of open problems solved through short proof
- EGF of rooted minimal directed acylic graph
- If G is a finite abelian group and $a_1,…,a_n$ are all its elements, show that $x=a_1a_2a_3…a_n$must satisfy $x^2=e$.
- What is the predual of $L^1$
- A young limit $\lim_{n\to\infty} \frac{{(n+1)}^{n+1}}{n^n} – \frac{{n}^{n}}{{(n-1)}^{n-1}} =e$
- Books like Grundlagen der Analysis in French
- Is $Y \cup_f X$ a CW complex?
- If $x\equiv 1 \mod 3$, then $x^{100}\equiv 1 \mod 3$.
- Short calculation of the dilogarithm?
- Finding the limit of $(1-\cos(x))/x$ as $x\to 0$ with squeeze theorem
- Morphic Image of a Complete Variety