Need help in showing that if (a,b) = 1, then (n,ab) = (n,a)(n,b).

Question

This is what I have been able to come up with so far.

I know that using Bezout's identity the g.c.d can be written into the sum of the products of two numbers (with a and b included). I also know that every number has a unique prime factorization, and to find the g.c.d you take the minimum value of the exponent for each prime number.

Additionally, I recognized that for the g.c.d of a and b to be 1, that means their prime factorization must include exponents raised to the zero power.

However, I am lost as to how to put all of this together to complete the proof.

CORRECTION For the last two lines it is supposed to be: min(v_i, r_i + s_i) = min(v_i, r_i) + min(v_i, s_i) and disregard the last line.

Answer 1

Let's consider only the primes where the exponents are greater than zero. Since a and b are coprime, your r's and your s's are disjoint and $min(v,r+s)$ is just either $min(v,r)$ or $min(v,s)$ You are mistaken in muliplying $min(v,r)$ and $min(v,s)$; they should be added, and you only get one or the other for a given prime, not both.

I don't think Bezout's inequality enters into it.

Answer 2

Let's make a teensy change to how we think of and express the unique prime factorization of a number.

If $p_k$ is the $k$th prime (so $p_1 = 2; p_2=3, etc.$) and for any natural number $m$ we will define $m_k$ as the non-negative integer (could be zero) that is the highest power of $p_k$ that divides $m_k$.

Then we can express the unique prime factorization of $m$ as $m = \prod\limits_{k=1}^{\infty} p_k^{m_k}$. And now that we've made that clear lets for the sake of typing assume the indexing of $1$ to $\infty$ is understood and we can write $m =\prod p_k^{m_k}$.

.....

Now a few things are immediate:

$\gcd(n,m) = \prod p_k^{\min (n_k,m_k)}$

$nm = \prod p_k^{n_k + m_k}$

$\gcd(n,m) =1$ implies that for any $k$ then either $n_k =0$ or $m_k=0$ (or, of course, both).

.....

Okay.... Now.... Let's just do it.

......

$\gcd(n,ab) = \prod p_k^{\min(n_k, a_k + b_k)}$

And $\gcd(a,n)\gcd(b,n) = \prod p_k^{(\min(a_k,n_k)+\min(b_k,n_k)}$.

And $\gcd(a,b)= 1$ so for all $k$ eithere $a_k =0$ or $b_k=0$.

So this is a matter of showing for each $k$ that $\min(n_k, a_k + b_k)=\min(a_k,n_k)+\min(b_k,n_k)$.

Now as $a_k = 0$ and $b_k =0$ so $a_k + b_k = a_k$ or $b_k$ whichever, if either, in non-negative (and therefore larger).

so $a_k + b_k = \max(a_k,b_k)$ and $\min(a_k,b_k) = 0$

So take cases:

......

Case 1: $n_k \ge \max (a_k, b_k) = a_k + b_k$.

The $\min(n_k,a_k+b_k) = a_k+b_k$ and $\min(a_k,n_k) +\min(b_k,n_k)= a_k + b_k$.

Case 2: $\min(a_k,b_k) = 0\le n_k < \max (a_k,b_k)$

Then $\min(n_k, a_k+b_k) =n_k$. And $\min(a_k,n_k) + \min(b_k,n_k)=$

Case 2a: $a_k = 0\le n_k <b_k$ then $\min(a_k,n_k) + \min(b_k,n_k) = a_k + n_k = 0+n_k = n_k$.

Case 2b: $b_k = 0 \le n_k < a_k$ then $\min(a_k,n_k) + \min(b_k,n_k)=n_k + b_k = n_k + 0 = n_k$.

That's it.

(Although it may seem a bit silly to note that for an infinite number of $k$ we are dealing with $n_k = a_k = b_k = 0$.)