Congruence

The congruence equation is one of the fundamental concepts in number theory:

Let $$$m$$$ be a given positive integer, and let $$$a$$$ and $$$b$$$ be integers. If $$$m\mid(a−b)$$$, then $$$a$$$ is congruent to $$$b$$$ modulo $$$m$$$, denoted as $$$a\equiv b\pmod m$$$ or $$$a\equiv b(m)$$$.

Other forms of expressing congruence include:

• $$$a=b+km$$$
• $$$a$$$ and $$$b$$$ have the same remainder when divided by $$$m$$$

Properties of congruence equations:

• If $$$a_1\equiv b_1\pmod m$$$ and $$$a_2\equiv b_2 \pmod m$$$, then $$$a_1 + b_1 \equiv a_2 + b_2 \pmod m$$$
• If $$$a\equiv b \pmod m$$$, then $$$a\equiv b + km\pmod m$$$, where $$$k$$$ is an integer
• If $$$a_1\equiv b_1 \pmod m$$$ and $$$a_2\equiv b_2 \pmod m$$$, then $$$a_1 b_1\equiv a_2 b_2 \pmod m$$$

Finding the smallest positive integer solution for the congruence equation $$$ax \equiv 1 \pmod b$$$ involves transforming the equation into $$$ax+by=1$$$ and using the Extended Euclidean Algorithm (EXGCD) to solve it.

EXGCD

The fundamental equation is to find $$$ax+by=1$$$, for instance, $$$ 8x+3y=1 $$$.

A step-by-step breakdown is performed to arrive at a solution:

• If $$$a < b$$$ in the equation $$$ax + by = 1$$$, no modifications are needed.
• When $$$a$$$ and $$$b$$$ are not coprime in the equation $$$ax + by = 1$$$, adjustments are necessary.
• For an equation in the form $$$ax + by = c$$$, the algorithm needs to be adjusted by dividing $$$a$$$, $$$b$$$, and $$$c$$$ by their greatest common divisor ($$$\gcd$$$) to yield a coprime equation. The final result using EXGCD yields $$$x=\frac{c}{\gcd(a,b)}$$$ and $$$y=0$$$.
• To find specific solutions or multiple solutions, adjustments are made to ensure $$$x$$$ is a positive minimum. Techniques like % operations or loops are employed to handle these cases.

Multiplicative Inverse (Modular Inverse)

Addition and multiplication operations are modular-friendly, but division isn't. Multiplicative inverse, denoted as $$$b^{-1}$$$ with respect to modulo $$$p$$$ (where $$$p$$$ is a prime number), satisfies the equation $$$(b\times b^{-1}) \pmod p = 1$$$. The range of $$$b^{-1}$$$ is $$$[0,p-1]$$$.

• Fermat's Little Theorem states that if $$$p$$$ is a prime number and integer $$$a$$$ is not a multiple of $$$p$$$, then $$$a^{p-1}\pmod p=1$$$.
• For a prime $$$p$$$, the modular inverse of $$$a$$$ is $$$a^{p-2}$$$, often computed using fast exponentiation techniques.
• If $$$p$$$ is not prime, the EXGCD method is employed to solve $$$b\times b^{-1} \equiv 1 \pmod p$$$, provided $$$b$$$ and $$$p$$$ are coprime. If they aren't, the inverse doesn't exist.
• Linear preprocessing from $$$1$$$ to $$$p-1$$$ can be utilized to compute inverses efficiently by using $$$a=p \text{ mod } i$$$ and $$$b=\frac{p}{i}$$$.