07/03/16 21:37:03
>>778 以降、合同方程式 x^2 ≡ a (mod m) の解法について述べて
きたが、これと >>756 に述べた方法を使って
m = ax^2 + bxy + cy^2 の解を求めて見よう。
まず、p = 2281 として p = x^2 + y^2 を解く。
>>758 の方法を使う。
>>941 より z = 1207 (mod 2281) とおくと、z^4 = -1 であった。
よって z^2 = 1571 (mod 2281) は x^2 ≡ -1 (mod m) の解である。
つまり、1571^2 ≡ -1 (mod 2281) である。
2*1571 = 3142 だから
3142^2 ≡ -4 (mod 4*2281) である。
3142^2 + 4 = 4*2281*1082
よって
２次形式 (a, b, c) = (2281, 3142, 1082) の判別式は
D = b^2 - 4ac = 3142^2 - 4*2281*1082 = -4
(a, b, c) を >>335 の方法(>>411 の注意も参照)により簡約２次形式に
変形する。
(2281, 3142, 1082)S^(-1) = (2281, -1420, 221)
(2281, -1420, 221)T = (221, 1420, 2281)
(221, 1420, 2281)S^(-3) = (221, 94, 10)
(221, 94, 10)T = (10, -94, 221)
(10, -94, 221)S^5 = (10, 6, 1)
(10, 6, 1)T = (1, -6, 10)
(1, -6, 10)S^3 = (1, 0, 1)
となる。
ここで
S = (1, 1)/(0, 1)
T = (0, -1)/(1, 0)
973:Kummer ◆g2BU0D6YN2
07/03/16 21:43:32
よって
(2281, 3142, 1082)S^(-1)TS^(-3)TS^5TS^3 = (1, 0, 1)
行列の積 U = S^(-1)TS^(-3)TS^5TS^3 を計算すると。
U = (11, 31)/(-16, -45)
U の逆行列は V = U^(-1) = (-45, -31)/(16, 11)
よって
(1, 0, 1)V = (2281, 3142, 1082)
>>758 より
x = -45, y = 16 が 2281 = x^2 + y^2 の解である。
実際、45^2 + 16^2 = 2025 + 256 = 2281
974:Kummer ◆g2BU0D6YN2
07/03/16 22:01:40
岩波数学辞典によると p = 9689 は素数で 2^p - 1 は素数である。
2^p - 1 は Mersenne数である。
さらに p ≡ 1 (mod 8) である。
p = x^2 + y^2 を >>972 と同様に解いてみるのも面白いかもしれない。
誰か解いてくれないか？
ただし、結果だけでなく >>972, >>973 と同様に
x^2 ≡ -1 (mod p) の解と２次形式 (a, b, c)
および (a, b, c) の簡約過程。
(1, 0, 1)V = (a, b, c) となる V ∈ SL_2(Z) も求めて欲しい。
975:Kummer ◆g2BU0D6YN2
07/03/17 03:31:02
>>974
今の場合、2^p - 1 が Mersenne数であるということに特に意味があるわけではない。
適当な大きさの素数が欲しかっただけである。
976:Kummer ◆g2BU0D6YN2
07/03/17 06:48:22
今度は p を奇素数としたとき p = x^2 + 2y^2 を解くことを
考えてみよう。
２次形式 (1, 0, 2) = x^2 + 2y^2 の判別式 D は -8 である。
判別式が -8 の簡約２次形式は、>>757 と同様にして
(1, 0, 2) のみであることが分かる。
よって >>758 と同様にして p = x^2 + 2y^2 に解があるためには、
x^2 ≡ -8 (mod 4p) に解があることが必要十分である。
x^2 ≡ 0 (mod 4) だから x は偶数である。
x = 2y とすると
y^2 ≡ -2 (mod p) である。
よって上記の条件は (-2/p) = 1 と同値である。
(-2/p) = (-1/p)(2/p) = 1 だから
これは (2/p) = (-1/p) = 1
または (2/p) = (-1/p) = -1
と同値である。
平方剰余の第一補充法則(>>163)と第２補充法則(>>53)より、
これは p ≡ 1 (mod 8) または p ≡ 3 (mod 8) と同値である。
977:Kummer ◆g2BU0D6YN2
07/03/17 06:49:40
x^2 ≡ -8 (mod 4p) の解 l に対して
l^2 + 8 = 4pk とする。
p は奇素数だから l とは互いに素である。
よって２次形式 (p, l, k) は正定値かつ原始的で判別式は -8 である。
これは (1, 0, 2) と同値である。
よって (1, 0, 2)σ = (p, l, k) となる σ ∈ SL_2(Z) がある。
σ = (u, q)/(r, s) とする。
>>749 より (1, 0, 2)ε = (1, 0, 2) となる ε ∈ SL_2(Z) は
{±1} である。
よって (1, 0, 2) を (p, l, k) に移す SL_2(Z) の元は
σ = (u, q)/(r, s) と -σ = (-u, -q)/(-r, -s) の２個である。
よって (u, r) と (-u, -r) が l に対応する p = x^2 + 2y^2 の
解である。
x^2 ≡ -4 (mod 4p) の別の解 -l には
２次形式 (p, -l, k) が対応する。
R = (1, 0)/(0, -1) とすると
(1, 0, 1)RσR = (p, l, k)R = (p, -l, k)
U = RσR とおく。
U ∈ SL_2(Z) で U = (u, -q)/(-r, s) である。
よって (u, -r) と (-u, r) が -l に対応する p = x^2 + 2y^2 の
解である。
978:Kummer ◆g2BU0D6YN2
07/03/17 07:19:23
>>976 と >>977 から次の命題が得られる。
命題(Fermat-Euler)
p を奇素数とする。
p = x^2 + 2y^2 が有理整数解を持つためには
p ≡ 1 (mod 8) または p ≡ 3 (mod 8) が必要十分である。
さらに、このとき解は順序と符号を除いて一つである。
979:Kummer ◆g2BU0D6YN2
07/03/17 19:54:29
>>974 を解いてみる。
p = 9689
p - 1 = 8*1211
(3/p) = (p/3) = (2/3) = -1
だから
z = 3^1211 ≡ 6682 (mod p)
とすると、z^8 = 1 である。
よって (z^2)^2 = -1 である。
z^2 = 2212 (mod p)
だから
2212^2 ≡ -1 (mod p)
2*2212 = 4424 だから
4424^2 ≡ -4 (mod 4*9689) である。
4424^2 + 4 = 4*9689*505
だから
２次形式 (9689, 4424, 505) の判別式は -4
>>335 より
(9689, 4424, 505) T = (505, -4424, 9689)
(505, -4424, 9689) S^4 = (505, -384, 73)
(505, -384, 73) T = (73, 384, 505)
このあとは読者の誰かに任そう。
誰か？
ただし、続きは上の結果が正しいかどうか確かめてからにしてください。
計算ミスがあるかもしれないので。
980:Kummer ◆g2BU0D6YN2
07/03/17 20:44:05
訂正
>>978
>さらに、このとき解は順序と符号を除いて一つである。
さらに、このとき解は符号を除いて一つである。
981:Kummer ◆g2BU0D6YN2
07/03/18 01:59:09
p を素数としたとき p = x^2 + 3y^2 を解くことを考えてみよう。
２次形式 (1, 0, 3) = x^2 + 3y^2 の判別式 D は -12 である。
>>408 より判別式 -4 の (a, b, c) が簡約２次形式であるためには
gcd(a, b, c) = 1 かつ、
|b| ≦ a ≦ c であり、
|b| = a または a = c のときは b ≧ 0 となることが必要十分である。
>>341 と同様にして a ≦ √(|D|/3) である。
a ≦ √(|D|/3) = 2
4ac = b^2 + |D| = b^2 + 12
よって b^2 ≡ 0 (mod 4)
よって b は偶数である。
0^2 + 12 = 4・3
2^2 + 12 = 16 = 4・4
a = 1 のとき (1, 0, 3)
a = 2 のとき (2, 2, 2) は原始的でない。
よって判別式が -12 の簡約２次形式は、(1, 0, 3) のみである。
p ≠ 2, 3 として合同方程式 x^2 ≡ -12 (mod 4p) を考える。
x^2 ≡ 0 (mod 4) だから x は偶数である。
x = 2y とおくと
y^2 ≡ -3 (mod p)
これは (-3/p) = (-1/p)(3/p) = 1 のときのみ解がある。
p ≡ 1 (mod 4) なら (-1/p) = 1, (3/p) = (p/3)
p ≡ 3 (mod 4) なら (-1/p) = -1, (3/p) = -(p/3)
いずれにしても (-1/p)(3/p) = (p/3) である。
よって (-3/p) = 1 は p ≡ 1 (mod 3) と同値である。
982:Kummer ◆g2BU0D6YN2
07/03/18 02:08:41
p ≡ 1 (mod 3) のとき
x^2 ≡ -12 (mod 4p) の解 l に対して
l^2 + 12 = 4pk とする。
p は奇素数だから l とは互いに素である。
よって２次形式 (p, l, k) は正定値かつ原始的で判別式は -12 である。
これは (1, 0, 3) と同値である。
よって (1, 0, 3)σ = (p, l, k) となる σ ∈ SL_2(Z) がある。
σ = (u, q)/(r, s) とする。
>>749 より (1, 0, 3)ε = (1, 0, 3) となる ε ∈ SL_2(Z) は
{±1} である。
よって (1, 0, 3) を (p, l, k) に移す SL_2(Z) の元は
σ = (u, q)/(r, s) と -σ = (-u, -q)/(-r, -s) の２個である。
よって (u, r) と (-u, -r) が l に対応する p = x^2 + 3y^2 の
解である。
x^2 ≡ -12 (mod 4p) の別の解 -l には
２次形式 (p, -l, k) が対応する。
R = (1, 0)/(0, -1) とすると
(1, 0, 3)RσR = (p, l, k)R = (p, -l, k)
U = RσR とおく。
U ∈ SL_2(Z) で U = (u, -q)/(-r, s) である。
よって (u, -r) と (-u, r) が -l に対応する p = x^2 + 3y^2 の
解である。
983:Kummer ◆g2BU0D6YN2
07/03/18 02:14:29
>>981 と >>982 から次の命題が得られる。
命題(Fermat-Euler)
p を 3 以外の奇素数とする。
p = x^2 + 3y^2 が有理整数解を持つためには
p ≡ 1 (mod 3) が必要十分である。
さらに、このとき解は符号を除いて一つである。
984:Kummer ◆g2BU0D6YN2
07/03/18 02:33:12
>>978 の命題は Fermat に知られていたが初めて証明したのは
Euler らしい。らしいというのは Gauss が Disquisitiones の
art. 182 に Lagrange が最初に証明したと書いているからである。
しかもはっきりと Euler は証明に成功しなかったと書いている。
しかし、Weil は「数論」で Euler が証明したと書いている。
985:１３２人目の素数さん
07/03/18 02:45:40
Kummer ◆g2BU0D6YN2 かっこいい
986:１３２人目の素数さん
07/03/18 02:48:40
@
987:Kummer ◆g2BU0D6YN2
07/03/18 11:36:15
今度は p を素数としたとき p = x^2 + 5y^2 を解くことを考えてみよう。
この問題は >>161 でも考えたし解決済み(>>363)である。
しかし、２次形式論の応用として証明をする。
２次形式 (1, 0, 5) = x^2 + 5y^2 の判別式 D は -20 である。
>>408 より判別式 -20 の (a, b, c) が簡約２次形式であるためには
gcd(a, b, c) = 1 かつ、
|b| ≦ a ≦ c であり、
|b| = a または a = c のときは b ≧ 0 となることが必要十分である。
>>341 と同様にして a ≦ √(|D|/3) である。
よって a ≦ 2
4ac = b^2 + |D| = b^2 + 20
よって b^2 ≡ 0 (mod 4)
よって b は偶数である。
0^2 + 20 = 4・5
2^2 + 20 = 4・2・3
a = 1 のとき (a, b, c) = (1, 0, 5)
a = 2 のとき (a, b, c) = (2, 2, 3)
よって判別式が -20 の簡約２次形式は、(1, 0, 5) と (2, 2, 3)
である。
988:Kummer ◆g2BU0D6YN2
07/03/18 13:22:45
p ≠ 2, 5 として合同方程式 x^2 ≡ -20 (mod 4p) を考える。
x^2 ≡ 0 (mod 4) だから x は偶数である。
x = 2y とおくと
y^2 ≡ -5 (mod p)
x^2 ≡ -20 (mod 4p) が解けるためには (-5/p) = 1 が
必要十分である。
(-5/p) = (-1/p)(5/p)
平方剰余の相互律から (5/p) = (p/5) である。
よって p ≡ 1, 4 (mod 5) のとき (5/p) = 1
p ≡ 2, 3 (mod 5) のとき (5/p) = -1
一方、p ≡ 1 (mod 4) のとき (-1/p) = 1
p ≡ 3 (mod 4) のとき (-1/p) = -1
よって (-5/p) = 1 は
p ≡ 1, 4 (mod 5) かつ p ≡ 1 (mod 4)
つまり、p ≡ 1, 9 (mod 20)
または
p ≡ 2, 3 (mod 5) かつ p ≡ 3 (mod 4)
つまり、p ≡ 3, 7 (mod 20)
と同値である。
989:Kummer ◆g2BU0D6YN2
07/03/18 13:45:35
p ≠ 2, 5 として p = x^2 + 5y^2 となる有理整数 (x, y) が
あったとする。
p ≡ x^2 (mod 5) だから (p/5) = 1
p ≠ 2, 5 として p = 2x^2 + 2xy + 3y^2 となる有理整数 (x, y) が
あったとする。
2p = 4x^2 + 4xy + 6y^2 = (2x + y)^2 + 5y^2
2p ≡ (2x + y)^2 (mod 5)
よって (2p/5) = (2/5)(p/5) = -(p/5) = 1
よって (p/5) = -1
990:Kummer ◆g2BU0D6YN2
07/03/18 15:39:57
p ≡ 1, 2, 3, 9 (mod 20) なら >>988 より x^2 ≡ -20 (mod 4p) に
解がある。
x^2 ≡ -20 (mod 4p) の解 l に対して
l^2 + 20 = 4pk とする。
p は奇素数だから l とは互いに素である。
よって２次形式 (p, l, k) は正定値かつ原始的で判別式は -20 である。
よって >>987 より (p, l, k) は (1, 0, 5) または (2, 2, 3) に
同値である。
>>733 より (p, l, k) が (1, 0, 5) に同値なら p = x^2 + 5y^2 となる
有理整数 (x, y) がある。
このとき >>989 より (p/5) = 1 である。
p ≡ 1, 3, 7, 9 (mod 20) であったから
p ≡ 1, 9 (mod 20) である。
逆に p ≡ 1, 9 (mod 20) なら (p/5) = 1 だから >>989 より
(p, l, k) は (2, 2, 3) に同値ではない。
よって (p, l, k) は (1, 0, 5) に同値である。
以上から p = x^2 + 5y^2 となる有理整数 (x, y) があるためには
p ≡ 1, 9 (mod 20) が必要十分である。
>>977 と同様に、この場合、解は符号を除いて一個である。
同様に p = 2x^2 + 2xy + 3y^2 となる有理整数 (x, y) があるためには
p ≡ 3, 7 (mod 20) が必要十分である。
この場合も、解は符号を除いて一個である。
991:Kummer ◆g2BU0D6YN2
07/03/18 16:05:30
p ≠ 2, 5 として 2p = x^2 + 5y^2 を考える。
gcd(x, y) = d なら 2p が d^2 で割れるから d = 1 である。
よって解があるなら合同方程式 x^2 ≡ -20 (mod 8p) に解がある。
x^2 ≡ 0 (mod 4) だから x は偶数である。
x = 2y とおくと y^2 ≡ -5 (mod 2p) である。
これは連立合同方程式
y^2 ≡ -5 (mod 2)
y^2 ≡ -5 (mod p)
と同値である
y^2 ≡ -5 (mod 2) は常に解 y ≡ 1 (mod 2) をもつから、
x^2 ≡ -20 (mod 8p) に解があるなら (-5/p) = 1 である。
よって >>988 より p ≡ 1, 3, 7, 9 (mod 20) である。
一方、2p = x^2 + 5y^2 なら x^2 ≡ 2p (mod 5)
よって (2p/5) = 1
(2p/5) = (2/5)(p/5) = -(p/5)
よって (p/5) = -1 となる。
よって p ≡ 3, 7 (mod 20) である。
よって >>990 と同様に
2p = x^2 + 5y^2 となる有理整数 (x, y) があるためには
p ≡ 3, 7 (mod 20) が必要十分である。
992:Kummer ◆g2BU0D6YN2
07/03/18 16:14:17
>>990 と >>991 をまとめると次の命題が得られる。
命題(Fermat-Euler-Lagrange)
p ≠ 2, 5 を素数とする。
(1) p = x^2 + 5y^2 となる有理整数 (x, y) があるためには
p ≡ 1, 9 (mod 20) が必要十分である。
(2) p = 2x^2 + 2xy + 3y^2 となる有理整数 (x, y) があるためには
p ≡ 3, 7 (mod 20) が必要十分である。
(3) 2p = x^2 + 5y^2 となる有理整数 (x, y) があるためには
p ≡ 3, 7 (mod 20) が必要十分である。
上記のいずれの場合も解は符号を除いて一意である。