Project Euler 451 - Modular Inverses

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

Note: Code runs in ~270sec but i'm very happy with my understanding

Thought Process

We are looking for solutions to x^2 = 1 (mod n), for which there is a general known solution method which uses the following methods

Now let's simplify things, since for the specific case of a = 1 we get some nice simplifications in Hensel's Lemma

Using this we can quickly find all the solutions to x^2 = 1 (mod p^e) which is step 1 at the begin of this page, then we can use any standard Chinese Remainder Theorem function and we can now calculate I(n) extremely quickly, however this is not good enough to solve the problem.

The last trick is to notice that again due to the Chinese remainder theorem, if we have solved for example I(100) = I(2^2 * 5^2) then we can solve I(300) = I(3 * 100) by using the Chinese remainder theorem since gcd(3, 100) = 1.

Knowing this we can quickly solve for larger n given that we have solved it for smaller n. In this case a smallest prime factor sieve is very useful to not repeatedly call a prime factorization function

Interactive Code

Enter an Integer (yourinput)

Code will output ΣI(n) for 3 ≤ n ≤ yourinput