Question

Show thatmis an integers greater than 1 and $\mathrm{ac}\equiv \mathrm{bc}\left(\mathrm{modm}\right)$, then$\mathrm{a}\equiv \mathrm{b}\left(\mathrm{modm}/\gcd \left(\mathrm{c},\mathrm{m}\right)\right)$

Short answer

$\mathrm{a}\equiv \mathrm{b}\left(\mathrm{modm}/\gcd \left(\mathrm{c},\mathrm{m}\right)\right)$

Step-by-step solution

Step 1

Given is an integer greater than .

$\mathrm{ac}\equiv \mathrm{bc}\left(\mathrm{modm}\right)$

To proof: $\mathrm{a}\equiv \mathrm{b}\left(\mathrm{modm}/\gcd \left(\mathrm{c},\mathrm{m}\right)\right)$

Proof by contradiction

Let us assume that b is the inverse of amodulom.

The inverse of modulo m is an integer $b$ for which $\mathrm{ab}\equiv 1\left(\mathrm{modm}\right)$

$a\equiv b\left(\mathrm{modm}\right)$

a is congruent to modulo $\mathrm{m}$ if mdivides $a-b$

Notation $a\equiv b\left(\mathrm{modm}\right)$

Then there exists a constant such that

$ac-bc=md$

Step 2

Let $f=\gcd \left(c,m\right)$.By definition of the greatest common divisor$f$, divides both integers

$$\begin{gathered} f\left|c \\ f\right|m \end{gathered}$$

Divide both sides of the equation$ac-bc=md$ by $f$

$ac-bc/f=md/f$

Let $m\text{'}=\frac{m}{gcd\left(c,m\right)}=\frac{m}{f}$

$\left(a-b\right)\frac{c}{f}=m\text{'}d$

Since$\raisebox{1ex}{$f$}\!\left/ \!\raisebox{-1ex}{$c$}\right.\frac{c}{f}$ is an integer

$m\text{'}|\left(a-b\right)$

is congruent to modulo m ifm divides $a-b$

$a\equiv b\left(\mathrm{mod}m\text{'}\right)$