But what values of p should we even check?

1. Using Euler's Criterion we have that: 13^((p-1)/2)≡ 1 mod p if there is an x such that x^2 ≡ 13 mod p

2. Equivalently this is when the Legendre symbol is equal to 1

Now we know what values of p to check and furthermore x^2 ≡ 13 mod p has a solution.

A common technique to extend this to solve x^2 ≡ 13 mod p^2 is the following:

1. Solve x^2 ≡ 13 mod p using Tonelli-shanks algorithm

2. Use Hensel's lemma to lift it to get the solution x^2 ≡ 13 mod p^2

After reading the Tonelli-shanks algorithm wiki page, I found https://eli.thegreenplace.net/2009/03/07/computing-modular-square-roots-in-python/ which implements the algorithm along with some minor improvements, I will be adding both the Tonelli-Shanks algorithm and the Legendre symbol to my essential functions

Originally I solved the problem using the below method, but I didn't fully understand what I was doing. I took Number Theory this semester and learned why this method works and how to do it in a manner that I believe is more understandable! I will add the new method below

The new method involves using derivatives to lift roots