📂Number Theory

Roots of Congruence Equations

Algorithm ¹

The solution $x$ to the congruence equation $x^{k} \equiv b \pmod{ m }$, given that natural number $b,k,m$ satisfies $\gcd (b , m) = \gcd ( k , \phi (m) ) = 1$, can be calculated as follows:

---

Step 1.

Calculate $\phi (m)$.

---

Step 2.

Find $u, v$ that satisfies $ku - \phi (m) v =1$, and obtain $x^{ku} \equiv b^{u} \pmod{m}$ by raising both sides to the power of $u$.

---

Step 3.

Calculate $b^{u} \pmod{ m }$ using the Exponentiation by Squaring method.

Explanation

$\phi$ is the Euler’s Totient function which has a multiplicative property, making the factorization of $m$ critical.

As is known, factorization has no royal road and is extremely difficult, especially when a enormously large prime number $p,q$ exists, such that if $m=pq$, then starting from finding $x := \phi (m)$ becomes challenging. At first glance, this seems like a disadvantage, but on the contrary, this can be used to treat $x$ as if it were a code. Even if $k$ and $m$ are publicly known, it is extremely difficult to calculate $x$ without knowing the factorization of $m$. Therefore, $x$ can be a great encryption system if only those who are eligible to know it have information on the factorization of $m$. Such an encryption system is known as the RSA encryption.

This algorithm suggests that finding very large prime numbers has practical significance.

Proof

The existence of integer solution $u,v$ satisfying $ku - \phi (m) v =1$ is guaranteed, and since $ku = \phi (m) v + 1$, $$x^{ku} \equiv x^{ \phi (m) v + 1 } \pmod{m}$$

Euler’s Totient Theorem: $\gcd(x,m) = 1 \implies x^{ \phi (m) } \equiv 1 \pmod{m}$

Since $x^{ \phi (m) v + 1 } \equiv x^{ 1 } = b^{u} \pmod{m}$, simply calculate $b^{u}$. Although condition $\gcd (x, m) = 1$ was not satisfied, the $x$ obtained in this way poses no problem as a solution to the given congruence equation.

$$x^{k} = \left( b^{u} \right)^{k} = b^{uk} = b^{ 1+ \phi (m ) v} = b \cdot b^{ \phi (m ) v}$$ Since we assumed $\gcd (b , m) = 1$, the following holds: $$x^{k} \equiv b \pmod{ m }$$

■