d×7≡1mod120
You asked:
Solve the linear congruence $d 7 \equiv 1 \pmod{120}$.
MathBot Answer:
There is a unique solution for $d$ in the congruence relation $d 7 \equiv 1 \pmod{120}$: $\textcolor{#228B22}{d = 103}$
Collect like terms, with constants on one side, and variables on the other: $7 d \equiv 1 \pmod{120}$.
We want to find $d$, and we have $7 d$.
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 = 7$ and a modulus $n = 120$, 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 $7 s + 120 t = 1$.
You may notice that when $s$ and $t$ are integers, this is a definition for
$7 s \equiv 1 \pmod{ 120 }$.
According to the definition of modular multiplicative inverse, $s$ is
the modular multiplicative inverse of $7$ in mod $120$.
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 & & 7 & 1 & 0 \\\hline
1 & & 120 & 0 & 1 \\\hline
2 & 0 & 7 & 1 & 0 \\\hline
3 & 17 & 1 & -17 & 1 \\\hline
4 & 7 & 0 & 120 & -7 \\\hline
\end{array}\]
The GCD is $1$, in the remainder column in the second-to-last row, and the value of $s$ is $-17$
in the second-to-last row, under the $s$ column.
Checking against the congruence relation $7 s \equiv 1 \pmod{ 120 }$, we can see that $7 \cdot -17 = -119 \equiv 1 \pmod{ 120 }$.
Multiplying both sides of the relation $7 d \equiv 1 \pmod{120}$ by the modular multiplicative inverse gives us $d \equiv 103 \pmod{ 120 }$.