The following proposition generalizes the previous proposition, which proves to be a special case of the following one with $\gcd(c,m)=1.$

Proposition: Cancellation of Congruences with General Factor

Let the $a,b,c$ be integers, and $m > 1$ be a positive integer and let $d=\gcd(c,m)$ be the greatest common divisor of $c$ and $m$. Then, from the equaility of the congruences $$(ac)(m)\equiv (bc)(m)$$ it follows that $$a\left(\frac md\right)\equiv b\left(\frac md\right).$$

Example

$3\cdot 2(8)\equiv 7\cdot 2(8)\Longrightarrow 3(4)\equiv 7(4).$

Proofs: 1

Proofs: 1


Thank you to the contributors under CC BY-SA 4.0!

Github:
bookofproofs


References

Bibliography

  1. Landau, Edmund: "Vorlesungen ├╝ber Zahlentheorie, Aus der Elementaren Zahlentheorie", S. Hirzel, Leipzig, 1927
  2. Jones G., Jones M.: "Elementary Number Theory (Undergraduate Series)", Springer, 1998