feature image

2020年12月10日 | ブログ記事

1,000,000,007 is 何??? ~体・四則演算を定義せよ~【AdC2020 27日目】

東工大では毎年3月末に1年生(+α)を対象に系所属(進振り)があり、その結果僕は数学系にぶち込まれ所属することになりました。いや知ってたけどさ、この系マジで数学しかやんねえなオイ

…ということで東京工業大学 理学院数学系2年[1] すく(@0214sh7)と申します。

この記事はアドベントカレンダー2020 27日目の記事です

去年のアドカレではう し た ぷ に き あ く ん 笑でロリハをする記事を書きました。
その記事はこちら

1. そんで1,000,000,007って何なのさ

競技プログラミングをやってる人ならば一度は必ず見たことがあるであろう謎の数字、「」。
この数はより大きい最小の素数なんですが、多くの状況においてこの数字を割った余りを求めさせるために登場する数ですね。

せっかくという数がありながら何故このような中途半端な数字で割った余りを取らせるのか!?という疑問を一度は持った人も多いのではないのでしょうか。

お答えします。で割った余りを取ること、それはつまり「体(たい)で計算すること」です!
体で計算すると何が良いのかというと、それはずばり「(0割りを除いて)常に割り算ができること」です!!

そこで思うわけですよ


「待てよ、割り算って何だ??」


んなこと思うわけねえだろ
ということでこの記事では体、すなわち割り算を定義してそれがとどのように関係するのかに触れていきます!

ですがその過程では他の四則演算(和、差、積)、すなわち環がどういうものであるのかにも触れなくてはいけないでしょう。体を定義する前に環の定義から入りましょう。

⚠注意⚠
ここからガチガチの大学数学が登場します。もしそういうのは全くわからない、結論だけ寄越せという人は6. Z/nZ、汝は体なりや?までジャンプして下さい。

2. 環

足し算って色々ありますよね。みんなお馴染み自然数の足し算、その拡張である整数・有理数・実数・複素数の足し算、それから行列の足し算など・・・。掛け算も同様に色々あります。

環(ring) というのは簡単に言うと、「足し算と掛け算がどうあるべきか」を定めるものです。これが成り立ってないと「足し算・掛け算としてふさわしい」とは言えないわけです。
集合(実数集合とは異なるよ!)と、上で定義されている演算が以下の定義を満たしているとき、であるといいます。

ゼロ元の存在 あるが、全てのに対し を満たす このようなをゼロ元(zero element)と呼ぶ
単位元の存在 あるが、全てのに対し を満たす このようなを単位元(identity element)と呼ぶ
和の可換 全てのに対し を満たす
和の逆元の存在 全てのに対しあるが存在しを満たす このようなを和の逆元(inverse element)や反数(opposite)と呼び、と書く
和の結合法則 全てのに対し を満たす
積の結合法則 全てのに対し を満たす
分配法則 全てのに対し を満たす

ひとつひとつ見ていきましょう。

ゼロ元の存在

(あるが存在して、全てのに対し を満たす)
足し算においてとは、どれに足しても足されても変化がないですよね。
足し算が要請するものはそのような、に相当する元の存在です!

単位元の存在

(あるが存在して、全てのに対し を満たす)
同様に掛け算においては、どれに掛けても掛けられても変化がないですね。
これが存在することも掛け算という演算に要請されます!

和の可換

(全てのに対し を満たす)
小学校でたびたび問題になる可換問題、環においては足し算にのみ可換、すなわち項を入れ替えても必ず結果が一緒になることが求められます!
一方、掛け算については必ずしも可換ではなくてもいいんですね。
積についても可換であるような環を特別に可換環と呼びますが、後述します。

和の逆元の存在

(全てのに対しあるが存在しを満たす)
逆元というのは単位元の存在と、演算の可換が成立して初めて存在に触れることができます。[2]

皆さんが逆元と聞くとに対するを最初に想起するのではないでしょうか?
そのイメージです。ある元の逆元とは、に掛けたり掛けられたりすると単位元になる、そんな元です!イメージでは積の逆元が浮かびがちですが、和でも同じことが言えるんです!

じゃあ和についてのの逆元は…? 
単位元がだから、が成り立つような・・・ ですね!
同様にの逆元はの逆元は・・・そんな感じですよ!

和の結合法則・積の結合法則

(全てのに対し を満たす)

(全てのに対し を満たす)
結合法則とはずばり「演算の順序を気にしない」こと。
足し算掛け算の特徴として、みたいに項が複数あったときどこから計算しても結果が同じというものがありますね。
アレです。アレが定義として要請されていたのです。

セグ木をご存知の方はモノイドという言葉を一度は聞いたことでしょう。
モノイドはこの結合法則と、単位元の存在の2つが成り立ったときの演算を指します!
なのでどのような集合であっても、演算が足し算・掛け算である限りは必ずモノイドになります!

分配法則

(全てのに対し を満たす)

(全てのに対し を満たす)
カッコで結ばれてる足し算と掛け算をバラしても結果が一緒になる、ってやつですね。(説明をサボったときの音)
偶然成り立ってたような顔をしていますが、実は環としては定義レベルで要請されている性質だったんですね!

これら7つの条件をすべて満たすとき、その演算を和、積と言うわけなんですね!

たとえば整数の集合に普通の和と積をのせたものは環です。なぜなら、

ゼロ元の存在 が、全てのに対し を満たす
単位元の存在 が、全てのに対し を満たす
和の可換 全てのに対し を満たす
和の逆元の存在 全てのに対しが存在しを満たす
和の結合法則 全てのに対し を満たす
積の結合法則 全てのに対し を満たす
分配法則 全てのに対し を満たす

なので、皆さんご存知の整数の足し算・掛け算は「足し算・掛け算としてふさわしい」ということになります!

ほかにも、有理数全体、実数全体、複素数全体に普通のをのせたやつも環ですね。
正方行列(行と列が同じサイズの行列)に普通のと行列積をのせたやつも環です。

意外なところだと、(0だけの集合)に,で定義されるをのせたやつも実は環です。おお直感に反しますね。
これは零環(zero ring) といって、環の定義には含めない人もいます。[3]

一方、自然数全体に普通のをのせたものは環ではないです。4番目の「和の逆元の存在」に反しますからね。(胡蝶しのぶ)

3. 可換環

環の7条件に加え、

積の可換 全てのに対し を満たす

これを満たすものを可換環(カカンカン、commutative ring)といいます。
オリエンタルラジオのリズム芸、なんだっけ?[4]

整数、有理数、実数、複素数に普通のをのせたやつはみんな環であり、可換環ですね。
零環も可換環です。
一方、正方行列(行と列が同じサイズの行列)に普通のと行列積をのせたやつは環だけど可換環ではないです。行列積は可換じゃないんだよね

先程チラッと言いましたが、逆元の存在に触れるためには単位元があることと、演算が可換であることが必要なんです![2:1]
可換環であって初めて、積についての逆元に触れることができます!

4. 可逆元

環というのは、足し算と掛け算(あとついでに和の逆元からおのずと生えてくる)引き算ができるものを指しているんですね。

さて四則演算の残り一つ、割り算は?
…実は環の定義は割り算をできることを保証していません。
じゃ…(割り算)しよっか。

積の逆元 に対しあるが存在しを満たす

このときのことをの(積の)逆元(inverse element)といい、と書きます。
そしてのことを(積の)逆元をもつ元、可逆元(invertible element)と呼びます!

たとえば整数環においては、可逆元はです。
他の元には逆元はありません。は整数じゃないしね。

の可逆元を全部集めたものをと書きます。ですね。

5. 体

でも有理数環においては以外の全ての元が逆元を持っています。
実数環、複素数環でも同じです。そこで…

非零環 ではない
可換環 は可換環である
逆元の存在 の可逆元は零元を除くすべての元である。 つまり、

の3つをすべて満たしているとき、であるといいます。
(field)というのは簡単に言うと、「四則演算がどうあるべきか」を定めるものです。

有理数、実数、複素数に普通のをのせたやつはみんな環であり、可換環であり、体ですね。
実際こいつらは(ゼロ割りを除き)自由に割り算ができますね。そういうのが体です。
定義も(零環じゃないとして)、可換環(和・差・積が自由にできる)に逆元(商が自由にできる)をくっつけた感じだし。

整数は可換環だけど体じゃないですね。まあ一応割り算は定義できるけど、あれ掛け算しても戻るとは限らんし・・・

零環は可換環だけど体ではないです。[5]
環の定義を踏まえて零環を見ると、

が成り立つんですね(これが成り立つのは零環のみ)。これはあんまりよくない性質を導いちゃうので、定義レベルで外すことが多いです。




6. Z/nZ、汝は体なりや?

(ジャンプした人も余裕があったら上の読んでほしい、頑張って書いたから)


そして皆さんお待たせしました!剰余環 について触れていこうと思います!
実は(に普通の足し算と掛け算を乗せたもの)は常に体というわけではなく、条件付きで体になります。その条件がコチラ!!

nを自然数とする。このとき、

簡単な証明(クリックで開く)

が素数のとき、よりであり、は可換環であり、以外には逆元がある(Fermatの小定理)ため、体である。

のとき、は零環であるため体ではない。

が合成数のとき、を満たす が存在する。
の何かをかけて得られる数はのみであって、にはならない。なので逆元が存在しないためが可逆元ではない。従って体の定義を満たさない。[6]

この証明に出てきた意味深なバー、なんでしょうね・・・?フフフ[7]


なので、が体になる、つまりで自由に割り算をするための条件は が素数であること というわけです!

このような体となるのことを「元体」と言って、と書きます。

7. フェルマーの小定理

では実際にの逆元はどう取ればいいのでしょう?
これは体を知らない競技プログラマーでも知ってる人が多いでしょう。

Fermatの小定理 が素数、のとき、

以下、を法とします。
ということなので、が成り立ちますね。
ここで可逆元で話した逆元の定義を思い出します。
なんかがまんま当てはまってそうですね!?

じゃあ実際に・・・そうですね、くらいで試してみましょう

お?

が「にかけると1になる元」として機能しているではありませんか?!
可換環での掛け算は定義可換則より、離れたところにがあったとしても持ってきて打ち消し合うことができます!
つまり、は真にとして機能している、ということになります!

なので、でのの逆元が欲しかったらを計算すればいいということです!
これを愚直に求めると時間計算量かかりますが、繰り返し二乗法などによってまで速くできます!

ちなみに、で割ったあまり、すなわちのときの逆元はです。つまり

らんま500000004

— こたつがめ (@kotatsugame_t) March 27, 2020

こういうことです。


8. おまけ:998,244,353 is 何???

に似たような場面でを見たことがある人もいるでしょう。
これもと同じくの近くにある素数です。これも余りを取らせるために使われますね。

せっかくという素数がありながら何故このような綺麗でもない素数で割った余りを取らせるのか!?という疑問を一度は持った人も多いのではないのでしょうか。

お答えします。わざわざを持ってくることで得られるアドは2進数表記にすると見えてきます。

0ばっかじゃん!

そうです、というのはのことで、こうすることで乗根()、乗根、乗根・・・乗根を取れるようになります。これはにはできない芸当です。

とりあえずここまでにします。あなたがNTT(整数環FFT)を勉強したいと思ったとき、再びあなたの前に姿を現すでしょう。

よくわからなかった?じゃあの剰余は体よりいい性質を持つ「スーパー体」ということで…(は?)


  1. traPのメンバーは大半が情報と名のつく学院・学系に所属しています。現時点で数学系のtraPメンバーは1%くらいです。つい最近までM1数学の人がいましたが、消し飛びました。 ↩︎

  2. 環の外に行くと可換が必要じゃないときもあるよ。右逆元・左逆元というやつ ↩︎ ↩︎

  3. 零環ってセグ木に乗るんですね。言われてみれば当たり前ですが、tatyamに言われて初めて気付きました。 ↩︎

  4. 可換環!可換環!可換カンカンカカンカン! ↩︎

  5. 体にする場合もあるらしい ↩︎

  6. もしかしたらこの証明、数学的誤りがあるかも(小声) ↩︎

  7. 本当はとするのは激ヤバ行為です。この記事の想定ターゲットはイデアルや同値類を知らない人にしており、かつそれらの導入は大変だから省略しました。イデアル・同値類を知らないあなたへ、とりあえずバーをつければ、つまりとすれば許されると理解して下さい。 ↩︎

9. おわりに

いかがでしたか?
でもよさそうなのにわざわざなんかで割ったあまりを取らせる理由は

です。

ただし、オーバーフロー回避のためだけにmodをとらせている場合もあります。
この場合、可換環で十分なので体である必要はなくでも機能しますが、逆元が必要ないことを暗に伝えてしまうため、あえてにしています。
一部のWriterがで機能する場面でを使わせる最大の理由がこれ。modにを採用することでNTTが必要ないことを暗に伝えてしまうことを防ぐ意図があります。

以上、すく(@0214sh7)でした!


明日のアドカレの担当者は@mazrean です。
せきゅきゃん△の話が聞けるぞ~楽しみ~

0214sh7 icon
この記事を書いた人
0214sh7

きいろこーだー アルゴリズム班の元班長さんです

この記事をシェア

このエントリーをはてなブックマークに追加
共有

関連する記事

2017年11月14日
IBIS2017参加報告
Keijan icon Keijan
2023年7月13日
アルゴリズム班はやとき王選手権「競(けい)プロ」を開催しました!
abap34 icon abap34
2021年4月18日
ベズー係数とN項の拡張ユークリッドの互除法
0214sh7 icon 0214sh7
2023年4月29日
CPCTF2023 PPC作問陣 Writeup
noya2 icon noya2
2023年4月21日
CPCTFを開催します
noc7t icon noc7t
2022年8月30日
【競プロer向け】母関数を習得しよう!
tatyam icon tatyam
記事一覧 タグ一覧 Google アナリティクスについて 特定商取引法に基づく表記