(mod P 上の逆元について)

問題 1 では、掛け算、足し算、引き算について行ってきました。

ここでは割り算について見ていきます。素数 P と 1 以上 P - 1 以下の整数 X に対し、 X × Y = 1 (mod P) となる Y (1 ≦ Y ≦ P - 1) が必ず 1 つずつ存在します。このとき、Y を X の逆元と呼びます。

mod P 上の演算で X を Y で割ることは、X に Y の逆元をかけることを意味します。

例として P = 5 とします。3 × 2 = 1 (mod 5) となるので、3 の逆元は 2 です。 1 の逆元は 1 × 1 = 1 (mod 5) となるので、1 となります。

また、2 ÷ 3 = 2 × 2 = 4 (mod 5) となり、4 ÷ 1 = 4 × 1 = 4 (mod 5) となります。

では、実際に逆元はどのように計算するのでしょうか。これは、問題2で学んだ高速なべき乗計算（繰り返し二乗法）を用いることで効率的に求めることができます。

逆元の計算はフェルマーの小定理を用います。フェルマーの小定理とは P が素数で a,P が互いに素なとき、a ^ (P - 1) = 1 (mod P) であるという定理です。

フェルマーの小定理により、1 以上 P - 1 以下の整数 X に対し、X × X ^ (P - 2) = 1 (mod P) が成り立つので、mod P 上での X の逆元は X ^ (P - 2) (mod P) であることがわかります。

先ほどの例では、3 の逆元は 3 ^ (5 - 2) = 2 (mod 5) と計算できます。

では実際に逆元を計算してみましょう。

(問題)

素数 P と Q 個の整数 q_1,q_2,...,q_Q が与えられます。1 ≦ i ≦ Q に対して、mod P 上での q_i の逆元を求めてください。