Given integers $m$ and $1 \lt a \lt m$, with $a \vert m$, prove that the equation $ax\equiv 1\pmod{m}$ has no solution.

Question

Given integers $m$ and $1 \lt a \lt m$, with $a \vert m$, prove that the equation $ax\equiv 1\pmod{m}$ has no solution. (That is, if $m$ is composite, and $a$ is a factor of $m$ then $a$ has no multiplicative inverse.)

Here is what i have done so far: I have said that if $m$ is even composite number than $a$ must also be even and that $ax-1$ will lead to a odd number therefore no solution. Also $ax\equiv 1\pmod{m}$ implies that there exists a $n$ such that $m=n(ax-1)$, this leaves a remainder of 1 and $m \gt 3 $ and therefore $m\nmid 1$.

For odd composite I am bit stuck and not sure what to do but it makes sense to show that there will be a remainder of $1$ left.

Does this make sense or am i doing it wrong?

Answer 1

Your proof isn't correct for $m$ even. Let $m=10, a=5.$ It need not be the case that a divisor of an even number is itself even.

But there's no need to break this problem up into cases. If $ax \equiv 1 \pmod{m}$, then $m \vert (ax-1)$. But $a \vert m \Rightarrow \exists q (aq=m)$ so

$$m \vert (ax-1) \Rightarrow \exists r(rm=arq=ax-1) \Rightarrow a(x-rq)=1,$$

where everything in sight is an integer and $1 \lt a$. That's not possible, so we have established a contradiction that proves the result.

Edited to add: The simpler way to say this is that because divisibility is transitive, $a \vert m$ and $m \vert (ax-1)$ implies $a \vert (ax-1)$, which obviously isn't possible.

Answer 2

This may be resolved in a fairly straightforward way which rests on modular arithmetic:

With

$1 < a < m, \; a \mid m, \tag 1$

we have

$\exists b, \; 1 < b < m, \; ab = m; \tag 2$

for such $b$,

$b \not \equiv 0 \mod m; \tag{2.5}$

now from (2),

$ab \equiv 0 \mod m; \tag 3$

if also

$\exists x, \; ax \equiv 1 \mod m, \tag 4$

then

$b \equiv bax \mod m; \tag 5$

but by (3),

$b \equiv bax \equiv (0)x \equiv 0 \mod m, \tag 6$

in contradiction to (2.5); thus there exists no such $x$.

The above is indeed a very special case of the more general

Fact: Let $R$ be a non-trivial commutative unital ring, and

$a \in R^\times; \tag 7$

then $a$ is not a zero divisor in $R$.

Indeed,

$\exists 0 \ne c \in R, \; ac = 0$ $\Longrightarrow c = a^{-1}ac = a^{-1}(0) = 0 \Rightarrow \Leftarrow c \ne 0. \tag 8$

Answer 3

If $ax=1\pmod m$ and $a|m$, then $a|1$. Hence $|a|=1$.