けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

てんぷらたんの双子素数問題

数学(整数問題) 素数 Fermatの小定理原始根

TL で見たので

問題へのリンク

問題概要

双子素数 $a, b$ が与えられる。 $a!$ を $b$ で割ったあまりと、 $b!$ を $a$ で割ったあまりをそれぞれ出力せよ。

制約

$2 \le a, b \le 10^{9}$

解法 1: Wilson の定理

簡単のため、適切に swap して $b = a + 2$ とする。
Wilson の定理というのがあり、 $p$ を素数として

$(p-1)! ≡ -1 ({\rm mod}. p)$

が成立する。これを用いると

$a! ≡ (a+1)! × (a+1)^{-1} ≡ (-1) × (-1)^{-1} ≡ 1 ({\rm mod}. a+2)$
$(a+2)! ≡ 0 ({\rm mod}. a)$

が成立する。後者は Wilson をするまでもなく、 $(a+2)!$ は $a$ で割り切れる。

解法 2: 原始根

Wilson の定理を知らなかったとしても、原始根を用いると解ける (し、Wilson の定理の証明にもなる)。

以下、 $p = a+2$ として $a! {\rm mod}. p$ を考える。 $p$ は奇数であるとしてよい。 ${\rm mod}. p$ での原始根を $r$ とおくと、 ${1, 2, \dots, p-1}$ と ${r^{0}, r^{1}, \dots, r^{p-2}}$ とは集合として一致するので

$(p-1)! ≡ r^{0}r^{1}\dots r^{p-2} ≡ r^{\frac{(p-1)(p-2)}{2}}({\rm mod}. p)$

となり、 $r$ の位数は $p-1$ であって、

$\frac{(p-1)(p-2)}{2} ≡ -\frac{p-1}{2} ≡ \frac{p-1}{2} ({\rm mod}. p-1)$ 　( $\frac{p-1}{2}$ が整数であることに注意)

であるから、

$(p-1)! ≡ r^{\frac{p-1}{2}} ≡ -1 ({\rm mod}. p)$

が成立する。最後は、Fermat の小定理から $(r^{\frac{p-1}{2}} + 1)(r^{\frac{p-1}{2}} - 1) ≡ 0 ({\rm mod}. p)$ であるが、 $r$ は原始根なので $r^{\frac{p-1}{2}} ≡ 1$ とはならないことを用いた。

Wilson の定理は逆も成り立つ

今回の問題では使わない性質であるが、Wilson の定理は逆も成り立ち。すなわち、 $(p-1)! ≡ -1 ({\rm mod}. p)$ ならば $p$ は素数である。