F - Tangent Addition Formula 解説
by 
maspy
ヒント → https://atcoder.jp/contests/arc166/editorial/7181
集合 \(\{0,1,\ldots,p-1\}\) に \(p\) を法とする四則演算を定めたものを， \(\mathbb{F}_p\) と書くことにします．また，\(\mathbb{F}_p^{\times}=\mathbb{F}_p\setminus \{0\}\) と書きます．
\(t\) が満たすべき等式
\[t(x+y)\bigl(1-t(x)t(y)\bigr)=t(x)+t(y) \tag{★}\]
を以下，(★) として参照します．
[0] この問題・解説の背景
この問題では，関数 \(t(x) = \tan(x)\) が満たす等式 (★) が題材となっています．\(\tan(x)\) は実数値をとる関数なので，この関数をそのまま \(\mathbb{F}_p\) 値の関数として解釈することはできません．「\(\tan(x)\) の \(\mathbb{F}_p\) 値版のようなもの」を調べることがが求められています．
複素指数関数を用いると，実数 \(x\) に対して
\[\tan(x)=\dfrac{\sin(x)}{\cos(x)}=\dfrac{(e^{ix}-e^{-ix})/(2i)}{(e^{ix}+e^{-ix})/2} = i\cdot\dfrac{1-e^{2ix}}{1+e^{2ix}}\]
と書くことが出来ます．特にある \(r\) に対して \(\tan(x)=i\cdot \dfrac{1-r^x}{1+r^x}\) 書けることが分かります．このことに基づいて，以下では \(\mathbb{F}_p\) 値の場合にも，\(t(x) = i\cdot \dfrac{1-r^x}{1+r^x}\) となる \(i, r\) が存在するという結論（ただし一部例外もあります）を目指して議論します．
[1] \(p=2\) のとき
定数列 \(t=(0,0,0,0,0,\ldots)\) および \(t=(1,1,1,1,1,\ldots)\) が (★) を満たします．したがって，本問の答えは Yes です．
なお，\(t(x)=0\) である \(x\) 全体がどのようなものかを考えれば，(★) を満たす \(t\) は次のように分類できることも分かります：
- \(t=(0,0,0,0,0,\ldots)\)
- \(t=(1,1,1,1,1,\ldots)\)
- ある \(n\in\mathbb{Z}\) に対して，\(t(x) = \begin{cases}0 & (x\in n\mathbb{Z}) \\ 1 & (x\notin n\mathbb{Z})\end{cases}\) により定まる \(t\)．
[2] \(p\equiv 1\pmod{4}\) のとき
\(p\equiv 1\pmod{4}\) より，\(I^2=-1\) となる \(I\in \mathbb{F}_p\) が存在します．
(★) に \(x=y=0\) を代入することで \(t(0)\in \{0, I, -I\}\) であることが分かります．
[2 - 1] \(t(0)\in \{I,-I\}\) のとき
(★) に \(y=0\) を代入することで，任意の \(x\) に対して \(t(x)\in \{I, -I\}\) が成り立つことが分かります．さらに \(t(1)\) の値で場合分けをして計算すれば，\(t\) は次の \(4\) 通りであることが分かります．
- \(t = (I, I, I, I, I, \ldots)\)
- \(t = (I, -I, -I, -I, -I, \ldots)\)
- \(t = (-I, I, I, I, I, \ldots)\)
- \(t = (-I, -I, -I, -I, -I, \ldots)\)
なお本問に答える上では，\(I\) または \(-I\) からなる定数列が条件を満たすことだけ確認すれば十分です．
[2 - 2] \(t(0)=0\) かつ \(t(1)\in \{I,-I\}\) のとき
(★) において \(y=1\) とした式から \(t(x)=t(1)\in \{I,-I\}\implies t(x+1)=t(1)\) が分かります．よってこの場合，\(t\) は次の \(2\) 通りであることが分かります．
- \(t = (0, I, I, I, I, \ldots)\)
- \(t = (0, -I, -I, -I, -I, \ldots)\)
[2 - 3] \(t(0)=0\) かつ \(t(1)\notin\{I,-I\}\) のとき
\(t(1) = I\cdot \dfrac{1-r}{1+r}\) となる \(r\in \mathbb{F}_p^{\times}\) がとれます．
(★) において \(y=1\) とした式を使って順に計算することで，次が分かります．
\(r^x\neq -1\) が常に成り立つならば \(t(x) = I\cdot \dfrac{1-r^x}{1+r^x}\)．
\(r^x = -1\) となる \(x\) が存在するならば，(★) を満たす \(t\) は存在しない．
前者について，このように定まる \(t(x)\) が実際に (★) を満たすことも簡単な計算で確かめられます．
結論として，この場合には \(t\) は次のように書けるものが全てであることが分かります．
- \(r\in \mathbb{F}_p^{\times}\) であって，任意の \(x\) に対して \(r^x\neq -1\) となるものをとる．\(t(x) = I\cdot \dfrac{1-r^x}{1+r^x}\) と定める．
[3] \(p\equiv 3\pmod{4}\) のとき
[2] と同様の議論を進めることを考えます．まず \(\mathbb{F}_p\) において \(I^2=-1\) となる \(I\) は存在しないので，場合分け [2-1], [2-2] に相当する議論は不要になります．
[2-3] に相当する議論を行おうとすると，\(I^2=-1\) となる \(I \in \mathbb{F}_p\) が存在しないということが困難となります．この困難を解消する方法を考えます．これには冒頭で実関数 \(\tan(x)\) を，虚数単位や複素指数関数を用いて表したのと同様の方法を用いることができます．
Gauss 整数環の利用（有限体 \(\mathbb{F}_{p^2}\) の利用）
\(\mathbb{F}_p\) には \(i^2=-1\) を満たす数 \(i\) はありません. そこで，\(i^2=-1\) を満たす新たな数 \(i\) を考え，\(F = \{a+bi\mid a, b \in \mathbb{F}_p\}\) とします．
\(F\) には，分配法則などと \(i^2=-1\) が成り立つように演算が定まります．具体的には \(a,b,c,d\in\mathbb{F}_p\) に対して次のように加法・乗法を定めます：
- \((a+bi)+(c+di) = (a+b)+(c+d)i\).
- \((a+bi)(c+di) = (ac-bd)+(ad+bc)i\).
\(F\) は体になります．つまり，\(0\) でない元の乗法逆元が存在します（\((a,b)\neq (0,0)\) に対して \(a^2+b^2\neq 0\) であることを利用します）．
なお有限体の知識がある人は，単に \(F = \mathbb{F}_{p^2}\) ととったと考えていただければ十分です．
\(a\in \mathbb{F}_p\) を \(a+0i\in F\) に対応させることで，\(\mathbb{F}_p\subset F\) と見なします．\(F^{\times}=F\setminus\{0\}\) と書きます．
\(i=0+1i\in F\) は \(i^2=-1\) を満たし，これを \(I\) の代わりに用いることで，[2-3] とほとんど同じ議論が可能になります．
詳細は省略して，結論だけ述べます.
結論
(★) を満たす \(t\) は次のように書けるものが全てである．
- \(r\in F^{\times}\) であって，\(i\cdot \dfrac{1-r}{1+r} \in \mathbb{F}_p\) であり，任意の \(x\) に対して \(r^x\neq -1\) となるものをとる．\(t(x) = i\cdot \dfrac{1-r^x}{1+r^x}\) と定める．
このうち，\(i\cdot \dfrac{1-r}{1+r}\in \mathbb{F}_p\) という部分についてもう少し扱いやすい形にしておきます．
二項定理と \(i^p=-i\) から分かる等式 \((a+bi)^p=a-bi\) より，
\[a+bi\in \mathbb{F}_p \iff b\neq 0 \iff a+bi= a-bi\iff a+bi=(a+bi)^p\]
が成り立ちます．よって，
\[i\cdot \dfrac{1-r}{1+r}\in \mathbb{F}_p\iff i\cdot \dfrac{1-r}{1+r} = \biggl(i\cdot \dfrac{1-r}{1+r}\biggr)^p \iff \dfrac{1-r}{1+r}+\dfrac{1-r^p}{1+r^p}=0 \iff r^{p+1}=1\]
と言い換えられます．
[4] 解の存在の判定
(★) を満たす \(t\) がどのようなものであるかが完全に分かったので，改めて本問の答えを求めましょう．
[2-3], [3] の部分に対する \(t\) の存在判定ができればよいです．これらをまとめて定式化しましょう．
\(a,b\) を入力で与えられるものとします． \(F, I, m, c\) を以下のようにとります．
\(p\equiv 1\pmod{4}\) のとき，\(F=\mathbb{F}_p\)，\(I\) を [2] で定めたものとする．\(m=0\) とする．\(c\in F^{\times}\) を \(b=I\cdot \dfrac{1-c}{1+c}\) を満たすようにとる（このような \(c\) が存在しないならば解なしである）．
\(p\equiv 3\pmod{4}\) のとき，\(F\) を [3] で定めたものとする．\(m=p+1\) とする．\(c\in F^{\times}\) を \(b=i\cdot \dfrac{1-c}{1+c}\) を満たすようにとる．
解くべき問題は次のようになります：
【問題】
非負整数 \(a,m\) および \(c\in F^{\times}\) が与えられる．次を満たす \(r\in F^{\times}\) が存在するか否かを判定せよ．
- \(r^a = c\).
- \(r^m = 1\).
- 任意の \(x\) に対して \(r^x\neq -1\).
ここで次が成り立ちます：
【定理】（有限体における原始根の存在）
\(F^{\times} = F\setminus\{0\}\) は巡回群である． つまり，\(n = |F^{\times}|\) とするときある \(g \in F^{\times}\) が存在して，\(g^n=1\) かつ \(F^{\times}=\{g^k\mid 0\leq k < n\}\) が成り立つ．
\(\mathbb{F}_p\) における原始根の存在証明として恐らく最もよく知られている証明が，そのままこの定理の証明になります．
証明の概略
- 体において，因数定理が成り立つことを示す．このことから，任意の $k$ に対して方程式 $x^k=1$ の解が高々 $k$ 個であることを示す．
- 各 $d\mid n$ に対して，位数 $d$ の元 $x$ が存在するならば，1. より $1,x,\ldots,x^{d-1}$ 以外に $1$ の $d$ 乗根は存在しない．このことから位数 $d$ の元の個数が $0$ または $\phi(d)$ であることが分かる（$\phi$ は Euler 関数）．
- 位数 $d$ の元の個数を $a_d$ と書けば，$n=\sum_{d\mid n}a_d$ である．このことと 2. から分かる $a_d \in \{0,\phi(d)\}$ および Euler 関数の性質 $n=\sum_{d\mid n}\phi(d)$ から，任意の $d\mid n$ に対して $n_d=\phi(d)$ であることが分かる．特に $a_n=\phi(n)>0$ であるから原始根が存在する．
\(n = |F^{\times}| = \begin{cases}p-1 & (p\equiv 1\pmod{4}) \\ p^2-1 & (p\equiv 3\pmod{4})\end{cases}\) とします．
原始根 \(g\) をとり，\(r=g^k\) であるとします（\(g, k\) は単に議論に利用するだけで，具体的な値を計算する必要はありません）．すると，\(r^m=1\) という条件は \(n\mid km\) と言い換えられます．これは \(k\) が \(\dfrac{n}{\gcd(n,m)}\) の倍数であることと同値です．
\(r^x\neq -1\) という条件は，\(kx\not\equiv n/2\pmod{n}\) と言い換えられます．\(n = 2^en' (2\nmid n')\) と書けば，任意の \(x\) に対して \(r^x\neq-1\) となることは \(k\) が\(2^e\) の倍数であることと同値です．
\(L = \mathrm{lcm}\biggl(\dfrac{n}{\gcd(n,m)}, 2^e\biggr)\) とすれば，結局次に帰着されます：
\(a, c\) が与えられる．\(c=r^a\) かつ，\(r\) が \(L\) 乗数であるものが存在するか否かを判定せよ．
つまり， \(c\) が \(aL\) 乗数であるかを判定できればよいです．
再び \(F^{\times}\) が巡回群であることを利用すれば，この条件は \(c\) の \(\dfrac{n}{\gcd(aL,n)}\) 乗が \(1\) であることと同値です．
結局 \(c\) のべき乗の計算に帰着されて，本問題は繰り返し二乗法により \(O(\log p)\) 時間で解くことができます．
[5] 参考
行列を用いて議論することもできるので，簡単に取り上げておきます．
\(t(1)=c\) を固定すると，\(t\) は漸化式 \(t(x+1)=\dfrac{t(x)+c}{-ct(x)+1}\) という \(1\) 次分数変換の形で書けるので，\(t(x)\) を行列 \(\begin{pmatrix}1&c\\-c&1\end{pmatrix}\) の \(x\) 乗を使って表すことができます．
結局 \(\begin{pmatrix}x&-y\\y&x\end{pmatrix}\)（\(x^2+y^2\neq 0\)） という形の行列全体を，定数倍の違いを同一視して得られる群の構造を調べることに帰着できます．
この群が \(p\equiv 1,3\pmod{4}\) のどちらかであるかに応じて位数 \(p-1,p+1\) の巡回群になります．\(p\equiv 1\pmod{4}\) の場合は行列の対角化と原始根の存在から分かります．\(p\equiv 3\pmod{4}\) の場合は \(\begin{pmatrix}x&-y\\y&x\end{pmatrix}\) という形の行列全体が体になることと，体の乗法群の有限部分群が巡回群であることから証明できます（なおこのような行列を Gauss 整数 \(x+yi\) に対応させれば，この体は上の解説で登場した \(F\) と同型です）．このように行列を用いて考察した場合にも，証明には \(\mathbb{F}_p\) や \(\mathbb{F}_{p^2}\) における原始根の存在定理やそれに近い結果が必要になると考えています．
投稿日時:
最終更新: