# Modular-arithmetic proofs

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.

• For $b)$ it's no. Consider a composite $m$ and use $a)$. (If $m=p$ a prime, it'll be true. ) – Chris Custer Sep 27 '19 at 6:02

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