Coprimality

Two integers are coprime (or relatively prime) if they share no common factors other than 1. This concept is central to modular arithmetic and the Chinese Remainder Theorem.

Definition

Properties

1. Modular Inverse: $a$ has an inverse modulo $n$ if and only if $\gcd (a,n)=1$.
2. Multiplicativity: If $\gcd (a,b)=1$ and $\gcd (a,c)=1$, then $\gcd (a,bc)=1$.
3. Euclid's Lemma: If $a\mid bc$ and $\gcd (a,b)=1$, then $a\mid c$.
4. Division: If $ac\equiv bc(\mathrm{mod}n)$ and $\gcd (c,n)=1$, then $a\equiv b(\mathrm{mod}n)$.

Pairwise vs. Mutual Coprimality

For a set of integers $\{a_1,\dots ,a_k\}$:

• Pairwise Coprime: $\gcd (a_i,a_j)=1$ for all $i\ne j$.
• Mutually Coprime: $\gcd (a_1,\dots ,a_k)=1$.

Note:* Pairwise implies Mutual, but Mutual does not imply Pairwise (e.g., 6, 10, 15).

Practice Problems