161010(4)

Ruby


3^n をn で割った余りについて(2)

A277289 のCOMMENTS に書いた

今のところ何番目かわからない要素について、

一応要素であることを確認しておく。

def pow(a, m, mod)
  return 1 % mod if m == 0
  k = pow(a, m >> 1, mod)
  k *= k
  return k % mod if m & 1 == 0
  return k * a % mod
end

[38832409867, 492385451091805616444].each{|i| p [i, pow(3, i, i) - i]}

出力結果
[38832409867, -7]
[492385451091805616444, -7]