Generalized Euclid's lemma

Statement

Let $n$, $a$ and $b$ be integers. If $n \mid a b$ and $n$ and $a$ are coprime, then $n \mid b$.

Remarks

When $n$ is a prime $p$ and $p \nmid a$, then $p$ and $a$ are coprime. So this result implies Euclid's lemma. The proof uses Bézout's identity: from $n x + a y = 1$ we get $b = n b x + a b y$, and $n$ divides both terms. For example, $5 \mid 3 \cdot 10$ and $\gcd(5, 3) = 1$, so $5 \mid 10$.

Explanations

L1 human

If $n$ divides $a b$ but has no common factor with $a$, then all the factors of $n$ must come from $b$. For example, $4 \mid 3 b$ forces $4 \mid b$, because $3$ gives no factor $2$.