> [!NOTE] Definition (Coprime) > Two [[Integers|integers]] or [[Natural Numbers|naturals]], $a,b\in \mathbb{Z}$ are coprime or relatively prime if their [[Greatest Common Divisor (GCD)|gcd]] is $1.$ In this case, we write $a\perp b.$ # Properties > [!NOTE] Theorem (Span $\mathbb{\mathbb{Z}}$) > If $a,b\in\mathbb{Z}$ are coprime then for any $z\in \mathbb{Z}$ there exists $x,y\in\mathbb{Z}$ so that $z=ax+by$ *Proof*. Since $\gcd(a,b)=1,$ [[Bézout's lemma|Bézout's lemma]] asserts that there exists $u,v\in \mathbb{Z}$ so that $1=au+bv$Multiplying both sides by $z$ gives $z=auz + bvz. $We can use [[Extended Euclidean Algorithm|extended Euclidean algorithm]] to compute these Bézout coefficients. # Applications **System of linear congruence:** Given $\gcd(a,n)=1,$ we can can find a unique solution to $bx\equiv 1 \pmod{n}$ using the above algorithm (i.e. $b$ has a [[Unit in Integers Modulo n|multiplicative inverse]] in $\mathbb{Z}/n\mathbb{Z}$). The [[Chinese remainder theorem|Chinese remainder theorem]] asserts that there is a unique solution to any system of linear congruences provided the moduli are pairwise coprime.