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)


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.

  • $\begingroup$ For $b)$ it's no. Consider a composite $m$ and use $a)$. (If $m=p$ a prime, it'll be true. ) $\endgroup$ – 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.


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.