← Complete problem index

PROJECT EULER · #0451

Modular Inverses

Statement only · UnsolvedOriginal problem ↗

Consider the number 15.
There are eight positive numbers less than 15 which are coprime to 15: 1,2,4,7,8,11,13,14.
The modular inverses of these numbers modulo 15 are: 1,8,4,13,2,11,7,14
because
11mod15=1
28=16mod15=1
44=16mod15=1
713=91mod15=1
1111=121mod15=1
1414=196mod15=1

Let I(n) be the largest positive number m smaller than n1 such that the modular inverse of m modulo n equals m itself.
So I(15)=11.
Also I(100)=51 and I(7)=1.

Find I(n) for 3n2×107.

Write-up coming later

The complete problem is available here. An approach, code, and answer will be added later.