TL で見たので
問題概要
双子素数 が与えられる。
を
で割ったあまりと、
を
で割ったあまりをそれぞれ出力せよ。
制約
解法 1: Wilson の定理
簡単のため、適切に swap して とする。
Wilson の定理というのがあり、 を素数として
が成立する。これを用いると
が成立する。後者は Wilson をするまでもなく、 は
で割り切れる。
解法 2: 原始根
Wilson の定理を知らなかったとしても、原始根を用いると解ける (し、Wilson の定理の証明にもなる)。
以下、 として
を考える。
は奇数であるとしてよい。
での原始根を
とおくと、
と
とは集合として一致するので
となり、 の位数は
であって、
(
が整数であることに注意)
であるから、
が成立する。最後は、Fermat の小定理から であるが、
は原始根なので
とはならないことを用いた。
Wilson の定理は逆も成り立つ
今回の問題では使わない性質であるが、Wilson の定理は逆も成り立ち。すなわち、 ならば
は素数である。