PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 271 / モジュラー立方数1

正の整数 n に対し,S(n) を 1< x< n で x^3≡1 mod n をみたす整数 x の和と定義する。n=91 のとき,x は8つの値を取りうる。9,16,22,29,53,74,79,81 である。
S(91)=9+16+22+29+53+74+79+81=363

S(13082761331670030) を求めよ。

Problem 271 - Project Euler


組み込み関数の PowerMod で x^3≡1 mod n が解けるので助かりました。

さて,与えられた 13082761331670030 は2から41までの素数の積です。
x^3≡1 mod n を各素数について解いたら,2, 3, 5, ... で割った余りの条件をみたす数を求めるのに中国式剰余定理が使えます。特に工夫するまでもなく,0.0006秒で終了しました。

素数のリストをベタ打ちするのはどうかと思ったので,すこし一般的な形に直してみました。ちょっと遅くなります。