ProjectEuler 451 Modular inverses - 拼圖

451. Modular inverses

http://projecteuler.net/problem=451

思考一下15這個數字。

比15小又和15互質的正整數有8個：1、2、4、7、8、11、13、14。

這些數字對15的模反元素(Modular inverses)分別是1、8、4、13、2、11、7、14。

因為

1 × 1 = 1 mod 15 = 1
2 × 8 = 16 mod 15 = 1
4 × 4 = 16 mod 15 = 1
7 ×13 = 91 mod 15 = 1
11 ×11 = 121 mod 15 = 1
14 ×14 = 196 mod 15 = 1

令I(n)為比n-1小的最大的正整數m，且m對n的模反元素就是m自己本身。

所以I(15) = 11。

已知I(100) = 51以及I(7) = 1。

請求出ΣI(n)對3≦n≦2 ×10^7的和。

--