2

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 $$

3 Answers3

3

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

Moonshine
  • 2,088
  • 1
    P.S. In some sense, what you call 'lifting' is closely related to Hensel lemma. – Moonshine Aug 24 '19 at 15:09
  • Can you a bit more explain how you got $10k \equiv 11 \mod 13$? It is not obvious for me –  Aug 24 '19 at 15:22
  • @Tester1998 Cancelling $,13,$ shows $,130k = 143+169n\iff 10k = 11 + 13n\ \ $ – Bill Dubuque Aug 24 '19 at 15:52
  • Generally $ab \equiv ac \pmod n \Longleftrightarrow b \equiv c \pmod {n'}$, where $n'=\frac{n}{\gcd(a,n)}$, which can be proven directly using the definition of congruences. In your case, we have $a=13, b=10k, c=11, n=169, n'=13$. – Ingix Aug 24 '19 at 15:52
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.

mvxxx
  • 286
1

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$$

J. W. Tanner
  • 60,406