Calculate $x^2 \equiv -1 \mod 169$

Question

Calculate $x^2 \equiv -1 \mod 169$

By hand I checked that $x^2 \equiv -1 \mod 13$ gives these solutions: $$ x \equiv 5 \mbox{ or } x \equiv 8 \mod 13 $$ Let say that I take $x \equiv 5 \mod 13$ so I have $$ x\equiv 13k+5 \mod 169 \mbox { for some } k $$ so I calculating again by lifting ( I found this term there Solve $99x^2 \equiv 1 \mod 125$ )

$$(13k+5)^2 \equiv -1 \mod 169$$ $$169k^2 + 130k + 25 \equiv 168 \mod 169$$ $$130k \equiv 143 \mod 169$$ $$ k \equiv \frac{143}{130} \mod 169$$ but my $k$ doesn't seem to be integer... Wolfram tells that the solutions are $$x \equiv 70 \mod 169 \mbox{ and }x \equiv 99 \mod 169 $$

Answer 1

Here is another approach: $\mod 169:$ $$k \equiv \frac{143}{130} \equiv \frac{-26}{-39} \equiv \frac{2}{3} \equiv \frac{112}{168} \equiv \frac{112}{-1} \equiv -112 \equiv 169 - 112 \equiv 57 $$ so your $x$ is $$x \equiv 57 \cdot 13 + 5 \equiv 746 \equiv 70 $$ so $$ x = 70 + 169n $$ as you wrote. The same thing can be done for other solution.

Answer 2

From $130k\equiv 143$ mod $169$, you actually get $10k\equiv 11$ mod 13.

Then, $k\equiv 10^{-1}\cdot 11$ and you can find $10^{-1}(mod\,13)$ by Euclidean algorithm on finding $x,y$ s.t. $10x+13y=1$. Actually, we have $10\cdot 4-13\cdot 3=1$. Thus, $10^{-1}\equiv 4$ mod $13$.

Now, $k\equiv 44\equiv 5$ mod 13.

Put this $k$ in your work and everything will go well now

Answer 3

You were on the right track.

You could have said

$$169k^\color{red}2 + 130k + 25 \equiv -1 \mod 169$$

$$130k \equiv -26 \mod 169$$

$$10k \equiv -2 \mod 13$$

$$5k \equiv -1 \mod 13$$

$$k \equiv 5 \mod 13$$