Linear congruence with Fermat's little theorem 987x ≡ 610 (mod 1597)

Question

987x ≡ 610 (mod 1597)

Is this correct way of applying little Fermat's theorem for linear congruences? Does it make any sense? If not could someone advice a bit.

Since gcd(987,1597)=1

-> 987ˆ1597-1 ≡ 1 (mod 1597)

-> 987ˆ1596 ≡ 1 (mod 1597)

610 ≡ 610 (1597)

987ˆ1596 * 610 ≡ 610 (mod 1597)

987 * 987ˆ1595 * 610 ≡ 610 (mod 1597)

-> x0 = 987ˆ1595 * 610

->[987ˆ1595 * 610]127

Answer 1

For an explicit solution, you have to perform the extended Euclidean algorithm: $$\begin{array}{rrrc} & u_i&v_i&q_i \\ \hline 1597& 0&1 \\ 987&1&0&1 \\ \hline 610&-1&1&1 \\ 377&2&-1&1\\ 233&-3&2&1\\ 144&5&-3&1\\ 89&-8&5&1\\ 55&13&-8&1\\ 34&-21&13&1\\ 21&34&-21&1\\ 13&-55&34&1\\ 8&89&-55&1\\ 5&-144&89&1\\ 3&233&-144&1\\ 2&-377&233&1 \\ 1&\color{red}{610}&-377\\ \hline \end{array}$$ Hence, a Bézout's relation between $987$ and $1597$ is $\;610\cdot 987-377\cdot 1597=1$, which shows that $$987^{-1}\bmod 1597=610, \quad \text{whence }\; x\equiv 610^2\equiv \color{red}{-1\bmod1597}.$$

Answer 2

I like to do the extended Euclidean algorithm by continued fractions.

$$ \gcd( 1597, 987 ) = ??? $$

$$ \frac{ 1597 }{ 987 } = 1 + \frac{ 610 }{ 987 } $$ $$ \frac{ 987 }{ 610 } = 1 + \frac{ 377 }{ 610 } $$ $$ \frac{ 610 }{ 377 } = 1 + \frac{ 233 }{ 377 } $$ $$ \frac{ 377 }{ 233 } = 1 + \frac{ 144 }{ 233 } $$ $$ \frac{ 233 }{ 144 } = 1 + \frac{ 89 }{ 144 } $$ $$ \frac{ 144 }{ 89 } = 1 + \frac{ 55 }{ 89 } $$ $$ \frac{ 89 }{ 55 } = 1 + \frac{ 34 }{ 55 } $$ $$ \frac{ 55 }{ 34 } = 1 + \frac{ 21 }{ 34 } $$ $$ \frac{ 34 }{ 21 } = 1 + \frac{ 13 }{ 21 } $$ $$ \frac{ 21 }{ 13 } = 1 + \frac{ 8 }{ 13 } $$ $$ \frac{ 13 }{ 8 } = 1 + \frac{ 5 }{ 8 } $$ $$ \frac{ 8 }{ 5 } = 1 + \frac{ 3 }{ 5 } $$ $$ \frac{ 5 }{ 3 } = 1 + \frac{ 2 }{ 3 } $$ $$ \frac{ 3 }{ 2 } = 1 + \frac{ 1 }{ 2 } $$ $$ \frac{ 2 }{ 1 } = 2 + \frac{ 0 }{ 1 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccccccccccccccccccccccccccc} & & 1 & & 1 & & 1 & & 1 & & 1 & & 1 & & 1 & & 1 & & 1 & & 1 & & 1 & & 1 & & 1 & & 1 & & 2 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 1 }{ 1 } & & \frac{ 2 }{ 1 } & & \frac{ 3 }{ 2 } & & \frac{ 5 }{ 3 } & & \frac{ 8 }{ 5 } & & \frac{ 13 }{ 8 } & & \frac{ 21 }{ 13 } & & \frac{ 34 }{ 21 } & & \frac{ 55 }{ 34 } & & \frac{ 89 }{ 55 } & & \frac{ 144 }{ 89 } & & \frac{ 233 }{ 144 } & & \frac{ 377 }{ 233 } & & \frac{ 610 }{ 377 } & & \frac{ 1597 }{ 987 } \end{array} $$ $$ $$ $$ \begin{array}{ccc} \frac{ 1 }{ 0 } & \mbox{digit} & 1 \\ \frac{ 1 }{ 1 } & \mbox{digit} & 1 \\ \frac{ 2 }{ 1 } & \mbox{digit} & 1 \\ \frac{ 3 }{ 2 } & \mbox{digit} & 1 \\ \frac{ 5 }{ 3 } & \mbox{digit} & 1 \\ \frac{ 8 }{ 5 } & \mbox{digit} & 1 \\ \frac{ 13 }{ 8 } & \mbox{digit} & 1 \\ \frac{ 21 }{ 13 } & \mbox{digit} & 1 \\ \frac{ 34 }{ 21 } & \mbox{digit} & 1 \\ \frac{ 55 }{ 34 } & \mbox{digit} & 1 \\ \frac{ 89 }{ 55 } & \mbox{digit} & 1 \\ \frac{ 144 }{ 89 } & \mbox{digit} & 1 \\ \frac{ 233 }{ 144 } & \mbox{digit} & 1 \\ \frac{ 377 }{ 233 } & \mbox{digit} & 1 \\ \frac{ 610 }{ 377 } & \mbox{digit} & 2 \\ \frac{ 1597 }{ 987 } & \mbox{digit} & 0 \\ \end{array} $$

$$ 1597 \cdot 377 - 987 \cdot 610 = -1 $$

I guess they did this on purpose, it turns out $$ 987 \cdot 610 \equiv 1 \pmod {1597}. $$ With $$ 987 \cdot x \equiv 610 \pmod {1597}, $$ we get $$ x \equiv 610^2 \pmod {1597}, $$ $$ x \equiv 1596 \equiv -1 \pmod {1597}. $$

I see what happened, $610 + 987 = 1597,$ so $x\equiv -1$ makes sense. Altogether, the square rrots of $-1$ are $610$ and $987.$ Well, why not?