Math Problem Solver

There are multiple solutions for $x$ in the congruence relation $3454 x \equiv 2 \pmod{4666}$: $\textcolor{#228B22}{x \in \left\{ 1128, 3461\right\} }$

Remove the greatest common factor shared between the left-hand side, the right-hand side, and the modulus. Dividing each by $2$ yields $1727 x \equiv 1 \pmod{2333}$. From this, we know that $3454 x \equiv 2 \pmod{4666}$ has $2$ solutions.

This is a different expression in a different modulus, but can be used to compute the solutions.

We want to find $x$, and we have $1727 x$. In normal arithmetic, we would divide to get the answer.
However, division is not well-defined for every number in modular arithmetic. Division in modular arithmetic is better defined by the modular multiplicative inverse.

Modular Multiplicative Inverse

Definition

The modular multiplicative inverse of a given number $a$ is written as $a^{-1}$, for which $a \cdot a^{-1} \equiv 1 \pmod{n}$.

Solution

A number $a$ has a modular multiplicative inverse $a^{-1}$ if and only if $a$ and $n$ are coprime.

For a given base $a = 1727$ and a modulus $n = 2333$, the modular multiplicative inverse can be computed using the Extended Euclidean Algorithm, shown below.

Extended Euclidean Algorithm

Definition

The Extended Euclidean Algorithm is used to compute two integers, $s$ and $t$, for which the equation $a s + n t = \operatorname{gcd}(a, n)$ is true. It will also produce the modular multiplicative inverse of $a \pmod n$, provided $a$ and $n$ are coprime.

This is because coprime numbers have a GCD of 1, making the equation $1727 s + 2333 t = 1$.
You may notice that when $s$ and $t$ are integers, this is a definition for $1727 s \equiv 1 \pmod{ 2333 }$.
According to the definition of modular multiplicative inverse, $s$ is the modular multiplicative inverse of $1727$ in mod $2333$.

Solution

To set up the initial state, we set $s_0 = 1$, $t_0 = 0$, $s_1 = 0$, and $t_1 = 1$.
For a given step $i$: $$\begin{align*} r_{i+1} = r_{i-1} - q_{i} r_{i} \\ s_{i+1} = s_{i-1} - q_{i} s_{i} \\ t_{i+1} = t_{i-1} - q_{i} t_{i} \end{align*}$$
Then, we continue until the remainder is $0$. $$\begin{array}{|c|c|c|c|c|}\hline i & \textnormal{quotient }\left(q\right) & \textnormal{remainder }\left(r\right) & s & t \\\hline 0 & & 1727 & 1 & 0 \\\hline 1 & & 2333 & 0 & 1 \\\hline 2 & 0 & 1727 & 1 & 0 \\\hline 3 & 1 & 606 & -1 & 1 \\\hline 4 & 2 & 515 & 3 & -2 \\\hline 5 & 1 & 91 & -4 & 3 \\\hline 6 & 5 & 60 & 23 & -17 \\\hline 7 & 1 & 31 & -27 & 20 \\\hline 8 & 1 & 29 & 50 & -37 \\\hline 9 & 1 & 2 & -77 & 57 \\\hline 10 & 14 & 1 & 1128 & -835 \\\hline 11 & 2 & 0 & -2333 & 1727 \\\hline \end{array}$$ The GCD is $1$, in the remainder column in the second-to-last row, and the value of $s$ is $1128$ in the second-to-last row, under the $s$ column.

Checking against the congruence relation $1727 s \equiv 1 \pmod{ 2333 }$, we can see that $1727 \cdot 1128 = 1948056 \equiv 1 \pmod{ 2333 }$.

Multiplying both sides of the relation $1727 x \equiv 1 \pmod{2333}$ by the modular multiplicative inverse gives us $x \equiv 1128 \pmod{ 2333 }$.

We were originally solving $3454 x \equiv 2 \pmod{4666}$. In mod $4666$, there are $2$ numbers that are solutions. Given that there is one unique solution in mod $2333$, the other solution is equivalent in mod $2333$, but distinct in mod $4666$. These distinct solutions can be produced by adding the modulus $2333$ to the result until the result is no longer less than $4666$, meaning the solutions to $3454 x \equiv 2 \pmod{4666}$ are $1128, 3461$.

These solutions can be verified by plugging them back into the original reduced equation $3454 x \equiv 2 \pmod{4666}$: $$\begin{align*} & 3454 \cdot 1128 & = \; & 3896112 & \equiv \; & 2 \pmod{ 4666 } \\ & 3454 \cdot 3461 & = \; & 11954294 & \equiv \; & 2 \pmod{ 4666 } \\ \end{align*}$$