◀ ▲ ▶Branches / Number-theory / Proof: By Induction

Proof: By Induction

(related to Proposition: Existence and Number of Solutions of Congruence With One Variable)

By hypothesis, $a,b$ are integers, $m > 0$ is a positive integer. We first show that the solvability of the congruence is equivalent to $\gcd(a,m)\mid b.$

"$\Rightarrow$"

• Assume, the congruence with one variable $(ax-b)(m)\equiv 0(m)$ is solvable.
  • Therefore, we have also $(ax-b)(\gcd(a,m))\equiv 0(\gcd(a,m)).$
  • Since the greatest common divisor $\gcd(a,m)$ is a divisor of both, $a$ and $m$, we $(-b)(\gcd(a,m)) \equiv 0(\gcd(a,m)).$
  • It follows $\gcd(a,m)\mid b.$

"$\Leftarrow$"

• Assume, $\gcd(a,m)\mid b.$
  • Consider the congruence with one variable $$\frac{a}{\gcd(a,m)}x\equiv\frac{b}{\gcd(a,m)}\mod \frac{m}{\gcd(a,m)}.\label{eq:E18453}\tag{1}$$
  • Note that $\frac{a}{\gcd(a,m)}\perp \frac{m}{\gcd(a,m)}$ are co-prime, by generating co-prime numbers knowing the $\gcd$.
  • According to congruences and division with quotient and remainder (see also explanation), the integers $0,1,\ldots,m-1$ build a complete residue system modulo $m$.
• According to creation of complete residue systems from others, this holds also for the system $c\cdot 0,c\cdot 1,\ldots,c\cdot(m-1)$ with $c:=\frac{a}{\gcd(a,m)}.$
• Therefore, the congruence with one variable $(\ref{eq:E18453})$ has exactly one solution.
• With multiplication of congruences with a positive factor, it follows that also the congruence $(ax)(m)\equiv b(m)$ is solvable.

It remains to be shown that the congruence has exactly $\gcd(a,m)$ different solutions. * The congruence with one variable $(\ref{eq:E18453})$ has exactly one solution modulo $\frac{m}{\gcd(a,m)}.$ * Since $\gcd(a,m)\mid m$, there are $\gcd(a,m)$ as many solutions modulo $m.$

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

Github: