有理数 mod は有理数 mod じゃないよという話

$\require{AMScd}$

有理数 mod p

競技プログラミングでよく聞かれる、有理数を$\bmod 998244353$ などで出力させる問題について、数学的な解釈をします。

「有理数 mod p と呼ばれるものが何なのか、数学的に厳密に構造を観察してみた」

こちらが正しい気がしてきました。

有理数 mod p を理解できていない人に誤解させない説明をという意図なら、環論は (数学から競プロに入った一部の人を除いて) 難しすぎるのではないでしょうか。「有理数 mod p と呼ばれるものが何なのか、数学的に厳密に構造を観察してみた」みたいなモチベーションなら理解できます。

— 熨斗袋 (@noshi91) April 18, 2023

お気持ち

（ここは後で消す）
TL に流れてきた「有理数 mod」の説明を見ると、分母の制約に言及せず、有理数なら必ず$\bmod p$ が取れるような誤解を与えかねない説明が見受けられたので、もう少し厳密に説明したいというお気持ちがありました。

結論

• 「有理数$\bmod p$」はできないよ
• 「有理数もどき（後述）$\bmod p$」ならできるよ

整数 mod p

有理数の話の前にまず整数を$\bmod p$ で答えるところを考えましょう。環などの導入をしますが、環論を知ってる人には冗長だと思うので飛ばしちゃって大丈夫です。$\bmod p$ ってなんだ？という声があるかもしれませんが、ざっくり言うと

$\bmod p$ で考えるとは、 $p$ の倍数の差を同一視すること

です。詳細は後述します。

環とイデアル

$R$ ¹ を 可換環 とします。本記事では、単に環というと $1$ を持つ可換環を表します。

$I\subset R$ が $R$ のイデアルであるとは、次を満たすことをいいます。

• $I$ は加法群である ²
• $\forall a\in I,\ r\in R$ について $ar \in I$

素イデアル

環 $R$ のイデアル $P$ が次の条件を満たすとき、素イデアルであるといいます。

• $1\notin P$
• $ab \in P \implies a \in P\ \mathrm{or}\ b \in P$

イデアルによる同値類と剰余環

$R$ のイデアル $I$ が与えられているとき、 $R$ に二項関係 $\sim$ を $a \sim b \iff a - b\in I$ で定めると、これは 同値関係 になります。 $a$ を代表元とする同値類を $a+I$ と表します。
また $R$ を同値関係 $\sim$ で割った商集合 $R/\sim$ には自然に演算 $+$ および $*$ が定義されて環になることが確認できます。

R/～ が環になる証明

Well-defined

環であることを確認する前に、まず和と積を定義する必要があります。まず和について、 $a+I$ と $b+I$ の和を $(a+b)+I$ と定めたいです。ここで問題なのは、 $a+I$ は代表元による表し方なので、他の表し方（例えば $a'+I$ ）もあるかもしれません。表し方によって結果が変わったら定義にならないですね。でも実はこれは定義になっている（ well-defined である）ことが次の主張から分かります。

主張：$a\sim a'$ かつ $b\sim b'$ であるとき $a+b \sim a'+b'$

主張の証明をします。まず $a\sim a'$ から $a-a' \in I$ です。同様に $b-b' \in I$ です。イデアルの性質から $(a-a') + (b-b') \in I$ すなわち $(a+b)-(a'+b') \in I$ ですが、これは $a+b \sim a'+b'$ を示しています■

積についても $a+I$ と $b+I$ の積を $ab+I$ と定義したいです。和のときと同様に $a\sim a'$ かつ $b\sim b'$ なら $ab \sim a'b'$ が言えるので、定義できているることが分かります。

和について

和について、交換則・結合則・零元の存在・逆元の存在を示す必要があります。前ふたつは簡単です。零元は $0+I$ が満たします。これは $(0+I) + (a+I) = a+I$ であることから分かります。また $a+I$ の加法逆元として $(-a) + I$ があることが分かります。

積について

積について、交換則・結合則・単位元の存在を示す必要がありますが、これも簡単です。単位元は $1+I$ です。

分配法則について

（well-defined である前提のもと計算すると）簡単に示せます。

以上より $R/\sim$ に上記の方法で定義した和・積を定めると環になることが分かります。この環 ³ を、 $R$ のイデアル $I$ による剰余環といい、 $R/I$ と書きます。

全射準同型

$I$ を $R$ のイデアルとします。このとき $R$ から $R/I$ への写像 $f:R\to R/I$
を $f(a)=a+I$ で定めると、これは全射な環準同型になります。
環準同型とは $f(a+b)=f(a)+f(b)$ 、 $f(ab)=f(a)f(b)$ 、 $f(0)=0$ 、 $f(1)=1$ ⁴ を満たすことです。言い換えれば、元の環での演算が $f$ で送った先での環の演算になり、かつ元の環での零元・単位元が送った先でも零元・単位元になることを言います。

整数 mod p と全射準同型

話を戻して、整数 mod 素数の意味を考えます。
整数環を $\mathbb Z$ と書きます。また $p$ を（普通の意味での）素数とします。 $p$ の倍数全体からなる集合は $\mathbb Z$ のイデアル（実は素イデアル）になります。これを $p\mathbb Z$ と書きます。（上の方法で）このイデアルによる剰余環 $\mathbb Z/p\mathbb Z$ が考えられます。
実は、整数を $\bmod p$ で答えるというのは、全射準同型 $\mathbb Z \to \mathbb Z/p\mathbb Z$ による像を答えることに相当します。ただし $\mathbb Z/p\mathbb Z$ の元は代表元 $a$ として $0\le a\lt p$ から取ることにします。

整数$\bmod p$ は、全射準同型 $\mathbb Z \to \mathbb Z/p\mathbb Z$ による像

競技プログラミングでは、代表元を $0\le a\le p$ に取ったものを答えさせる問題と考えることができます。

商環

有理数（もどき）を作るために、商環を定義します。

積閉集合

環 $R$ の部分集合 $S$ が積閉集合であるとは、次が成立すること。

• $1\in S$
• $\forall a,\ b \in S$ について $ab \in S$

商環

まず環 $R$ およびその積閉集合 $S$ の元からなるタプル $\{(r,\ s)\ |\ r\in R,\ s \in S\}$ に同値関係 $\sim$ を次で定めます。

$(r_1,\ s_1) \sim (r_2,\ s_2) \iff \exists\ t\in S\ s.t.\ t(r_1s_2-r_2s_1)=0$

ここで $(r,\ s)$ の同値類を（分数の形で） $r/s$ のように表しましょう。さらに（通常の分数が満たすように） $a/s+b/t=(at+bs)/st$ 、 $(a/s)(b/t)=ab/st$ のように和および積を定義すると、これは環になることが確認できます。この環を $R$ の $S$ による局所化あるいは商環といい、 $S^{-1}R$ と書きます。

「局所化」とは分数を考えること

有理数 mod p

前置きが長くなりましたが、そろそろ有理数 mod p の話にいきたいです。先に言っておくと、有理数 mod p を定義することはできません（！）。

Z → Q

$\mathbb Z$ の積閉集合として $S=\{a \in \mathbb Z\ |\ a\neq 0\}$ を取ります。このとき $S^{-1}\mathbb Z$ は有理数体 $\mathbb Q$ と同型になります。

整数を非零集合で局所化すると有理数

Z → Zp

$\mathbb Z$ の部分集合 $S=\{a \in \mathbb Z\ |\ a\ は\ p\ で割り切れない\}$ を考えます。 $S$ は積閉集合であることが確認できます。このとき $S^{-1}\mathbb Z$ は、分母が $p$ の倍数でない（既約）分数全体からなる集合（に通常の和・積を定義した環）になります。これを $\mathbb Z_{(p)}$ と書きます。 $\mathbb Z_{(p)}$ は $\mathbb Q$ の真部分集合です。 $\mathbb Z_{(p)}$ は有理数全体から分母が $p$ の倍数である分数を除いたようなものです。有理数から一部欠けているというニュアンスで「有理数もどき」と呼びましょう ⁵ 。

整数を「非 $p$ の倍数」で局所化すると有理数もどき

Q vs Zp

「有理数もどき」の集合は「有理数」全体と比べると若干小さくなっています。

有理数もどき mod p

$\mathbb Z_{(p)}$ は集合としては $\{a/s \ |\ a\in \mathbb Z,\ s\in \mathbb Z,\ s\ は\ p\ で割り切れない \}$ と書けます。 $\{a/s \ |\ a\in \mathbb Z,\ s\in \mathbb Z,\ s\ は\ p\ で割り切れない,\ a\ は p で割り切れる \}$ を考えると、これは $\mathbb Z_{(p)}$ の素イデアルになることが分かるので、これを $p\mathbb Z_{(p)}$ と書きます。このイデアルによる剰余環を $X=\mathbb Z_{(p)}/p\mathbb Z_{(p)}$ と書きます。実はこの $X$ こそが競技プログラミングで聞かれる「有理数$\bmod p$ 」と呼ばれているものの正体です！

X

剰余環を取る操作と局所化は可換であることが知られています。具体的には次のような可換図式が成立します。この右下のものが $X$ です。

\begin{CD}
\mathbb Z @>\bmod p>> \mathbb Z/p\mathbb Z \\
@V 局所化 VV @V 局所化　VV  \\
\mathbb Z_{(p)} @> \bmod p >>\mathbb Z_{(p)}/p\mathbb Z_{(p)}
\end{CD}

左下ルートと右上ルート

本記事の流れでは、 $X$ は 左上→左下→右下 という流れで説明しましたが、左上→右上→右下 と考えてみましょう。
右上の $\mathbb Z/p\mathbb Z$ は体なので、局所化しても構造は変わりません。つまり右下の $\mathbb Z_{(p)}/p\mathbb Z_{(p)}$ も通常の整数を$\bmod p$ で表した $\mathbb Z/p\mathbb Z$ とみることができる ⁶ ことが分かりました。

右上ルートによる別定義

右上ルートを別の考え方で見るために、期待値の例を考えてみましょう。整数値を取る離散確率変数 $X$ があるとします。この確率変数の期待値は $$E(X)=\displaystyle\sum_{x\in \mathbb Z}\ x * \mathbb{prob}(X=x)\quad\quad (1)$$ と定義されますね。ここでもし $X$ が整数値ではなく $\mathbb Z/p\mathbb Z$ 上の値を取る確率変数であればどうなるでしょうか？確率 $\mathbb{prob}(X=x)$ が $\mathbb Z/p\mathbb Z$ の元であれば ⁷ $$E(X)=\displaystyle\sum_{x\in \mathbb Z/p\mathbb Z}\ x * \mathbb{prob}(X=x)\quad\quad (2)$$ が定義されます ⁸ 。 $(2)$ は $(1)$ の$\bmod p$ を取ったものに相当します。つまり期待値$\bmod p$ を取ったものを考えることは、確率を最初から$\bmod p$ で考えれば、普通に（上式の意味で）期待値を取ったものを考えることに相当します。この考え方（右上ルート方式）だと局所化が不要になりましたね。

まとめ

競技プログラミングでよく出てくる整数$\bmod p$ を答えさせる問題は、全射準同型 $\mathbb Z \to \mathbb Z/p\mathbb Z$ の像を求める問題と言うことができます。
有理数についても$\bmod p$ で答えさせる問題があるが、厳密には「有理数$\bmod p$ 」は定義できません。有理数のうち分母が $p$ の倍数にならないものを「有理数もどき」と言うことにすると、「有理数もどき$\bmod p$ 」なら定義できます。これは $\mathbb Z_{(p)} \to \mathbb Z_{(p)}/p\mathbb Z_{(p)} \sim \mathbb Z/p\mathbb Z$ の像を答えさせる問題と言うことができます。

まだ

まだ編集中なのであとで変わるかもです。おかしなところなどあれば教えてください。

1. 厳密には、集合・加法の演算・乗法の演算・加法の単位元・乗法の単位元の 5 タプルからなる $(R,+,*,0,1)$ ↩

2. つまり $I$ は $R$ の演算 $+$ について閉じていて、かつこの演算について群をなす ↩

3. 厳密には $(R/\sim, +, *,0+I,1+I)$ の 5 タプル ↩

4. 左辺の $0$ や $1$ と右辺の $0$ や $1$ はどちらも零元・単位元ではあるものの、考えている環が異なるので別の概念であることに注意する必要がある。 ↩

5. この記事の中のみでの呼び方です。 ↩

6. 同型である ↩

7. 言い換えれば、確率の分母が $p$ の倍数にならなければ ↩

8. 通常の確率の定義の方法とは異なります。 ↩