Unlike addition, subtraction and multiplication of congruences, there is no general way to divide congruences. The reason for this is the following: We can have two congruence classes $a(m),b(m)\in\mathbb Z_m$, both unequal zero: $a(m)\not\equiv 0(m),$ and $b(m)\not\equiv 0(m),$ but their product is zero: $a(m)\cdot b(m)\equiv 0(m).$ Take for example $6(15)\cdot 5(15)\equiv 0(15).$ We say that $(Z_m,\cdot,+)$ has zero divisors. However, in some cases, we can simplify a given congruence $ac(m)\equiv bc(m)$ by canceling out the factor $c$. The following proposition shows that this is only possible if $c$ and the module $m$ are co-prime.

Proposition: Cancellation of Congruences With Factor Co-Prime To Module, Field $\mathbb Z_p$

Let the $a,b,c$ be integers, and $m > 1$ be a positive integer and let $c\perp m$ be co-prime. Then, from the equaility of the congruences $$(ac)(m)\equiv (bc)(m)$$ it follows that $$a(m)\equiv b(m).$$

In particular, if $m=p$ is a prime number, then $\mathbb Z_p$ is a (finite) field and the congruence $ax(p)\equiv b(p)$ is solvable, if $a\perp p,$ and has the unique solution $x(p)\equiv b\cdot a^{-1}(p).$

Notes

Proofs: 1

Algorithms: 1
Proofs: 2 3
Propositions: 4 5


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
  3. Kraetzel, E.: "Studienb├╝cherei Zahlentheorie", VEB Deutscher Verlag der Wissenschaften, 1981