161010(2)

Ruby


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

A277126, A277274 の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

[7469046275, 598371102650063].each{|i| p [i, pow(3, i, i)]}

出力結果
[7469046275, 7]
[598371102650063, 11]