Integers Coprime to m Subset of Integers Modulo m

Theorem

Let $\Z_m$ be the set of integers modulo $m$.

Let $\Z'_m$ be the set of integers coprime to $m$ in $\Z_m$.

Then $\forall m \in \Z: m > 1: \varnothing \subset \Z'_m \subset \Z_m$.

Proof

By its definition, we have $\Z'_m = \left\{{x \in \Z_m: x \perp m}\right\}$.

From Subset of Set with Propositional Function, we have $\Z'_m \subseteq \Z_m$.

• As $\gcd \left\{{m, 0}\right\} = m$ it follows that $m > 1 \implies \gcd \left\{{m, 0}\right\} \ne 1$.

So $\left[\!\left[{0}\right]\!\right]_m \notin \Z'_m$.

However, $\left[\!\left[{0}\right]\!\right]_m \in \Z_m$, so $\Z'_m \ne \Z_m$.

Thus $\Z'_m \subset \Z_m$.

• Now, note that $\left[\!\left[{1}\right]\!\right]_m = 1 \implies 1 \perp m$.

So $\forall m \in \Z: \left[\!\left[{1}\right]\!\right]_m \in \Z'_m$.

Thus $\Z'_m \ne \varnothing$ and therefore $\varnothing \subset \Z'_m$.

$\blacksquare$