Modular-arithmetic proofs

Question

Read examples $3.2.2$ and $3.2.3$ and answer the following questions:

Example $3.2.2.$ Find a solution to the congruence $5x\equiv11\mod 19$

Solution. If there is a solution then, by Theorem $3.1.4$, there is a solution within the set $\{0,1,2,\dots,18\}$. If $x=0$, then $5x=0$, so $0$ is not a solution. Similarly, for $x=1,5x=5$; for $x=2,5x=10;$ for $x=3,5x=15;$ and for $x=4,5x=20.$None of these are congruent to $11\mod19$. so we have not yet found a solution. However, when $x=6,5x=30$, which is congruent to $11\mod19$.Thus, $x\equiv6\mod19$ is a solution of the congruence.

Example $3.2.3$ Show that there is no solution to the congreuce $x^2\equiv3\mod5$

Proof. If $x=0$, then $x^2=0$; if $x=1$, then $x^2=1$; if $x=2$, then $x^2=4$; if $x=3$, then $x^2=9$,which is congruent to $4\mod 5$; and if $x=4$, then $x^2=16$ which is congruent to $1\mod5$. If there was any solution, it would be congruent to one of $\{0,1,2,3,4\}$ by Theorem $3.1.4$. Thus, the congruence has no solution. $\tag*{$\square$}$ Theorem 3.1.4

For a given modulus $m$, each integer is congruent to exactly one of the numbers in the set $\{0,1,2,\dots,m-1\}.$

(from UTM "A Readable Introduction to Real Mathmatics" Chapter 3)

---

Questions:

a) For any two integers $a$ and $b$, prove that $ab= 0$ implies $a= 0$ or $b= 0$. Prove that this is still true in mod prime numbers but not true in mod a composite number.

b)Here is how we prove $a^2=b^2$ implies $a=±b$: $$a^2=b^2\Rightarrow a^2-b^2=0\Rightarrow(a-b)(a+b)=0$$ $$\Rightarrow a-b=0 \vee a+b=0$$ Is this conclusion valid in modular arithmetic $\mod m$: does $a^2≡b^2(\mod m)$ implies $a≡ ±b(\mod m)$? Either prove, or give a counterexample.

c) Given integers $m$ and $1< a < m$, with $a|m$, prove that the equation $ax≡1 (\mod m)$ has no solution.(That is, if $m$ is composite, and $a$ is a factor of $m$ then $a$ has no multiplicative inverse.)

---

a) First part should be a easy proof,

But i'm not sure what it means by $$\text{Prove that this is still true in mod prime numbers}$$ $$\text{but not true in mod a composite number}$$

How does this related with first part.

Is it means $$\forall a,b,m\in\mathbb{N},\text{prime}(m)\rightarrow (ab\equiv0\mod m\rightarrow (a\equiv0\mod m\vee b\equiv0\mod m))$$

And if m is not prime implies otherwise?

b) $$\text{WTS }\forall a,b,m\in\mathbb{N},a^2\equiv b^2\mod m\rightarrow a\equiv \pm b\mod m$$

The converse is true, but my guess is there might be some counter examples for this one.

c) $$\forall m\in\mathbb{Z},a\in(1,m)\cap\mathbb{Z},a\mid m\rightarrow ax\equiv1\mod m \text{ has no solution}$$

Where should I start for c)?

Any help or hint or suggestion would be appreciated.

Answer 1

Here's a counterexample for $b)$. Let $m=8, a=1$ and $b=3$. Then $a^2\cong b^2\pmod8$, but $a\not\cong\pm b\pmod8$.

For $c)$, $a\mid m\land 1\lt a\lt m\implies m=ka$, where $k\not\cong0\pmod m$. So $ka\cong0\pmod m$. Now $0\cong kaa^{-1}\cong k\pmod m$. $\Rightarrow \Leftarrow $.

Answer 2

In view of a) and b), if $xy=0$ then $x=0$ or $y=0$ only holds if $x,y$ are nonzero divisors. In a field there are no zero divisors (since units are not zero divisors; 0 is not considered as a zero divisor, its absorbing: $x0=0=0x$ in each commutative ring).

So $(a+b)(a-b)=0\Rightarrow a+b=0\vee a-b=0$ only holds if $m$ is prime in your notation.

In view of c), the residue class ring ${\Bbb Z}_m$ consists of $0$, units and zero divisors. The units are the elements $a\ne 0$ s.t. $\gcd(a,m)=1$ and the zero divisors are the elements $a$ s.t. $\gcd(a,m)\ne 1$. That's the general situation. If $a\ne 1$ divides $m$, then $\gcd(a,m)=a$ and so $a$ is a zero divisor. So it there is no solution.