160721(4)

Ruby

Numbers n such that 2^n == 3 (mod n)

「数論〈未解決問題〉の事典」の「F10」には、

n = 4700063497, 63130707451134435989380140059866138830623361447484274774099906755

しか載っていないが、

オンライン整数列大辞典の
A050259
をもとに、他の解も確認してみた。

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

ary =
[1,4700063497,3468371109448915,8365386194032363,
 10991007971508067]
ary.each{|i| p pow(2, i, i) == (3 % i)}

# Peter Montgomeryが見つけた解
i = 63130707451134435989380140059866138830623361447484274774099906755
p pow(2, i, i) == (3 % i)

出力結果
true
true
true
true
true
true