PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 451 / モジュラ逆数

数 15 について考えよう。15と互いに素となる15以下の正数は8個ある。1, 2, 4, 7, 8, 11, 13, 14 である。それらの数の15を法とするモジュラ逆数は 1, 8, 4, 13, 2, 11, 7, 14 である。

  • 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

m の法 n に対するモジュラ逆数が m 自身となるような n-1 より小さい最大の正数 m を I(n) としよう.
I(15)=11, I(100)=51, I(7)=1

3 ≤ n ≤ 2*10^7 における ΣI(n) を求めよ。

Problem 451 - Project Euler


「m の法 n に対するモジュラ逆数が m 自身」を合同式で表します。

 m^2\equiv 1\pmod{n}\quad \therefore (m+1)(m-1)\equiv 0\pmod{n}

n を素因数分解してこれを処理すればいいことになります。m+1, m-1 両方の約数になりうる素数は2だけです。

ほとんどのプラミング言語ではこのように解くと思いますが,Mathematica はモジュラ逆数を直接計算できます。100のモジュラ逆数を求めてみましょう。

2番目に大きい 51 が I(100) です。因数分解した合同式から m=n-1 が必ずモジュラ逆数になることがわかるので,一般に I(n) はこの PowerModList の後ろから2番目の数です。その和を求めればできあがりです。