1
$\begingroup$

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?

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

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.