# 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.

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?

• Do you mean to say $a \vert ~ m$ and $ax \equiv 1 \pmod{m}$? – Robert Shore Sep 27 at 15:54
• Yes sorry i will correct that – bow123 Sep 27 at 15:55

## 3 Answers

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.

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

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$$