← 完整题目索引

PROJECT EULER · #0451

模逆元

Modular Inverses

仅题目 · 待解原题 ↗

考虑数字 15
有八个小于 15 的正数与 15 互质:1,2,4,7,8,11,13,14
这些数字以 15 为模的模逆为:1,8,4,13,2,11,7,14
因为
11mod15=1
28=16mod15=1
44=16mod15=1
713=91mod15=1
1111=121mod15=1
1414=196mod15=1

I(n) 为小于 n1 的最大正数 m,使得 mn 的模逆等于 m 本身。
所以I(15)=11
还有 I(100)=51I(7)=1

I(n) 等于 3n2×107

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。