Krdytkyu

I'm having trouble proving the following if and only if statement:

For all integers $a,b,n$, prove that $n|gcd(a,n)gcd(b,n)$ if and only if $n|ab$

For proving $n|gcd(a,n)gcd(b,n)implies n|ab$, I tried using Bezout's Lemma for both $gcd$s and expanding but didn't know how to show that $n$ divided $ab$.

Also didn't didn't how to approach the converse. Any help?

$c := (a,n)(b,n) = ((a,n)b,(a,n)n) = (ab,nb,na,nn)$

This implies that $ nmid ciff nmid ab,nb,na,nniff nmid ab$

May I suggest a different line of thought, which shows the claim of the problem to be valid not only for integers but for any elements in an arbitrary unique factorisation domain.

We concentrate on the reverse implication, as @fleablood has cleared the direct one out of the way for us. First, the general case of integers can be easily reduced to natural numbers by taking absolute values (which preserves divisibility, as it entails multiplication by the invertible $1$ or $-1$). Second, were any of your three numbers to be null, the claimed equivalence would hold trivially. We can thus limit our attention to the case when all three numbers are non-zero naturals.

Here we must prepare some tools: write $mathbb{P}$ for the set of all (natural non-zero) primes (from the point of view of abstract commutative ring theory, $-2$ and $0$ are also prime). For arbitrary $p in mathbb{P}$ define the $p$-valuation map:

$$v_{p}: mathbb{N}^{*} rightarrow mathbb{N}, v_{p}(n)=mathrm{max}{k in mathbb{N} | p^k|n }$$

This map assigns to any number $n$ the exponent with which $p$ appears in the prime factor decomposition of $n$, and it is easy to see that it is a morphism of monoids between $(mathbb{N}^{*}, cdot)$ and $(mathbb{N}, +)$.

For arbitrary set $I$, denote by $mathbb{N}^{I}$ the set of all families of naturals indexed by $I$ ; it comes equipped with a natural addition (carried out component-wise, the direct product of the standard addition on the individual factors) rendering it into a cancellable commutative monoid (cancellability means that every element is cancellable, i.e. it can be cancelled from equations). For arbitrary $nu in mathbb{N}^{I}$ introduce the support as:

$$mathrm{Supp} nu={i in I | nu_{i} neq 0}$$

The support encodes the indices at which the respective family exhibits non-zero component. Finally consider the subset:

$$mathbb{N}^{(I)}={nu in mathbb{N}^{I} | |mathrm{Supp} nu| in mathbb{N} }$$

of families of finite support ($|M|$ denotes the cardinality of set $M$ and claiming that it is a natural number is equivalent to claiming that $M$ is finite, in the formulation of Set Theory that I espouse); this subset is a submonoid of $mathbb{N}^{I}$.

We also must make use of the orders that naturally arise. On the direct product set $mathbb{N}^{I}$ we are going to consider the order relation $Pi'$, defined such that:

$$lambda leqslant_{Pi'} mu iff (forall i)(i in I implies lambda_{i} leqslant mu_{i})$$

in other words two families are comparable if and only if their components are comparable in the standard order on naturals at every index. This is none other than the direct product order of the individual standard orders on each of the factors $mathbb{N}$. As the usual order on $mathbb{N}$ is total it turns it into a lattice, meaning that any two elements admit infimum (their minimum) and supremum (their maximum). The direct product of lattices remains a lattice under the direct-product order: the infimum of any two families is expressed as the family of infima between the respective components at every index and similarly for suprema.

The set $mathbb{N}^{(I)}$ of families of finite support is a sublattice of this lattice structure (meaning that infima and suprema between two families of finite support remain families of finite support, which is easy to see) and when equipped with the restriction $Pi$ of the parent-order $Pi'$ the monoid of families of finite support becomes an ordered monoid, a so-called lattice ordered monoid. The parent monoid of all families equipped with $Pi'$ is also an ordered monoid (this simply means that the order is preserved under addition).

Denoting the divisibility relation on $mathbb{N}^{*}$ with $Delta$, let us notice that the structure $(mathbb{N}^{*}, cdot, Delta)$ is also a lattice-ordered monoid (the infimum/supremum between two elements under divisibility being none other than the greatest common divisor/least common multiple).

Finally we can state:

Structure theorem. Define
$$Gamma: mathbb{N}^{*} rightarrow mathbb{N}^{(mathbb{P})},
Gamma(n)=(v_{p}(n))_{p in mathbb{P}}$$
Then $Gamma$ is an isomorphism of ordered monoids between $(mathbb{N}^{*}, cdot, Delta)$ and $(mathbb{N}^{(mathbb{P})}, +, Pi)$

($Pi$ defined precisely as above).

The merit of all this is that under $Gamma$ the equivalence you seek to prove becomes:

$$lambda leqslant_{Pi} (lambda wedge mu)+(lambda wedge nu) iff lambda leqslant_{Pi} mu + nu$$

Broken down component-wise, this becomes:

$$m leqslant mathrm{min}{m, n}+mathrm{min}{m, p} iff m leqslant n+p$$

for any $m, n, p in mathbb{N}$.

Can you see why this would be so?

There is an even more general argument that can be made. Consider a commutative cancellable monoid $(M, cdot)$ with trivial group of units, equip it with the relation of divisibility $Delta$ which thus becomes an order on $M$ and assume that $(M, Delta)$ is an inf-lattice, meaning that any two elements have a greatest common divisor (so-called GCD monoids). In this setting it holds that

$$x|(x,y)(x,z) iff x|yz$$

for any $x,y,z in M$. Again, we focus on the not so simple implication. Write $$u=(x,y), v=(x,z), x=us=vt, y=uy', z=vz'$$

where it follows from standard properties of GCD-monoids that $(s, y')=(t, z')=1_{M}$. We exploit the relation $x|yz$ in two ways: on the one hand, from $us|uy'z$ and cancellability we infer $s|y'z$ and since $s, y'$ are coprime we obtain $s|z$ ; similarly, on the other hand we have $t|y$.
As we clearly have $t|x$, combining with the above entails $t|(x,y)=u$ and hence $(t,u)=t$. We therefore have $(x, uv)=(tv, uv)=(u,t)v=tv=x$, which means that $x|uv$, Q.E.D

Bill Dubuque has expressed this very elegantly!

Let $d=gcd(a,n)$ and $e=gcd(b,n)$ and let $a = da'; b = eb'$ and $n = n'd; n =overline ne$. Note: $n'$ is relatively prime to $a'$ and $overline n$ to $b'$

If $n|de$ then $n|de*a'b' = (da')(eb') = ab$.

That was the simple direction.

If $n|ab$ then $n'd|a'db$ so $n'|a'b$ but as $n'$ and $a'$ are relatively prime $n'|b$. So $n'$ is a common factor of $b$ and $n$ so $n'$ divides that greatest common factor of $b$ and $n$. So $n'|e$.

So $n'|e$ so $n'd|de$ so $n|de$.

Likewise we can argue:

If $n|ab$ then $overline ne|ab'e$ so $overline n|ab'$ but as $overline n$ and $a$ are relatively prime $overline n|a$. So $overline n$ is a common factor of $a$ and $n$ so $overline n$ divides that greatest common factor of $a$ and $n$. So $overline n|d$.

So $overline n|d$ so $overline ne|de$ so $n|de$.