Prove if $n\in N$ is composite then there exists an equivalence class $a\bmod n$ that does not have a multiplicative inverse

324 Views Asked by At

Prove if $n\in N$ is composite then there exists an equivalence class $a\bmod n$ that does not have a multiplicative inverse

I know that the if $n=j*k$ with $j,k<n$ that $j\bmod n$ or $k\bmod n$ probably don't have inverses, but I don't remember the theorem for it.

1

There are 1 best solutions below

0
On

Per lulu's comment, $0$ is an equivalence class without a multiplicative inverse $\pmod n$.

Here is a demonstration that there is a non-zero equivalence class

without a multiplicative inverse $\pmod n$ when $n$ is composite.

Say $n=jk$ with $j$ and $k$ strictly between $0$ and $n$.

Then $jk\equiv0\pmod n$ but $j,k\not\equiv0\pmod n$.

Assume, aiming for contradiction, there is $k^{-1}$ such that $kk^{-1}\equiv1\pmod n$.

Then $0\equiv0\times k^{-1}\equiv (jk)k^{-1}\equiv j(kk^{-1})\equiv j\times1 \equiv j.$

This contradiction shows that $k$ is a non-zero equivalence class

without a multiplicative inverse $\pmod n$.

Swapping the role of $j$ and $k$ would show that $j$ is also not invertible $\pmod n$.