Show that for any integer $x, ax\not\equiv1\pmod{a\cdot b}$ where $a,b$ are integers that $1<a$ and $1<b$

47 Views Asked by At

If $m$ is a natural number greater than $1$ and is not prime, then we know that $m=ab$, where $1<a<m$ and $1<b<m$. Show that there is no integer $x$ such that $ax≡1\pmod{m}$.

My thoughts:

What I think is $ax$ can only congruent to multiple of $a$ under mod $a\cdot b$ and since $a>1$ that means it could never congruent to $1$.

\begin{align} ax&\equiv y\pmod{a\cdot b}\tag*{Let $x\in\mathbb{Z}$, solve $y$}\\ y&=a(b\cdot k+x)\tag*{Case1: $ax<ab;k\in\mathbb{Z}$}\\ y&=a(x-b+b\cdot k)\tag*{Case2: $ax\ge ab;k\in\mathbb{Z}$}\\ y&\neq 1\tag*{Since $a>1$}\\ \end{align}

Is this idea correct, are there other approaches to prove this statement ?