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

Official link: https://projecteuler.net/problem=457

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

  1. Legendre symbol

  2. Euler's criterion

  3. Tonelli–Shanks algorithm

  4. Hensel's lemma

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)