Coprimes
Claims: If \(n\) is coprime with \(a\) and \(b\), then \(n\) is coprime with \(ab\).
Firstly let us define what we mean by coprime. If \(n\) and \(a\) are coprime, then
$$ gcd(n, a) = 1 $$
Using Euclidean algorithm, we know that if (and only if) the above is true then there must exist integers \(x\) and \(y\) such that
$$ ax + ny = 1 $$
So then to prove the result above, let \(v\), \(w\), \(x\), \(y\) be some integer such that
[Read More]