Proof verification: If $\gcd(n,a) = 1$ and $n\mid ab$ then $n\mid b$.

Question

The statement I'm trying to prove is:

Show that if $\gcd(n,a) = 1$ and $n\mid ab$ then $n\mid b$.

I feel like my proof right now is correct but a bit disorganized and repetitive. Can I please get feedback on the format of my proof, if the proof is in fact correct and any suggestions readers may have on how to refine my proof. I feel like it's too long and I can shorten it but I also don't want to lose the substance of the proof.

Proof:

For the purposes of this question we will assume $\mathbb{N}$ includes 0. Let, $n,a,b \in \mathbb{Z}$. Suppose $\gcd(n,a) = 1$ and $n|ab$. I aim to prove that $n|b$.

By the fundamental theorem of arithmetic, $n,a,b$ all have prime factorization. Let $r \in \mathbb{Z}$. Let $p_1 < p_2 < ... < p_r$ be distinct primes, for $r \in \mathbb{N}$. Let $i \in \mathbb{N}$ such that $1 \leq i \leq r$. Let $\eta_i, \alpha_i, \beta_i \in \mathbb{N}$ be the powers of the primes in each of the prime factorizations of $n, a$ and $b$, such that:

$ n = p_1^{\eta_1} \cdot p_2^{\eta_2} \cdot p_2^{\eta_3} \cdot ... \cdot p_r^{\eta_r} \\ \\ a = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot p_2^{\alpha_3} \cdot ... \cdot p_r^{\alpha_r} \\ \\ b = p_1^{\beta_1} \cdot p_2^{\beta_2} \cdot p_2^{\beta_3} \cdot ... \cdot p_r^{\beta_r} \\ $

With this notation we have that $ab = p_1^{\alpha_1 + \beta_1} \cdot p_2^{\alpha_2 + \beta_2} \cdot p_2^{\alpha_3 + \beta_3} \cdot ... \cdot p_r^{\alpha_r + \beta_r}$

We have that, $n|ab$. Hence, $\exists k \in \mathbb{Z}$ such that $nk = ab$. That means that $n \leq ab$ and in particular, $\eta_i \leq \alpha_i + \beta_i$. As well, since $\gcd(n,a) = 1$, the only common divisors $n$ and $a$ is $1$. That means it impossible for a prime divisor of $n$ to also be a prime divisor of $b$. Using our notation, it must be the case that for any $i$, if $\eta_i > 0$ then $\alpha_i = 0$ and if $\alpha_i > 0$ then $\eta_i = 0$. If that were not the case then gcd($n,a$) $\neq 1$.

But now, since $nk = ab$ and gcd($n,a$) = 1, then $\exists k'$ such that $nak' = ab$. That implies that $nk' = b$. By definition of division, that implies that $n|b$.

Answer 1

Your proof looks correct. In the last paragraph you could explain a bit more in details why there is such $k'$, but I believe you understand why is this the case. It just follows from the fact that the power of each prime $p_i$ in $na$ is either $\alpha_i$ or $\eta_i$, and both are not bigger than $\alpha_i+\beta_i$.

But there is also a much shorter proof, which doesn't use prime factorization. If $\gcd(n,a)=1$ then there are integers $k,l\in\mathbb{Z}$ such that $ka+ln=1$. Multiply this by $b$ to get $kab+lnb=b$. Since $n$ divides both $kab$ and $lnb$, it follows that $n|b$ as well.

Answer 2

Another proof of this, but using multisets (you can have repeated elements): Let A, B, N be the multiset that contains the prime factorization of a,b,n.

$n \mid ab \implies N \subseteq (A+B)$, but as $N \cap A=\emptyset$ because $gcd(n,a)=1$, then $N \subseteq B \implies n \mid b$

Answer 3

Write $d(r)$ for the denominator of a rational $r$ (when written in lowest terms).

$a$ and $n$ are coprime, so $d(a/n)=n$.

Let $d(b/n)=m$. Then $1/m$ is a multiple of $1/n$, so $m\mid n$.

$n\mid ab$, so $ab/n$ is an integer, so $m\mid a$. But $a$ and $n$ are coprime, so $m=1$, so $b/n$ is an integer, i.e. $n\mid b$.