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

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

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

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

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

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

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

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

そこで思うわけですよ

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

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

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

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

2. 環

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

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


ゼロ元の存在	ある $δ \in R$ が、全ての $a \in R$ に対し $a + δ = δ + a = a$ を満たす	このような $δ$ をゼロ元(zero element)と呼ぶ
単位元の存在	ある $ε \in R$ が、全ての $a \in R$ に対し $a \times ε = ε \times a = a$ を満たす	このような $ε$ を単位元(identity element)と呼ぶ
和の可換	全ての $a, b \in R$ に対し $a + b = b + a$ を満たす
和の逆元の存在	全ての $a \in R$ に対しある $x \in R$ が存在し $a + x = δ$ を満たす	このような $x$ を和の逆元(inverse element)や反数(opposite)と呼び、 $- a$ と書く
和の結合法則	全ての $a, b, c \in R$ に対し $(a + b) + c = a + (b + c)$ を満たす
積の結合法則	全ての $a, b, c \in R$ に対し $(a \times b) \times c = a \times (b \times c)$ を満たす
分配法則	全ての $a, b, c \in R$ に対し $a \times (b + c) = a \times b + a \times c$ と $(a + b) \times c = a \times c + b \times c$ を満たす

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

ゼロ元の存在

\exists δ \in R, \forall a \in R, a + δ = δ + a = a

(ある $δ \in R$ が存在して、全ての $a \in R$ に対し $a + δ = δ + a = a$ を満たす)
足し算において $0$ とは、どれに足しても足されても変化がないですよね。
足し算が要請するものはそのような、 $0$ に相当する元の存在です！

単位元の存在

\exists ε \in R, \forall a \in R, a \times ε = ε \times a = a

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

和の可換

\forall a, b \in R, a + b = b + a

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

和の逆元の存在

\forall a \in R, \exists x \in R, a + x = δ

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

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

じゃあ和についての $1$ の逆元は…？　
単位元が $0$ だから、 $1 + x = 0 = x + 1$ が成り立つような $x$ ・・・　 $- 1$ ですね！
同様に $2$ の逆元は $- 2$ 、 $- 3$ の逆元は $3$ ・・・そんな感じですよ！

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

\forall a, b, c \in R, (a + b) + c = a + (b + c)

(全ての $a, b, c \in R$ に対し $(a + b) + c = a + (b + c)$ を満たす)

\forall a, b, c \in R, (a \times b) \times c = a \times (b \times c)

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

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

分配法則

\forall a, b, c \in R, a \times (b + c) = a \times b + a \times c

(全ての $a, b, c \in R$ に対し $a \times (b + c) = a \times b + a \times c$ を満たす)

\forall a, b, c \in R, (a + b) \times c = a \times c + b \times c

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

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

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


ゼロ元の存在	$0 \in Z$ が、全ての $a \in Z$ に対し $a + 0 = 0 + a = a$ を満たす
単位元の存在	$1 \in Z$ が、全ての $a \in Z$ に対し $a \times 1 = 1 \times a = a$ を満たす
和の可換	全ての $a, b \in Z$ に対し $a + b = b + a$ を満たす
和の逆元の存在	全ての $a \in Z$ に対し $- a \in Z$ が存在し $a + (- a) = 0$ を満たす
和の結合法則	全ての $a, b, c \in Z$ に対し $(a + b) + c = a + (b + c)$ を満たす
積の結合法則	全ての $a, b, c \in Z$ に対し $(a \times b) \times c = a \times (b \times c)$ を満たす
分配法則	全ての $a, b, c \in Z$ に対し $a \times (b + c) = a \times b + a \times c$ と $(a + b) \times c = a \times c + b \times c$ を満たす

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

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

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

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

3. 可換環

環の７条件に加え、


積の可換	全ての $a, b \in R$ に対し $a \times b = b \times a$ を満たす

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

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

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

4. 可逆元

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

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


積の逆元	$a \in R$ に対しある $x \in R$ が存在し $a \times x = x \times a = ε$ を満たす

このとき $x$ のことを $a$ の(積の)逆元(inverse element)といい、 $a^{- 1}$ と書きます。
そして $a$ のことを(積の)逆元をもつ元、可逆元(invertible element)と呼びます！

たとえば整数環においては、可逆元は $1$ と $- 1$ です。
他の元には逆元はありません。 $\frac{1}{2}$ は整数じゃないしね。

環 $R$ の可逆元を全部集めたものを $R^{\times}$ と書きます。 $Z^{\times} = {1, - 1}$ ですね。

5. 体

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


非零環	$R$ は ${0}$ ではない
可換環	$(R, +, \times)$ は可換環である
逆元の存在	$R$ の可逆元は零元を除くすべての元である。	つまり、 $R^{\times} = R ∖ {0}$

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

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

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

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

ゼロ元と単位元が同一
ゼロ元が可逆

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

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

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

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

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

Z / n Z は 体 で あ る \Leftrightarrow n は 素 数 で あ る

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

$n$ が素数のとき、 $n \geq 2$ より $Z / n Z \neq = {\overset{ˉ}{0}}$ であり、 $Z / n Z$ は可換環であり、 $\overset{ˉ}{0}$ 以外には逆元がある( $∵$ Fermatの小定理)ため、体である。

$n = 1$ のとき、 $Z / n Z$ は零環であるため体ではない。

$n$ が合成数のとき、 $n = a \times b$ を満たす $1 < a, b < n$ が存在する。
$\overset{a}{ˉ}$ に $Z / n Z$ の何かをかけて得られる数は $\overset{a}{ˉ}, \overset{ˉ}{2 a}, . . ., \overset{n}{ˉ} (= \overset{ˉ}{0})$ のみであって、 $\overset{ˉ}{1}$ にはならない。なので逆元が存在しないため $\overset{a}{ˉ}$ が可逆元ではない。従って体の定義を満たさない。^[6]

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

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

このような体となる $Z / p Z$ のことを「 $p$ 元体」と言って、 $F_{p}$ と書きます。
$F_{p} = Z / p Z$ だ

7. フェルマーの小定理

では実際に $\overset{a}{ˉ} \in Z / p Z$ の逆元はどう取ればいいのでしょう？
これは体を知らない競技プログラマーでも知ってる人が多いでしょう。


Fermatの小定理	$p$ が素数、 $g c d (a, p) = 1$ のとき、 $a^{p - 1} \equiv 1 (m o d p)$

以下、 $p$ を法とします。
$a^{p - 1} \equiv 1$ ということなので、 $a \times a^{p - 2} \equiv a^{p - 2} \times a \equiv 1$ が成り立ちますね。
ここで可逆元で話した逆元の定義を思い出します。
なんか $a^{p - 2}$ がまんま当てはまってそうですね！？

じゃあ実際に･･･そうですね、 $F_{7}$ くらいで試してみましょう

$a$	$a^{7 - 2}$	$a \times a^{7 - 2}$
$1$	$1 (\equiv 1)$	$1$
$2$	$4 (\equiv 32)$	$1$
$3$	$5 (\equiv 243)$	$1$
$4$	$2 (\equiv 1, 024)$	$1$
$5$	$3 (\equiv 3, 125)$	$1$
$6$	$6 (\equiv 7, 776)$	$1$

お？

$a^{p - 2}$ が「 $a$ にかけると1になる元」として機能しているではありませんか？！
可換環での掛け算は定義と可換則より、離れたところに $a$ と $a^{p - 2}$ があったとしても持ってきて打ち消し合うことができます！
つまり、 $a^{p - 2}$ は真に $\frac{1}{a}$ として機能している、ということになります！

なので、 $F_{p}$ での $a$ の逆元が欲しかったら $a^{p - 2}$ を計算すればいいということです！
これを愚直に求めると時間計算量 $O (p)$ かかりますが、繰り返し二乗法などによって $O (l o g p)$ まで速くできます！

ちなみに、 $2^{1, 000, 000, 005}$ を $p = 1, 000, 000, 007$ で割ったあまり、すなわち $p = 1, 000, 000, 007$ のとき $2$ の逆元は $500, 000, 004$ です。つまり

らんま500000004
— こたつがめ (@kotatsugame_t) March 27, 2020

こういうことです。

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

$1, 000, 000, 007$ に似たような場面で $998, 244, 353$ を見たことがある人もいるでしょう。
これも $1, 000, 000, 007$ と同じく $1, 000, 000, 000 = 1 0^{9}$ の近くにある素数です。これも余りを取らせるために使われますね。

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

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

998, 244, 35 3_{10} = 11101110000000000000000000000 1_{2}

0ばっかじゃん！

そうです、 $998, 244, 353$ というのは $119 \times 2^{23} + 1$ のことで、こうすることで $2$ 乗根()、 $4$ 乗根、 $8$ 乗根･･･ $2^{23}$ 乗根を取れるようになります。これは $1, 000, 000, 007$ にはできない芸当です。

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

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

traPのメンバーは大半が情報と名のつく学院･学系に所属しています。現時点で数学系のtraPメンバーは1%くらいです。つい最近までM1数学の人がいましたが、消し飛びました。 ↩︎
環の外に行くと可換が必要じゃないときもあるよ。右逆元・左逆元というやつ ↩︎ ↩︎
零環ってセグ木に乗るんですね。言われてみれば当たり前ですが、tatyamに言われて初めて気付きました。 ↩︎
可換環！可換環！可換カンカンカカンカン！ ↩︎
体にする場合もあるらしい ↩︎
もしかしたらこの証明、数学的誤りがあるかも(小声) ↩︎
本当は $Z / n Z = {0, 1, . . ., n - 1}$ とするのは激ヤバ行為です。この記事の想定ターゲットはイデアルや同値類を知らない人にしており、かつそれらの導入は大変だから省略しました。イデアル･同値類を知らないあなたへ、とりあえずバーをつければ、つまり $Z / n Z = {\overset{ˉ}{0}, \overset{ˉ}{1}, . . ., \overset{ˉ}{n - 1}}$ とすれば許されると理解して下さい。 ↩︎

9. おわりに

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

計算を体の上でさせたいから
体の上で計算すると、逆元を取ることができるから

です。

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

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

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

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

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

2. 環

ゼロ元の存在

単位元の存在

和の可換

和の逆元の存在

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

分配法則

3. 可換環

4. 可逆元

5. 体

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

7. フェルマーの小定理

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

9. おわりに

関連する記事

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

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

2. 環

ゼロ元の存在

単位元の存在

和の可換

和の逆元の存在

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

分配法則

3. 可換環

4. 可逆元

5. 体

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

7. フェルマーの小定理

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

9. おわりに

この記事をシェア

関連する記事

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