Solve $124\, x = 1 \pmod{625}$ for $x$

Question

I know the answer is $x = 499 + 625\, z$ where $z$ is an integer, from this source.

I also know that you use the Extended Euclidean algorithm

Answer 1

Another option is \begin{align} 124 \, x &= 1 \pmod {625} \iff \\ 124 \, x &= 625 \, q + 1 \quad (q \in \mathbb{Z}) \iff \\ 124 \, x - 625 \, q &= 1 \quad (q \in \mathbb{Z}) \iff \\ 124 \, x + 625 \, y &= 1 \quad (*) \end{align} where $(*)$ is a linear Diophantine equation in integer $x, y$.

The solution algorithm involves the extended Euclidean algorithm.

For the coefficients $a = 124, b = 625$ we get $g = \gcd(a,b) = \gcd(124, 625) = 1$ so we do not have to rescale and $g$ divides $c = 1$, so we have solutions.

The solutions of the homogeneous equation to $(*)$ $$ 124 \, x + 625 \,y = 0 $$ are $$ (x_h, y_h) = (625 \, t, -124 \, t) \quad (t \in \mathbb{Z}) $$

A particular solution of $(*)$ is found using the extended Euclidean algorithm which gives (link) $$ (x_p, y_p) = (-126, 25) $$ All solutions are found by adding a particular solution to the homogenous solutions: $$4 (x, y) = (625\, t - 126, -124\, t + 25) $$ The first component is $$ x = 625 \,t - 126 = 625 \, (t - 1) + 625 - 126 = 625 \, t' + 499 $$

Answer 2

$$ 124 x \equiv 1 \bmod 625 \implies 124 x \equiv 1 \bmod 125 \implies -1 x \equiv 1 \bmod 125 \implies x \equiv -1 \bmod 125 $$

Write $x= 125y-1$. Then $$ 0 \equiv 124 x-1 = (125-1)(125y-1)-1 \equiv -125y-125=-125(y+1) \bmod 625 $$ This implies $y \equiv -1 \bmod 5$. Write $y=5z-1$. Then $$ x = 125y-1 = 125(5z-1)-1 = 625z - 126 = 625(z-1)+499 $$

Answer 3

Hint:

Solve the linear Diophantine equation $124x+625m=1$.

Answer 4

In this particular case, by noticing that $124 = 5^3 - 1$, $625 = 5^4$ and $$(5^3 + 1)(5^3 - 1) = 5^6 - 1 = -1 \pmod{5^4}$$ we get $x = -(5^3 + 1) = -126 = 499 \pmod{625}$.

Answer 5

We wish to solve the congruence $124x \equiv 1 \pmod{625}$, which means we must solve for the multiplicative inverse of $124 \pmod{625}$.

Since $\gcd(124, 625) = 1$, $124$ has a multiplicative inverse modulo $625$. To find the inverse, we use the extended Euclidean algorithm. \begin{align*} 625 & = 5 \cdot 124 + 5\\ 124 & = 24 \cdot 5 + 4\\ 5 & = 1 \cdot 4 + 1\\ 4 & = 4 \cdot 1 \end{align*} Now, we work backwards to write $1$ as a linear combination of $124$ and $625$. \begin{align*} 1 & = 5 - 4\\ & = 5 - (124 - 24 \cdot 5)\\ & = 25 \cdot 5 - 124\\ & = 25(625 - 5 \cdot 124) - 124\\ & = 25 \cdot 625 - 126 \cdot 124 \end{align*} Hence, $-126 \cdot 124 \equiv 1 \pmod{625}$. Thus, $x \equiv 124^{-1} \equiv -126 \equiv 499 \pmod{625}$.