Question

(a) Give an example to show that the following statement is false: If $ab\equiv ac\left(modn\right)$and$a\not\equiv 0\left(modn\right)$, then$b\equiv c\left(modn\right)$.

(b) Prove that the statement in part (a) is true whenever$\left(a,n\right)=1$.

Short answer

1. If we consider $a=6,b=4,c=6$, and$n=12$ ,the given statement is false.
2. It is proved that if $ab\equiv ac\left(modn\right)$and $a\not\equiv 0\left(modn\right)$,then$b\equiv c\left(modn\right)$ when$\left(a,n\right)=1$ .

Step-by-step solution

Give an example

Let us consider that $a=6,b=4,c=6$and $n=12$, then we can say that $ab\equiv ac\left(modn\right)$, that is,

$\begin{array}{rcl}6·4& \equiv & 6·6\left(mod12\right)\\ & \equiv & 0\left(mod12\right)\end{array}$

But it is observed that $a\not\equiv 0\left(mod12\right)$and $4\not\equiv 6$, that is, $4\not\equiv 6\left(mod12\right)$.

Therefore, the given statement is false.

Prove that the statement in part (a) is true whenever a,n=1

It is given that$ab\equiv ac\left(modn\right)$ , this implies that$\overline{)n}a\left(b-c\right)$ .

But we have a condition$\left(a,n\right)=1$ ,theleast common multiple of$a$ and$n$ is 1;this implies no prime factor of $n$divides$a$ . This means that all prime factors of$n$ divide $b-c$.

Therefore, $b\equiv c\left(modn\right)$ .

Hence, it is proved that if $ab\equiv ac\left(modn\right)$and$a\not\equiv 0\left(modn\right)$ , then $b\equiv c\left(modn\right)$when$\left(a,n\right)=1$ .