3乗根定理と4乗根定理
整数の3乗根とか4乗根が存在するための条件の話。平方剰余というのがある。奇素数$p$に対し、$1,2,\cdots,p-1$の中にはモジュロ$p$で平方数に等しいものが半分、そうでないものが半分入ってる。それを判定する相互法則というのがあったりする。相互法則は3乗や4乗のものもある。そんな感じ。
3乗根定理
$p$は3で割って1余る素数とする。このとき、
$$\exists x\in \mathbb{Z}~~~~x^3\equiv 2~~\mathrm{mod}~p~\Leftrightarrow~\exists A,B\in \mathbb{Z}~~~p=A^2+27B^2.$$
具体例。
$$31=2^2+27\cdot 1^2,~~~43=4^2+27\cdot1^2,~~~109=1^2+27\cdot 2^2.$$
2の3乗根。
$$4^3\equiv 2~~\mathrm{mod}~31,~~~{20}^3\equiv 2~~\mathrm{mod}~43,~~~{57}^3\equiv 2~~\mathrm{mod}~109.$$
$p$は3で割って1余る素数とする。このとき、
$$\exists x\in \mathbb{Z}~~~~x^3\equiv 3~~\mathrm{mod}~p~\Leftrightarrow~\exists A,B\in \mathbb{Z}~~~4p=A^2+243B^2.$$
具体例。
$$4\cdot 61=1^2+243\cdot 1^2,~~~4\cdot 73=5^2+243\cdot1^2,~~~4\cdot 193=23^2+243\cdot 1^2.$$
3の3乗根。
$$4^3\equiv 3~~\mathrm{mod}~61,~~~{25}^3\equiv 3~~\mathrm{mod}~73,~~~{48}^3\equiv 3~~\mathrm{mod}~193.$$
5と7の3乗根はちょっと混み入っている。
$p$は3で割って1余る素数とする。このとき、$x^3\equiv 5~~\mathrm{mod}~p$を満たす整数$x$が存在するためには、$p$がある整数$A,B$を用いて次の形で書けることが必要かつ十分である。
$$4p=A^2+25\cdot 27B^2~~または~~4p=25A^2+27B^2.$$
具体例。
$$4\cdot 13 = 25\cdot 1^2+27\cdot 1^2,~~~4\cdot 181 = 7^2 + 25\cdot 27\cdot 1^2.$$
5の3乗根。
$$8^3\equiv 5~~\mathrm{mod}~13,~~~{102}^3\equiv 5~~\mathrm{mod}~181.$$
$p$は3で割って1余る素数とする。このとき、$x^3\equiv 7~~\mathrm{mod}~p$を満たす整数$x$が存在するためには、$p$がある整数$A,B$を用いて次の形で書けることが必要かつ十分である。
$$4p=A^2+49\cdot 27B^2~~または~~4p=49A^2+27B^2.$$
具体例。
$$4\cdot 19= 49\cdot 1^2+27\cdot 1^2,~~~~4\cdot 73 = 49\cdot 1^2 + 27\cdot 3^2.$$
7の3乗根。
$$4^3\equiv 7~~\mathrm{mod}~19,~~~{31}^3\equiv 7~~\mathrm{mod}~73.$$
もうちょっとだけ。
$$4\cdot 181= 49\cdot 1^2+27\cdot 5^2,~~~~4\cdot 331 = 1^2 + 49\cdot 27\cdot 1^2.$$
7の3乗根。
$${32}^3\equiv 7~~\mathrm{mod}~181,~~~{10}^3\equiv 7~~\mathrm{mod}~331.$$
4乗根定理
$p$は4で割って1余る素数とする。このとき、
$$\exists x\in \mathbb{Z}~~~~x^4\equiv 2~~\mathrm{mod}~p~\Leftrightarrow~\exists A,B\in \mathbb{Z}~~~p=A^2+64B^2.$$
具体例。
$$73=3^2+64\cdot 1^2,~~~89=5^2+64\cdot 1^2,~~~113=7^2+64\cdot 1^2.$$
2の4乗根。
$${25}^4\equiv 2~~\mathrm{mod}~73,~~~8^4\equiv 2~~\mathrm{mod}~89,~~~{27}^4\equiv 2~~\mathrm{mod}~113.$$
$p$は4で割って1余る素数とする。このとき、$x^4\equiv 3~~\mathrm{mod}~p$を満たす整数$x$があるためには、$p$が次のいずれかの条件を満たすことが必要かつ十分である。
$$(1):p\equiv 1~~\mathrm{mod}8~~かつ~~\exists A,B\in \mathbb{Z}~~~~p=A^2+36B^2.$$
$$(2):p\equiv 5~~\mathrm{mod}8~~かつ~~\exists A,B\in \mathbb{Z}~~~~p=9A^2+4B^2.$$
$(1)$の例。
$$p=193=7^2+36\cdot 2^2,~~~~{20}^4\equiv 3~~\mathrm{mod}193.$$
$(2)$の例を3つほど。
$$13=9\cdot 1^2+4\cdot 1^2,~~~109=9\cdot 1^2+4\cdot 5^2,~~~181=9\cdot 3^2 +4\cdot 5^2.$$
181何回も出てくるけど、この数が特殊なだけでバグではないです。
$$2^4\equiv 3~~\mathrm{mod}~13,~~~7^4\equiv 3~~\mathrm{mod}~109,~~~{24}^4\equiv 3~~\mathrm{mod}~181.$$
$p$は4で割って1余る素数とする。このとき、
$$\exists x\in \mathbb{Z}~~~~x^4\equiv 5~~\mathrm{mod}~p~\Leftrightarrow~\exists A,B\in \mathbb{Z}~~~p=A^2+100B^2.$$
具体例。
$$101=1^2+100\cdot 1^2,~~~109=3^2+100\cdot 1^2,~~~149=7^2+100\cdot 1^2.$$
5の4乗根。
$${64}^4\equiv 5~~\mathrm{mod}~~101,~~~{81}^4\equiv 5~~\mathrm{mod}~~109,~~~{51}^4\equiv 5~~\mathrm{mod}~~149.$$
$p$は4で割って1余る素数とする。このとき、$x^4\equiv 7~~\mathrm{mod}~p$を満たす整数$x$があるためには、$p$が次のいずれかの条件を満たすことが必要かつ十分である。
$$(1):p\equiv 1~~\mathrm{mod}8~~かつ~~\exists A,B\in \mathbb{Z}~~~~p=A^2+49B^2.$$
$$(2):p\equiv 5~~\mathrm{mod}8~~かつ~~\exists A,B\in \mathbb{Z}~~~~2p=A^2+49B^2.$$
$(1)$の例から。
$$113=8^2+49\cdot 1^2,~~~193={12}^2+49\cdot 1^2.$$
7の4乗根。
$$9^4\equiv 7~~\mathrm{mod}~113,~~~~{32}^4\equiv 7~~\mathrm{mod}~193.$$
$(2)$の例。
$$2\cdot 29 = 3^2 + 49 \cdot 1^2,~~~2\cdot 109 = {13}^2+49\cdot 1^2. $$
7の4乗根。
$$8^4\equiv 7~~\mathrm{mod}~29,~~~{48}^4\equiv 7~~\mathrm{mod}~109.$$
ガウス和とかヤコビ和とか使って証明されるんだけど長すぎてここには書けないので参考文献だけ。
参考文献：A Classical Introduction to Modern Number Theory, Kenneth Ireland, Michael Rosen. Springer Verlag, 1990. 2nd Edition.
整数論について色々書いてある本で、第9章だと思う、3次と4次の相互法則が載っててそこら辺参考にして自分でいろいろ計算して出した気がする。懐かしい・・。