# Project Euler 457 - A polynomial modulo the square of a prime # Thought Process

This problem was extremely hard and I had to learn a lot of new things, there are 4 key facts that I will use to solve this problem

Now lets get into the problem, 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 Using f(x) = x^2 - 13, and e = 2, we can easily find solutions to x^2 = 13 (mod p) and then find solutions for n

# Interactive Code

Enter an integer (yourinput)

Code will output SR(yourinput)