大雑把に逆元を理解したい
筆者はおつむが残念なので、厳密性に欠けた部分があるかもしれません。また、高校数学までを理解していれば多分読めます。
競プロの実装については一切記載していません！
- 単位元とは
ざっくりいうと、その演算を右からしても左からしても元の値を変化させないようなものをいいます。
加法の単位元は0です。例えば5+0=0+5=5なので。
乗法の単位元は1です。例えば5*1=1*5=5なので。
- 逆元とは
ざっくりいうと、ある数xに対してある演算を行ったとき、右から演算しても左から演算してもその結果が単位元となるものをいいます。
xに対して…
加法の逆元は-xです。
乗法の逆元は、x^-1です。x=0のときは定義されません[要出典]。
- 逆元を求めてみたい
法は素数とします。だいたい10^9+7ですし。知らんけど。また、aとpは互いに素とします。互いに素じゃなかったら困るので。
さて、先程述べたことを思い出すと、除法は乗法の逆元をかけているとみなすことができます。
つまりmod p上での除法は、もとの数に逆元をかけてあげればいいことになります。
ですから、私達のしたいことは整数aに対して
ax≡1(mod p)…①
なるxを求めてあげることです。このxがaの逆元となります。
ところで、不定方程式
ax+py=1…②
を考えてみましょう。不定方程式にmodをとって解いた経験はお有りでしょう。この不定方程式にmod pを取れば①に一致します。
なので、②を満たす(x,y)を求めてあげれば、xはaの逆元となります。
特殊解を(x',y')とすれば、媒介変数k(∈Z)を用いて
x=pt+x',y=-at+y'となりますから、結局特殊解を求めるだけで用は済みます。aとpが互いに素であるとき、この方程式は無数に解があることが知られています(あとで証明します)から、必ず逆元が存在することがわかります。
- ax+py=1型の方程式には、aとpが互いに素なときには解が無数に存在する証明
(i):まず、「a,2a,3a,……,(p-1)aをpで割ったあまりはすべて相異なる」を示します。あまりが同じになる組があるとすれば、これをkaとla(1≦k<l≦n-1)とおきますが、2つの数の差はpで割り切れることになります。つまり、
(k-l)a≡0(mod p)…③
となりますが、aとpは互いに素であるため、③が成り立つには、k-l≡0でなくてはいけません。kとlの範囲を考えてあげると、このような(k,l)は存在しません。したがって背理法によって(i)が示されました。
(ii):次に、(i)で扱った{a,2a,3a,……,(p-1)a}の集合を考えます。
(i)で示したことから、この集合の要素をpで割った余りには、1からp-1までの(p-1)種類の数がそれぞれ一回だけ登場するはずです。ですからpで割ったあまりが1になるような数が(i)で考えた集合の中に存在します。うまいこと(s,t)を選べば、
sa=tp+1
とできます。
これを移項して式を見比べることによって、ax+py=1には、(x,y)=(s,-t)という特殊解が存在することがわかりました。
また、「a,2a,3a,……,(p-1)aをpで割ったあまりはすべて相異なる」ことと、「a,2a,3a,……,(p-1)aをpで割ったあまりには1からp-1までの(p-1)種類の数がそれぞれ一回だけ登場する」ことを考えると、mod pの世界では、
{a,2a,3a,……,(p-1)a}の集合と、{1,2,3,……,p-1}の集合は合同であることがわかります。
要素を全部掛け合わせてしまえば、
(p-1)!a^(p-1)≡(p-1)!
ですから、(p-1)!で両辺割れば
a^(p-1)≡1
となります。これをフェルマーの小定理といいます。
これを、
a*a^(p-2)≡1と変形して、
ax≡1と見比べたら、
a^(p-2)が逆元であることがわかりました。嬉しい！
