代数的整数論　004

1 名前：１３２人目の素数さん [2006/11/23(木) 21:57:04 ] Kummer ◆g2BU0D6YN2氏が代数的整数論を語るスレです。 前スレ science4.2ch.net/test/read.cgi/math/1141019088/ 830 名前：Kummer ◆g2BU0D6YN2 [2007/03/04(日) 11:02:16 ] 補題 n ≧ 3 を有理整数とする。 5^(2^(n-3)) ≡ 1 + 2^(n-1) (mod 2^n) である。 証明 n に関する帰納法を使う。 n = 3 のときは正しい。 ある n ≧ 3 に対して 5^(2^(n-3)) ≡ 1 + 2^(n-1) (mod 2^n) が正しいとする。 >>829 より、 5^(2^(n-2)) ≡ (1 + 2^(n-1))^2 (mod 2^(n+1)) ここで (1 + 2^(n-1))^2 = 1 + 2^n + 2^(2n - 2) 2n - 2 ≧ n + 1 だから 5^(2^(n-2)) ≡ 1 + 2^n (mod 2^(n+1)) 証明終 831 名前：Kummer ◆g2BU0D6YN2 [2007/03/04(日) 11:18:47 ] 補題 n ≧ 3 を有理整数とする。 a を任意の奇数とすると、 a^(2^(n-2)) ≡ 1 (mod 2^n) である。 証明 n に関する帰納法を使う。 n = 3 のときは正しい。 ある n ≧ 3 に対して a^(2^(n-2)) ≡ 1 (mod 2^n) が正しいとする。 >>829 より a^(2^(n-1)) ≡ 1 (mod 2^(n+1)) 証明終 832 名前：Kummer ◆g2BU0D6YN2 [2007/03/04(日) 11:23:16 ] 補題 n ≧ 3 を有理整数とする。 5 mod 2^n の (Z/2^nZ)^* における位数は 2^(n-2) である。 証明 >>830 と >>831 より明らかである。 833 名前：Kummer ◆g2BU0D6YN2 [2007/03/04(日) 11:38:03 ] 補題 n ≧ 3 を有理整数とする。 任意の有理整数 k ≧ 0 に対して 5^k ≡ -1 (mod 2^n) とはならない。 証明 5^k ≡ -1 (mod 2^n) と仮定する。 5^k ≡ -1 (mod 4) である。 一方 5 ≡ 1 (mod 4) だから 1 ≡ -1 (mod 4) となって矛盾である。 証明終 834 名前：Kummer ◆g2BU0D6YN2 [2007/03/04(日) 11:44:34 ] 命題 n ≧ 3 を有理整数とする。 G = (Z/2^nZ)^* とおく。 a と b をそれぞれ mod 2^n における -1 と 5 の剰余類とする。 a で生成される G の部分群を K とし、 b で生成される G の部分群を H とする。 |K| = 2 |H| = 2^(n-2) であり G = K × H (直積)である。 証明 |G| = 2^(n-1) と >>832 と >>833 より明らかである。 835 名前：Kummer ◆g2BU0D6YN2 [2007/03/04(日) 11:58:05 ] >>800 の証明は以下のようにしたほうが明快だろう。 >>789 より N が素数 p のベキ p^m の場合に証明すればよい。 G における x^(p^(m-1)) = 1 の解の個数は p^(m-1) 以下である。 よって g^(p^(m-1)) ≠ 1 となる g ∈ G がある。 g が G の生成元である。 証明終 836 名前：１３２人目の素数さん mailto:sage [2007/03/05(月) 16:04:00 ] 23 837 名前：１３２人目の素数さん mailto:sage [2007/03/05(月) 16:05:00 ] 22 838 名前：１３２人目の素数さん mailto:sage [2007/03/05(月) 16:06:00 ] 21 839 名前：１３２人目の素数さん mailto:sage [2007/03/05(月) 16:07:00 ] 20 840 名前：１３２人目の素数さん mailto:sage [2007/03/05(月) 16:08:00 ] 19 841 名前：１３２人目の素数さん mailto:sage [2007/03/05(月) 16:09:00 ] 18 842 名前：１３２人目の素数さん [2007/03/06(火) 10:42:57 ] modular form no ii hon oshiete!!! 843 名前：Kummer ◆g2BU0D6YN2 [2007/03/06(火) 13:08:24 ] >>795 の >>789 を使わない証明を思いついた。 命題 G を有限アーベル群とする。 p を |G| を割る素数とすると G は位数 p の元をもつ。 証明 G の位数に関する帰納法を使う。 G の元 x ≠ 1 の位数 m が p で割れるとする。 m = pt とする。x^t の位数は p だから、この場合は命題は 証明された。 G の元 x ≠ 1 の位数 m が p で割れないとする。 x で生成される部分群を H とする。 G/H の位数は p で割れるから帰納法の仮定より G/H は位数 p の元を もつ。その元の任意の代表を y とする。 y^p ∈ H だから (y^p)^m = 1 である。よって y の位数は pm の 約数である。 よって、y の位数が p で割れないとすると、y^m = 1 となる。 このとき y mod H の位数は m の約数となり p で割れない。 これは矛盾である。 よって y の位数は p で割れる。 よって y の適当なべきの位数は p である。 証明終 844 名前：Kummer ◆g2BU0D6YN2 [2007/03/06(火) 20:29:06 ] 補題 H と K をそれぞれ位数 n と位数 m の巡回群とする。 G = H × K を直積とする。 gcd(n, m) ≠ 1 なら G は巡回群ではない。 証明 gcd(n, m) ≠ 1 だから、n と m はある素数 p で割れる。 >>795 より H と K はそれぞれ位数 p の部分群をもつ。 これらは明らかに異なる。 一方、G が巡回群なら位数 p の部分群はただ一つである。 よって G は巡回群ではない。 証明終 845 名前：Kummer ◆g2BU0D6YN2 [2007/03/06(火) 20:31:41 ] >>844 は間違いではないが、次のように訂正する。 補題 H と K をそれぞれ位数 n と位数 m のアーベル群とする。 G = H × K を直積とする。 gcd(n, m) ≠ 1 なら G は巡回群ではない。 証明 gcd(n, m) ≠ 1 だから、n と m はある素数 p で割れる。 >>795 より H と K はそれぞれ位数 p の部分群をもつ。 これらは明らかに異なる。 一方、G が巡回群なら位数 p の部分群はただ一つである。 よって G は巡回群ではない。 証明終 846 名前：Kummer ◆g2BU0D6YN2 [2007/03/06(火) 20:35:27 ] 命題 H と K をそれぞれ位数 n と位数 m の巡回群とする。 G = H × K を直積とする。 G が巡回群であるためには gcd(n, m) = 1 が必要十分である。 証明 >>805 と >>845 より明らかである。 847 名前：Kummer ◆g2BU0D6YN2 [2007/03/06(火) 20:39:11 ] 補題 p を素数とし、n ≧ 1 を有理整数とする。 (Z/p^nZ)^* の位数は p = 2 で n = 1 を除いて偶数である。 証明 |(Z/p^nZ)^*| = (p^(n - 1))(p - 1) より明らかである。 848 名前：Kummer ◆g2BU0D6YN2 [2007/03/06(火) 20:58:06 ] 命題 N ≧ 2 を有理整数とする。 (Z/NZ)^* が巡回群となるのは、以下の場合のみである。 N = 2, 4, p^n, 2p^n ここで p は奇素数で n ≧ 1 である。 証明 N の素因数分解を N = Π q^r とする。 中国式剰余定理(前スレ１の341)より Z/NZ = Π Z/(q^r)/Z である。 よって >>612 より (Z/NZ)^* = Π (Z/(q^r)/Z)^* である。 >>820 より p が奇素数で n ≧ 1 のとき (Z/p^nZ)^* は巡回群である。 >>834 より (Z/2^nZ)^* は n ≧ 3 のときは巡回群でない。 一方、 (Z/2Z)^* と (Z/4Z)^* 明らかに巡回群である。 以上の事実と >>847 と >>845 より本命題の主張は明らかである。 証明終 849 名前：Kummer ◆g2BU0D6YN2 [2007/03/06(火) 21:19:02 ] アーベル群の基本定理と >>845 から >>800 の別証明が得られる。 この証明は高木の「代数的整数論」にある証明(p.34)と同じである。 >>800 の別証明 アーベル群の基本定理から G は巡回群の直積である。 G が巡回群でないとすると >>846 よりある素数 p があり、 G は位数 p の部分群２個 の直積を部分群として含む。 すると x^p = 1 の G における解の個数は p^2 以上となり 仮定に反する。 証明終 850 名前：Kummer ◆g2BU0D6YN2 [2007/03/07(水) 21:12:09 ] 補題 n ≧ 1 と m ≧ 1 を有理整数とする。 d = gcd(n, m) とおく。 a を有理整数とする。 合同方程式 nx ≡ a (mod m) に解があるためには a が d で割れる ことが必要十分である。 このとき x^n = a 解の個数は d である。 証明 nb ≡ a (mod m) となる b ∈ Z があるとする。 nb - a = mk となる k ∈ Z がある。 a = nb - mk である. よって a ≡ 0 (mod d) である。 逆に a ≡ 0 (mod d) とする。 a = d(a ') と書ける。 n と m は d で割れるから n = d(n ') m = d(m ') と書ける。 よって nx ≡ a (mod m) は (n ')x ≡ a ' (mod m ') と同値である。 gcd(n ', m ') = 1 だから (n ')x ≡ a ' (mod m ') は mod m ' で唯一の解 b ' を持つ。 nx ≡ ny (mod m) なら、n(x - y) ≡ 0 (mod m) よって n '(x - y) ≡ 0 (mod m ') よって x ≡ y (mod m ') これから nx ≡ a (mod m) の解は b ', b ' + m ', ..., b ' + (d - 1)m ' の d 個である。 証明終 851 名前：Kummer ◆g2BU0D6YN2 [2007/03/07(水) 22:14:54 ] 命題 G を位数 m の巡回群とする。 n ≧ 1 を有理整数、 a を G の元とする。 d = gcd(n, m) とする。 x^n = a に解があるためには a^(m/d) = 1 が必要十分である。 このとき、この解の個数は d である。 証明 G の生成元を g とする。 a = g^i とかける。 x を G の元とし x^n = a とする。 x = g^y とすると g^(ny) = g^i となる。 よって x^n = a に解があるためには ny ≡ i (mod m) に解 y が あることが必要十分である。 >>850 より、これは i ≡ 0 (mod d) と同値である。 容易にわかるように、これは a^(m/d) = 1 と同意である。 x^n = a に解があるとき、この解の個数は >>850 より d である。 証明終 852 名前：１３２人目の素数さん mailto:sage [2007/03/07(水) 22:15:33 ] 　　　　 　　　.， 　　　　 　　　.|　　　　　　　　　　　　　 　　　　　　　　　　　　.　　　　　　　　　　　　 、・　　　　　　ﾞ； 　　　　　　　､′　　　.　　　.　　.　　.′　　　　　　　.　　　　　　　.　　　　　　　._．t~´　　　　 　　　.’ 　　　　　　　ﾞ，　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　.l・^´ . ’　　　.　　　.　　.1　.　.._．・￣＼_ 　　 　　.　　 ；　.　.　.._＞~　　　.　　.，　　　 ，　...→_　　　　　　　　　　　　.l　　　､’ﾞ_､．‐　　 　　._．・/＜　.　.　.　.’ 　　　.　　　､，　..._．¨｀　　　　　　　 ’　　 　.|､。・｀.､’_　 　.，・¨¨“÷　　　，._、-・ﾍ´　　 　.　 ／゛ .．′　　.　　.　　.! 　　　　　　､，。・′・　　　　　　　　､1　　　 }・　.　.　..’　.､，　　　ﾞｶ　　　ﾞ，＾　　　 ’_　　　　　　　.ｿ”　 　.、．．　.　.} 　　　　　　 ；′　.　..’_　　　　.　　　､’　.　...1　　　　､}　　′　　ﾞﾂﾞ|　.　､，　　　　　.’_　　.　　､，・　　　 /　 　.｀､..../ 　　　　　　.；　　 　.　 ’　　　　.　　　､}　.　...l!　　.　.　.|　.　...＼・~ . |　.　.，　　　　　　 ’_　　　 ，’　 　.　 ｀．_　....}_ﾉ｀ 　　　　　　，　　.　　.　.’　　　　　　　ﾞ!　.　､’　　 　　.’　　　　　　､，　　′　　　.　　　､’、-　　.　　.　　.　　.｀¨¨′ 　　.　　.　.i　　　　　　　ﾞ’　　　　　　　　　　　　　　　　　　　　　　､｜ 　　.　　.　.l　　　　　　　　　　　　　　　　　　　　　　　　　　　　￣￣　　　 　.　.　.._ 　.　.　.i 　　　ﾞ，　　.　.　.-_　.　､； 　　　，・ﾅ・_　 　. ｀､　./ 　　､，　 　.)　　　　.｀j.´ 　　､l　、．-’　.　.　./ 　　.　　.　　.l　　　　　　　} 　､＝＝＝＝＝＝＝＝＝＝＝＝- 　　.　　.　　.|　 　. 、　.　..| 　　.　　.　　.’　.　､|　　　ﾞ’ 　　.　.}．-‐………………………， 　　　､|　　 　　.　 |＝＝・　.　.　.　.・ 　　　､’　　　 　　.’._、．｣ 　　　　　.　　　　./ ´ 　　.　　.　　.　　.，¨¨TTﾅﾅﾅ， 　　　　　　　　ﾞ＿_＿＿＿＿｜ 853 名前：KingOfUniverse ◆667la1PjK2 [2007/03/07(水) 22:21:19 ] talk:>>852 お前に何が分かるというのか？ 854 名前：１３２人目の素数さん mailto:sage [2007/03/07(水) 22:45:08 ] 　　　　 　　　.， 　　　　 　　　.|　　　　　　　　　　　　　 　　　　　　　　　　　　.　　　　　　　　　　　　 、・　　　　　　ﾞ； 　　　　　　　､′　　　.　　　.　　.　　.′　　　　　　　.　　　　　　　.　　　　　　　._．t~´　　　　 　　　.’ 　　　　　　　ﾞ，　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　.l・^´ . ’　　　.　　　.　　.1　.　.._．・￣＼_ 　　 　　.　　 ；　.　.　.._＞~　　　.　　.，　　　 ，　...→_　　　　　　　　　　　　.l　　　､’ﾞ_､．‐　　 　　._．・/＜　.　.　.　.’ 　　　.　　　､，　..._．¨｀　　　　　　　 ’　　 　.|､。・｀.､’_　 　.，・¨¨“÷　　　，._、-・ﾍ´　　 　.　 ／゛ .．′　　.　　.　　.! 　　　　　　､，。・′・　　　　　　　　､1　　　 }・　.　.　..’　.､，　　　ﾞｶ　　　ﾞ，＾　　　 ’_　　　　　　　.ｿ”　 　.、．．　.　.} 　　　　　　 ；′　.　..’_　　　　.　　　､’　.　...1　　　　､}　　′　　ﾞﾂﾞ|　.　､，　　　　　.’_　　.　　､，・　　　 /　 　.｀､..../ 　　　　　　.；　　 　.　 ’　　　　.　　　､}　.　...l!　　.　.　.|　.　...＼・~ . |　.　.，　　　　　　 ’_　　　 ，’　 　.　 ｀．_　....}_ﾉ｀ 　　　　　　，　　.　　.　.’　　　　　　　ﾞ!　.　､’　　 　　.’　　　　　　､，　　′　　　.　　　､’、-　　.　　.　　.　　.｀¨¨′ 　　.　　.　.i　　　　　　　ﾞ’　　　　　　　　　　　　　　　　　　　　　　､｜ 　　.　　.　.l　　　　　　　　　　　　　　　　　　　　　　　　　　　　￣￣　　　 　.　.　.._ 　.　.　.i 　　　ﾞ，　　.　.　.-_　.　､； 　　　，・ﾅ・_　 　. ｀､　./ 　　､，　 　.)　　　　.｀j.´ 　　､l　、．-’　.　.　./ 　　.　　.　　.l　　　　　　　} 　､＝＝＝＝＝＝＝＝＝＝＝＝- 　　.　　.　　.|　 　. 、　.　..| 　　.　　.　　.’　.　､|　　　ﾞ’ 　　.　.}．-‐………………………， 　　　､|　　 　　.　 |＝＝・　.　.　.　.・ 　　　､’　　　 　　.’._、．｣ 　　　　　.　　　　./ ´ 　　.　　.　　.　　.，¨¨TTﾅﾅﾅ， 　　　　　　　　ﾞ＿_＿＿＿＿｜ 855 名前：KingOfUniverse ◆667la1PjK2 [2007/03/07(水) 22:57:44 ] talk:>>854 お前に何が分かるというのか？ 856 名前：１３２人目の素数さん mailto:sage [2007/03/09(金) 10:24:00 ] 25 857 名前：１３２人目の素数さん mailto:sage [2007/03/09(金) 10:25:00 ] 26 858 名前：１３２人目の素数さん mailto:sage [2007/03/09(金) 10:26:00 ] 25 859 名前：１３２人目の素数さん mailto:sage [2007/03/09(金) 10:27:00 ] 24 860 名前：Kummer ◆g2BU0D6YN2 [2007/03/09(金) 21:49:34 ] 命題 m ≧ 1 を有理整数とし、(Z/mZ)^* は巡回群とする。 n ≧ 1 を有理整数、 a を 有理整数で gcd(a, m) = 1 とする。 このとき x^n ≡ a (mod m) に解があるためには a^(φ(m)/d) ≡ 1 (mod m) が必要十分である。 ここで φ(m) は Euler の関数である。 つまり、φ(m) = |(Z/mZ)^*| である。 さらに、d = (n, φ(m)) である。 証明 >>851 より明らかである。 861 名前：Kummer ◆g2BU0D6YN2 [2007/03/10(土) 05:49:28 ] >>860 の命題と同じ条件で、x^n ≡ a (mod m) に解があるとき、 その解の個数は d = (n, φ(m)) である。 これも >>851 より明らかである。 862 名前：Kummer ◆g2BU0D6YN2 [2007/03/10(土) 06:46:03 ] 命題 p を有理素数とする。 n ≧ 1 と a を 有理整数でそれぞれ p で割れないとする。 x^n ≡ a (mod p) が解 b を持つとする。 このとき、任意の e ≧ 1 に対して x^n ≡ a (mod p^e) が c ≡ b (mod p) となる根 c を持つ。 このような c は mod p^e で一意に決まる。 証明 x^n ≡ a (mod p) の解を b とする。 f(X) = X^n - a とおく。 仮定より f '(b) = nb^(n-1) は p で割れない。 よって本命題は >>99 から得られる。 証明終 863 名前：Kummer ◆g2BU0D6YN2 [2007/03/10(土) 07:49:46 ] 命題 p を奇素数とする。 a を 有理整数で a は p で割れないとする。 n ≧ 1、e ≧ 1 に対して x^n ≡ a (mod p^e) が解を持つためには a^(φ(p^e)/d) ≡ 1 (mod p^e) が必要十分である。 ここで、d = gcd(n, φ(p^e)) である。 x^n ≡ a (mod p^e) が解を持つなら、その個数は d である。 証明 >>820 より (Z/p^eZ)^* は巡回群である。 よって本命題は >>860 と >>861 から出る。 864 名前：Kummer ◆g2BU0D6YN2 [2007/03/10(土) 08:02:49 ] >>863 において n が p で割れないときはもっと良い結果が得られる。 命題 p を奇素数とする。 n ≧ 1 と a を 有理整数でそれぞれ p で割れないとする。 x^n ≡ a (mod p) が解を持つためには a^((p - 1)/d) ≡ 1 (mod p) が必要十分である。 ここで、d = gcd(n, p - 1) である。 x^n ≡ a (mod p) が解を持たないとする。 このとき、任意の e ≧ 1 に対して x^n ≡ a (mod p^e) も 解を持たない。 x^n ≡ a (mod p) が解を持つなら、 任意の e ≧ 1 に対して x^n ≡ a (mod p^e) も解を持ち、 その個数は d = gcd(n, p - 1) である。 証明 最初の主張は >>863 より出る。 残りの主張は >>862 より出る。 865 名前：Kummer ◆g2BU0D6YN2 [2007/03/10(土) 09:05:48 ] >>862 は p = 2 でも成り立つから >>864 も p = 2 で成り立つ。 従って、n ≧ 1 と a が奇数のとき 任意の e ≧ 1 に対して x^n ≡ a (mod 2^e) は 唯一の解を持つ。 866 名前：Kummer ◆g2BU0D6YN2 [2007/03/10(土) 10:05:06 ] >>864 より次の命題が直ちに得られる。 命題 p を奇素数とする。 a を 有理整数で a は p で割れないとする。 (a/p) = 1 なら、任意の e ≧ 1 に対して x^2 ≡ a (mod p^e) が 解を持つ。このとき、解の個数は２である。 ここで (a/p) は Legendre の記号(前スレ３の746)である。 逆に、ある e ≧ 1 に対して x^2 ≡ a (mod p^e) が解を持つなら (a/p) = 1 である。 867 名前：１３２人目の素数さん mailto:sage [2007/03/10(土) 13:50:22 ] 解析的整数論ってなんかかっこいいよね 868 名前：１３２人目の素数さん mailto:sage [2007/03/10(土) 18:57:17 ] ζ関数、多重ゼータ値、保型形式など 869 名前：１３２人目の素数さん mailto:sage [2007/03/10(土) 20:04:00 ] 22 870 名前：１３２人目の素数さん mailto:sage [2007/03/10(土) 20:05:00 ] 21 871 名前：１３２人目の素数さん mailto:sage [2007/03/10(土) 20:06:00 ] 20 872 名前：１３２人目の素数さん mailto:sage [2007/03/10(土) 20:07:00 ] 19 873 名前：１３２人目の素数さん mailto:sage [2007/03/10(土) 20:08:00 ] 18 874 名前：Kummer ◆g2BU0D6YN2 [2007/03/10(土) 20:08:33 ] [Gauss: Disquisitiones, art.102] 今度は p を奇素数として a が p で割れるときに x^2 ≡ a (mod p^n) を考える。 a = (p^k)b, gcd(b, p) = 1 とする。 1) k ≧ n のとき a ≡ 0 (mod p^n) であるから x^2 ≡ a (mod p^n) は解 x = 0 を持つ。 2) １≦ k ＜ n で k が奇数のとき x^2 ≡ a (mod p^n) は解を持たない。 証明 x^2 ≡ a (mod p^n) が解 x = c を持つとする。 ｃ^2 ≡ (p^k)b (mod p^n) より c^2 は p^k で割れる。 c = (p^s)d, gcd(d, p) = 1 とする。 k = 2t + 1 とすると、2s ≧ 2t + 1 だから s ≧ t + 1 よって c^2 は 2t + 2 で割れる。 ｃ^2 ≡ (p^k)b (mod p^n) で 2t + 2 ≦ n だから (p^(2t + 1))b ≡ 0 (mod p^(2t + 2)) よって b ≡ 0 (mod p) となり矛盾である。 3) １≦ k ＜ n で k が偶数のとき x^2 ≡ a (mod p^n) が解を持つためには、(b/p) = 1 が 必要十分である。 証明 k = 2s とする。 x^2 ≡ (p^(2s))b (mod p^n) x = (p^s)y とおくと y^2 ≡ b (mod p^(n - k)) これと >>866 より上記の主張が出る。 875 名前：１３２人目の素数さん mailto:sage [2007/03/10(土) 20:09:00 ] 17 876 名前：１３２人目の素数さん mailto:sage [2007/03/10(土) 20:10:00 ] 17 877 名前：Kummer ◆g2BU0D6YN2 [2007/03/10(土) 20:16:13 ] >>874 は簡単だが、あまり他では言及されてない。 878 名前：Kummer ◆g2BU0D6YN2 [2007/03/10(土) 21:17:02 ] [Gauss: Disquisitiones, art.104] >>874 の 1) と 3) における(互いに合同でない)解の個数を求める。 条件を再度述べる。 p を奇素数として a が p で割れるときに x^2 ≡ a (mod p^n) を考える。 a = (p^k)b, gcd(b, p) = 1 とする。 1) k ≧ n のとき n が偶数のとき n = 2m n が奇数のとき n = 2m - 1 とおく。 x^2 ≡ a (mod p^n) より x^2 ≡ 0 (mod p^n) となる。 よって x ≡ 0 (mod p^m) となる。 0, p^m, 2p^m, ..., (p^(n - m) - 1)p^m の p^(n - m) 個が解である。 3) １≦ k ＜ n で k が偶数で、(b/p) = 1 のとき。 k = 2s とする。 x^2 ≡ (p^(2s))b (mod p^n) x = (p^s)y とおくと y^2 ≡ b (mod p^(n - 2s)) この解の一つを v とする。 v(p^s), (v + p^(n - 2s))(p^s) = v(p^s) + p^(n - s), ... , (v + (p^s - 1)p^(n - 2s))(p^s) = v(p^s) + (p^s - 1)p^(n - s) の p^s 個が v から得られる解である。 y^2 ≡ b (mod p^(n - 2s)) のもう一つの解 v' も同様であるから、 合計 2(p^s) 個 の解が得られる。 879 名前：Kummer ◆g2BU0D6YN2 [2007/03/10(土) 23:07:15 ] a を奇数として合同方程式 x^2 ≡ a (mod 2^n) を考える。 まず x^2 ≡ a (mod 2) は唯一つの解 x ≡ 1 (mod 2) を持つ。 次に x^2 ≡ a (mod 4) を考える。 a が奇数だから x も奇数である。 x = 2k + 1 とすると x^2 = 4k^2 + 4k + 1 だから x^2 ≡ 1 (mod 4) である。 よって a ≡ 1 (mod 4) である。 よって x^2 ≡ a (mod 4) に解があるためには a ≡ 1 (mod 4) が 必要十分である。 このとき解は x ≡ 1 (mod 4) と x ≡ 3 (mod 4) の２個である。 次に x^2 ≡ a (mod 8) を考える。 a が奇数だから x も奇数である。 x = 4k ± 1 とすると、 x^2 = 16k^2 ± 8k + 1 だから x^2 ≡ 1 (mod 8) である。 よって x^2 ≡ a (mod 8) に解があるためには a ≡ 1 (mod 8) が 必要十分である。 このとき解は x ≡ 1 (mod 8) と x ≡ 3 (mod 8) x ≡ 5 (mod 8), x ≡ 7 (mod 8) の４個である。 880 名前：Kummer ◆g2BU0D6YN2 [2007/03/10(土) 23:23:47 ] [Dirichlet の整数論講義より] 今度は n ≧ 3 のとき a を奇数として合同方程式 x^2 ≡ a (mod 2^n) を考える。 x^2 ≡ a (mod 2^n) に解 c があるとする。 c^2 - a = (2^n)h とする。 x = c + (2^(n-1))y とおく。 x^2 = c^2 + (2^n)cy + (2^(2n-2))y^2 x^2 - a = (2^n)h + (2^n)cy + (2^(2n-2))y^2 n ≧ 3 だから 2n - 2 ≧ n + 1 よって x^2 - a ≡ (2^n)(h + cy) (mod 2^(n+1)) よって h + cy ≡ 0 (mod 2) なら x^2 ≡ a (mod 2^(n+1)) である。 c が奇数だから h + cy ≡ 0 (mod 2) となる y は存在する。 以上から x^2 ≡ a (mod 2^n) に解があれば、 x^2 ≡ a (mod 2^(n+1)) に解があることがわかった。 881 名前：Kummer ◆g2BU0D6YN2 [2007/03/10(土) 23:41:34 ] 命題 n ≧ 3 で a を奇数とする。 x^2 ≡ a (mod 2^n) に解があるためには、 a ≡ 1 (mod 8) が必要十分である。 証明 >>879 と >>880 より明らかである。 882 名前：Kummer ◆g2BU0D6YN2 [2007/03/10(土) 23:56:30 ] 命題 n ≧ 3 で a を奇数とする。 a ≡ 1 (mod 8) のとき x^2 ≡ a (mod 2^n) には４個の解がある。 証明(Dirichlet の整数論講義) x^2 ≡ a (mod 2^n) の解の一つを c とする。 x をこの方程式の任意の解とする。 (x - c)(x + c) ≡ 0 (mod 2^n) である。 x も c も奇数であるから x - c と x + c は偶数である。 よって ((x - c)/2)((x + c)/2) ≡ 0 (mod 2^(n-2)) である。 (x + c)/2 - (x - c)/2 = c は奇数だから (x - c)/2 と (x + c)/2 のどちらか一方は奇数である。 よって (x - c)/2 ≡ 0 (mod 2^(n-2)) または (x + c)/2 ≡ 0 (mod 2^(n-2)) である。 つまり x ≡ c (mod 2^(n-1)) または x ≡ -c (mod 2^(n-1)) よって x ≡ c (mod 2^n) または x ≡ c + 2^(n-1) (mod 2^n) x ≡ -c (mod 2^n) または x ≡ -c + 2^(n-1) (mod 2^n) 証明終 883 名前：Kummer ◆g2BU0D6YN2 [2007/03/11(日) 00:27:05 ] 今度は a が偶数のときに x^2 ≡ a (mod 2^n) を考える。 命題 a を偶数で a = (2^k)b, gcd(b, 2) = 1 とする。 n が偶数のとき n = 2m n が奇数のとき n = 2m - 1 とおく。 k ≧ n のとき x^2 ≡ a (mod 2^n) は 2^(n - m) 個の解をもつ。 証明 k ≧ n だから a ≡ 0 (mod 2^n) である。 よって x^2 ≡ 0 (mod 2^n) となる。 よって x ≡ 0 (mod 2^m) となる。 0, 2^m, 2(2^m), ..., (2^(n - m) - 1)2^m の 2^(n - m) 個が解である。 証明終 884 名前：Kummer ◆g2BU0D6YN2 [2007/03/11(日) 00:37:31 ] 命題 a を偶数で a = (2^k)b, gcd(b, 2) = 1 とする。 １≦ k ＜ n で k が奇数のとき x^2 ≡ a (mod 2^n) は解を持たない。 証明 >>874 と同様だが一応証明する。 x^2 ≡ a (mod 2^n) が解 x = c を持つとする。 ｃ^2 ≡ (2^k)b (mod 2^n) より c^2 は 2^k で割れる。 c = (2^s)d, gcd(d, 2) = 1 とする。 k = 2t + 1 とすると、2s ≧ 2t + 1 だから s ≧ t + 1 よって c^2 は 2t + 2 で割れる。 ｃ^2 ≡ (2^k)b (mod 2^n) で 2t + 2 ≦ n だから (2^(2t + 1))b ≡ 0 (mod 2^(2t + 2)) よって b ≡ 0 (mod 2) となり矛盾である。 証明終 885 名前：Kummer ◆g2BU0D6YN2 [2007/03/11(日) 00:49:27 ] 命題 a を偶数で a = (2^k)b, gcd(b, 2) = 1 とする。 1 ≦ k ＜ n で k が偶数のとき x^2 ≡ a (mod 2^n) が解を持つためには、 n = k + 1 のときは無条件 n = k + 2 のとき b ≡ 1 (mod 4) n ≧ k + 3 のとき b ≡ 1 (mod 8) が必要十分である。 証明 k = 2s とする。 x^2 ≡ (2^(2s))b (mod 2^n) x = (2^s)y とおくと y^2 ≡ b (mod 2^(n - k)) これと >>879 より上記の主張が出る。 証明 886 名前：Kummer ◆g2BU0D6YN2 [2007/03/11(日) 00:57:22 ] 命題 a を偶数で a = (2^k)b, gcd(b, 2) = 1 とする。 1 ≦ k ＜ n で k = 2s が偶数とする。 x^2 ≡ a (mod 2^n) が解を持つとき、その個数は n = k + 1 のときは 2^s 個 n = k + 2 のとき 2^(s+1) 個 n ≧ k + 3 のとき 2^(s+2) 個 である。 証明 >>885 より >>878 の 3) と同様にすればよい。 887 名前：Kummer ◆g2BU0D6YN2 [2007/03/11(日) 01:06:23 ] 以上で合同方程式 x^2 ≡ a (mod p^n) の解の様子はわかった。 a が p で割れる場合と p = 2 の場合も扱うと（難しくはないが）煩雑である。 888 名前：Kummer ◆g2BU0D6YN2 [2007/03/11(日) 02:07:07 ] p を奇素数とし gcd(a, p) = 1 のとき x^2 ≡ a (mod p) に解があるかどうかを決定するには、 Legendre の記号(前スレ３の746) (a/p) を計算すればよい。 (a/p) を計算する一つの方法は、 (a/p) ≡ a^((p - 1)/2) (mod p) (前スレ３の747) を使う。 p が大きいとき、この方法は効率が悪いように見えるが 実はそうでもない。 後で述べるが a^((p - 1)/2) を計算機で計算するのに効率のよい アルゴリズムがある。 (a/p) を計算する別の方法としては、a の素因数分解と 平方剰余の相互律(前スレ３の751)を使うものがある。 この方法は具体例で示したほうが分かりやすい。 p = 997 として (588/997) を計算してみよう。 588 = (7^2)・3・2^2 だから (588/997) = (7^2/997)(3/997)(2^2/997) = (3/997) 997 ≡ 1 (mod 4) だから平方剰余の相互律より (3/997) = (997/3) = (1/3) = 1 である。 よって (588/997) = 1 実際 183^2 ≡ 588 (mod 997) しかし、この方法は a の素因数分解が必要なので、大きい数の 計算には不向きである。 この不都合は次にのべる Jacobi の記号により解消される。 889 名前：Kummer ◆g2BU0D6YN2 [2007/03/11(日) 09:32:19 ] a を任意の有理整数とする。 >>100 を f(X) = X^2 - a に適用することにより、 x^2 ≡ a (mod m) の解は 各 x^2 ≡ a (mod (p_i)^(k_i)) の解が分かればよい。 しかし、この形の合同方程式の解の個数とその解法は原理的には 解決済みである(>>887)。 よって x^2 ≡ a (mod m) の解の個数と解法(中国式剰余定理を使う)も 解決されたとみてよい。 890 名前：Kummer ◆g2BU0D6YN2 [2007/03/11(日) 09:37:35 ] n ＞ 1 を奇数で n = (p_1)(p_2)... をその素因数分解とする。 m を gcd(m, n) = 1 となる任意の有理整数としたとき (m/n) を (m/n) = (m/p_1)(m/p_2)... と定義する。 (m/n) を Jacobi の記号という。 n が素数のときは (m/n) は Legendre の記号である。 よって Jacobi の記号は Legendre の記号の拡張になっている。 x^2 ≡ m (mod n) に解があるのは n の各素因数 p に対して (m/p) = 1 となることが必要十分である(>>866, >>889)。 ところが、(m/p) = -1 となる p が偶数個あっても (m/n) = 1 となる。 よって、(m/n) = 1 であっても x^2 ≡ m (mod n) に解があるとは 限らない。 891 名前：Kummer ◆g2BU0D6YN2 [2007/03/11(日) 09:48:36 ] 命題 a ≡ b (mod n) なら (a/n) = (b/n) である。 証明 n = Π p を n の素因数分解とする。 a ≡ b (mod p) だから (a/p) = (b/p) である。 よって Π (a/p) = Π (b/p) 即ち (a/n) = (b/n) である。 証明終 892 名前：Kummer ◆g2BU0D6YN2 [2007/03/11(日) 09:53:29 ] 命題 (ab/n) = (a/n)(b/n) である。 証明 n = Π p を n の素因数分解とする。 前スレ３の756より各 p に対して (ab/p) = (a/p)(b/p) である。 よって Π (ab/p) = Π (a/p)(b/p) = Π (a/p)Π (b/p) 即ち (ab/n) = (a/n)(b/n) である。 証明終 893 名前：Kummer ◆g2BU0D6YN2 [2007/03/11(日) 10:05:10 ] 補題 a, b を奇数とすれば (ab - 1)/2 ≡ (a - 1)/2 + (b - 1)/2 (mod 2) 証明 a - 1 と b - 1 は偶数だから (a - 1)(b - 1) ≡ 0 (mod 4) よって ab - a - b + 1 ≡ 0 (mod 4) ab - 1 ≡ (a - 1) + (b - 1) (mod 4) よって (ab - 1)/2 ≡ (a - 1)/2 + (b - 1)/2 (mod 2) 証明終 894 名前：Kummer ◆g2BU0D6YN2 [2007/03/11(日) 10:09:31 ] 補題 a, b を奇数とすれば (a^2b^2 - 1)/8 ≡ (a^2 - 1)/8 + (b^2 - 1)/8 (mod 2) 証明 a^2 - 1 ≡ 0 (mod 4) b^2 - 1 ≡ 0 (mod 4) よって (a^2 - 1)(b^2 - 1) ≡ 0 (mod 16) よって a^2b^2 - a^2 - b^2 + 1 ≡ 0 (mod 16) a^2b^2 - 1 ≡ (a^2 - 1) + (b^2 - 1) (mod 16) よって (a^2b^2 - 1)/8 ≡ (a^2 - 1)/8 + (b^2 - 1)/8 (mod 2) 証明終 895 名前：Kummer ◆g2BU0D6YN2 [2007/03/11(日) 10:16:27 ] 命題 m ＞ 1 と n ＞ 1 が奇数で gcd(m, n) = 1 のとき (m/n)(n/m) = (-1)^((m-1)/2)((n-1)/2) 証明 平方剰余の相互律(前スレ３の751)と >>893 より明らかである。 896 名前：Kummer ◆g2BU0D6YN2 [2007/03/11(日) 10:20:07 ] 命題 n ＞ 1 が奇数のとき (-1/n) = (-1)^((n-1)/2) 証明 平方剰余の第一補充法則(>>163)と >>893 より明らかである。 897 名前：Kummer ◆g2BU0D6YN2 [2007/03/11(日) 10:22:41 ] 命題 n ＞ 1 が奇数のとき (2/n) = (-1)^((n^2 - 1)/8) 証明 平方剰余の第２補充法則(>>53)と >>894 より明らかである。 898 名前：Kummer ◆g2BU0D6YN2 [2007/03/11(日) 11:04:32 ] Jacobi の記号(>>890)をつかうと a の素因数分解を使わずに (a/p) が 計算できる。 例として (365/1847) を計算する(Dirichletの例)。 1847 は素数である。 365 ≡ 1 (mod 4) だから >>895 より (365/1847) = (1847/365) 1847 ≡ 22 (mod 365) だから >>895 より (1847/365) = (22/365) >>892 より (22/365) = (2/365)(11/365) >>897 より (2/365) = -1 よって (365/1847) = -(11/365) >>895 より (11/365) = (365/11) = (2/11) = -1 よって (365/1847) = 1 実際 496^2 ≡ 365 (mod 1847) 899 名前：Kummer ◆g2BU0D6YN2 [2007/03/11(日) 11:35:11 ] Legendre の記号 (a/p) を計算するために Jacobi の記号を使う方法は 相互律と素因数分解を使う方法より遥かに早い。 高木は「初等整数論講義」(第２版)の p.85 で 「このように Jacobi の記号を用いて Legendre の記号 (a/p) の値の計算 の手続きをいくぶん節約することができるのであるが、ただそれだけを 目標にして、 Jacobi の記号を掲出したのではない。 それはあまりにことごとしいであろう。」 と書いている。 理論的観点からはその通りかもしれない。 しかし、計算アルゴリズムという観点から見ると「いくぶん節約」 どころではなく遥かに早い。 大きい数の素因数分解は非常に遅いのである。 900 名前：１３２人目の素数さん mailto:sage [2007/03/11(日) 12:20:00 ] 21 901 名前：１３２人目の素数さん mailto:sage [2007/03/11(日) 12:21:00 ] 20 902 名前：１３２人目の素数さん mailto:sage [2007/03/11(日) 12:22:00 ] 19 903 名前：１３２人目の素数さん mailto:sage [2007/03/11(日) 12:23:00 ] 18 904 名前：１３２人目の素数さん mailto:sage [2007/03/11(日) 12:24:00 ] 17 905 名前：１３２人目の素数さん mailto:sage [2007/03/11(日) 12:25:00 ] 16 906 名前：１３２人目の素数さん mailto:sage [2007/03/11(日) 13:31:00 ] 15 907 名前：１３２人目の素数さん mailto:sage [2007/03/11(日) 13:32:00 ] 14 908 名前：１３２人目の素数さん mailto:sage [2007/03/11(日) 13:33:00 ] 13 909 名前：１３２人目の素数さん mailto:sage [2007/03/11(日) 13:34:00 ] 12 910 名前：１３２人目の素数さん mailto:sage [2007/03/11(日) 13:35:00 ] 11 911 名前：１３２人目の素数さん mailto:sage [2007/03/11(日) 13:36:00 ] 10 912 名前：Kummer ◆g2BU0D6YN2 [2007/03/11(日) 20:20:31 ] >>888 で述べた a^((p - 1)/2) (mod p) を効率よく計算する アルゴリズムを紹介する。 Cohen の A course in computational algebraic number theory に 述べられている方法である。 問題を一般にして、G を群とし、G の元 g と n ＞ 0 に対して g^n を計算する方法を考える。 n を２進数で表示して n = Σ(ε_i)2^i とする。 ε_i は 0 または 1 である。 g^n = Π g^(2^i) である。ここで i は ε_i = 1 となる i を動く。 各 g^(2^i) は、最初に z = g として z = z・z を繰り返せばよい。 ここで = は右辺を左辺に代入することを表す。 各 g^(2^i) を計算したら順次、前に計算した結果に掛けていく。 これで終わりである。 このアルゴリズムを擬似コードで書くと次のようになる。 913 名前：Kummer ◆g2BU0D6YN2 [2007/03/11(日) 20:24:46 ] N = n z = g y = 1 do while(true) 　　if N is odd then 　　　　y = yz 　　end if 　　N = [N/2] 　　if N = 0 then 　　　　exit 　　else 　　　　z = zz 　　end if end do [N/2] は N/2 の整数部分を表す。 コンピュータ言語のPascal風の擬似ｺ-ﾄﾞの説明は不要だろう。 914 名前：Kummer ◆g2BU0D6YN2 [2007/03/11(日) 21:01:37 ] p を奇素数、 a を有理整数で gcd(a, p) = 1 とする。 (a/p) = 1 のときに x^2 ≡ a (mod p) を解く方法を考える。 x = 1 から順番に x^2 ≡ a (mod p) を確かめていくのは p が大きい ときにはコンピュータを使ったとしても実用的ではない。 ここでも Cohen 本から効率的なアルゴリズムを紹介する。 p が特殊な場合は解はすぐ得られる。 p ≡ 3 (mod 4) のときは x = a^((p + 1)/4) が解である(これを計算するのは>>912を使う)。 何故なら x^2 = a^((p + 1)/2) = aa^((p - 1)/2) (a/p) = 1 だから a^((p - 1)/2) ≡ 1 (mod p) よって x^2 ≡ a (mod p) 915 名前：Kummer ◆g2BU0D6YN2 [2007/03/11(日) 21:15:14 ] 命題 p を奇素数で p ≡ 5 (mod 8) とする。 a を有理整数で gcd(a, p) = 1、(a/p) = 1 とする。 a^((p - 1)/2) ≡ 1 (mod p) だから a^((p - 1)/4) ≡ ±1 (mod p) である。 このとき a^((p - 1)/4) ≡ 1 (mod p) なら x = a^((p + 3)/8) は x^2 ≡ a (mod p) の解である。 a^((p - 1)/4) ≡ -1 (mod p) なら x = 2a(4a)^((p - 5)/8) は x^2 ≡ a (mod p) の解である。 証明 a^((p - 1)/4) ≡ 1 (mod p) なら x^2 = a^((p + 3)/4) = aa^((p - 1)/4) ≡ 1 (mod p) p ≡ 5 (mod 8) と、平方剰余の第２補充法則より (2/p) = (-1)^((p^2 - 1)/8) = -1 よって 2^((p - 1)/2) ≡ -1 (mod p) だから x^2 = 4a^2(4a)^((p - 5)/4) = a(4a)^((p - 1)/4) = a(2^((p - 1)/2))a^((p - 1)/4) ≡ a (mod p) 証明終 916 名前：Kummer ◆g2BU0D6YN2 [2007/03/11(日) 22:01:44 ] >>914 と >>915 より p ≡ 3 (mod 4) と p ≡ 5 (mod 8) のときは x^2 ≡ a (mod p) の解は求まった。 残るのは p ≡ 1 (mod 8) の場合である。 p - 1 = (2^e)r, r は奇数とする。 (Z/pZ)^* は位数 p - 1 の巡回群だから、その 2-Sylow 部分群(>>790) P は位数 2^e の巡回群である。 a^(p - 1)/2 = (a^r)^(2^(e-1)) ≡ 1 (mod p) よって b = a^r (mod p) とおくと b^(2^(e-1)) = 1 である。 P の生成元を z とする。 b = z^s とすると z^(s2^(e-1)) = 1 より s は偶数である。 -s ≡ k (mod 2^e) で 0 ≦ k ＜ 2^e となるものがある。 k も偶数である。 bz^k = 1 である。 x = (a^(r + 1)/2)z^k/2 とおく。 x^2 = (a^(r + 1))z^k = abz^k ≡ a (mod p) よって問題は z と k を求めることに帰着する。 n を p と素な有理整数とする。 z = n^r (mod p) とおく。 z^(2^e) = (n^r)^(2^e) = n^(p - 1) ≡ 1 (mod p) z^(2^(e-1)) = (n^r)^(2^(e-1)) = n^(p - 1)/2 よって (n/p) = -1 なら z は P の生成元である。 n をランダムに選べば 50% の確率で (n/p) = -1 となるから z は簡単に求まる。 917 名前：Kummer ◆g2BU0D6YN2 [2007/03/11(日) 23:11:38 ] 今度は k を求める方法を考える。 b = a^r (mod p) とおいた。b^(2^(e-1)) = 1 である。 b^2^m = 1 となる最小の m ≧ 1 を求める。 b_1 = bz^2^(e-m) とおく。 (b_1)^2^(m-1) = (b^2^(m-1))(z^2^(e-1)) = (-1)^2 = 1 よって b_1 の位数は 2^(m-1) 以下である。 以上の処理を繰り返せば bz^k = 1 となる k が求まる。 918 名前：Kummer ◆g2BU0D6YN2 [2007/03/11(日) 23:18:29 ] >>616 と >>617 のアルゴリズムは Tonelli と Shanks による。 919 名前：１３２人目の素数さん mailto:sage [2007/03/12(月) 09:06:00 ] 12 920 名前：１３２人目の素数さん mailto:sage [2007/03/12(月) 09:07:00 ] 11 921 名前：１３２人目の素数さん mailto:sage [2007/03/12(月) 09:08:00 ] 10 922 名前：１３２人目の素数さん mailto:sage [2007/03/12(月) 09:09:00 ] 11 923 名前：１３２人目の素数さん mailto:sage [2007/03/12(月) 12:14:00 ] 10 924 名前：１３２人目の素数さん mailto:sage [2007/03/12(月) 12:15:00 ] 9 925 名前：１３２人目の素数さん mailto:sage [2007/03/12(月) 12:16:00 ] 8 926 名前：１３２人目の素数さん mailto:sage [2007/03/12(月) 12:17:00 ] 7 927 名前：１３２人目の素数さん mailto:sage [2007/03/12(月) 12:18:00 ] 6 928 名前：１３２人目の素数さん mailto:sage [2007/03/12(月) 12:19:00 ] 5 929 名前：Kummer ◆g2BU0D6YN2 [2007/03/12(月) 21:02:02 ] >>616 と >>617 のアルゴリズムがどこから来たのかがやや分かりにくい。 これを私の想像で説明して見よう。 >>916 の記号を使う。 b = a^r (mod p) とおくと b^(2^(e-1)) = 1 である。 よって b ∈ P である。 この観察が最初のキーポイントだと思われる。 y = a^(r + １)/2 (mod p) とおく。 y^2 = a^(r + １) = ab である。 w^2 = b となる w が求まれば y^2 = aw^2 よって x = yw^(-1) おくと、 x^2 = (y^2)(w^(-2)) = abb^(-1) = a となって x^2 ≡ a (mod p) が解ける。 従って、w^2 = b となる w を求めればよい。 これには P の生成元 z と b = z^s となる s を求めればよい。 以上が Tonelli と Shanks の基本アイデアだと思われる。 930 名前：Kummer ◆g2BU0D6YN2 [2007/03/12(月) 21:11:51 ] 訂正 >>929 >w^2 = b となる w が求まれば >y^2 = aw^2 >よって x = yw^(-1) おくと、 >x^2 = (y^2)(w^(-2)) = abb^(-1) = a >となって x^2 ≡ a (mod p) が解ける。 w^2 = b となる w が求まれば y^2 = aw^2 よって (yw^(-1))^2 = a よって x = yw^(-1) おけば x^2 = a となって x^2 ≡ a (mod p) が解ける。 931 名前：Kummer ◆g2BU0D6YN2 [2007/03/12(月) 21:21:51 ] >>916 や >>929 で a と a (mod p) を同一視している。 これは論理的にはおかしいがいわゆる記号の濫用 (abuse of notation)の一種(のつもり)です。 abuse of notation については英語版の wikipedia を参照。 932 名前：Kummer ◆g2BU0D6YN2 [2007/03/12(月) 21:27:44 ] 訂正 >>918 >>>616 と >>617 のアルゴリズムは Tonelli と Shanks による。 >>916 と >>917 のアルゴリズムは Tonelli と Shanks による。>>929 >>>616 と >>617 のアルゴリズムがどこから来たのかがやや分かりにくい。 >>916 と >>917 のアルゴリズムがどこから来たのかがやや分かりにくい。 933 名前：Kummer ◆g2BU0D6YN2 [2007/03/12(月) 23:25:52 ] 後の参照のため >>889 で述べたことの一部をもっと詳しく述べる。 命題 m ＞ 1 と a を有理整数で gcd(a, m) = 1 とする。 m = (2^e)r、r は奇数。 r の相異なる素因数の個数を s とする。 x^2 ≡ a (mod m) に解があるためには (1) e = 0 または e = 1 のときは r の各素因数 p に対して (a/p) = 1 が必要十分である。 この条件が満たされるとき解の個数は 2^s である。 (2) e = 2 のときは r の各素因数 p に対して (a/p) = 1 であり、さらに a ≡ 1 (mod 4) が必要十分である。 この条件が満たされるとき解の個数は 2^(s+1) である。 (3) e ≧ 3 のときは r の各素因数 p に対して (a/p) = 1 であり、さらに a ≡ 1 (mod 8) が必要十分である。 この条件が満たされるとき解の個数は 2^(s+2) である。 証明 (1) は >>866 と >>889 より直ちに出る。 (2) は >>866 と >>879 と >>889 より直ちに出る。 (3) は >>866 と >>881, >>882 と >>889 より直ちに出る。 934 名前：１３２人目の素数さん mailto:sage [2007/03/13(火) 00:00:38 ] 　　　　 　　　.， 　　　　 　　　.|　　　　　　　　　　　　　 　　　　　　　　　　　　.　　　　　　　　　　　　 、・　　　　　　ﾞ； 　　　　　　　､′　　　.　　　.　　.　　.′　　　　　　　.　　　　　　　.　　　　　　　._．t~´　　　　 　　　.’ 　　　　　　　ﾞ，　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　.l・^´ . ’　　　.　　　.　　.1　.　.._．・￣＼_ 　　 　　.　　 ；　.　.　.._＞~　　　.　　.，　　　 ，　...→_　　　　　　　　　　　　.l　　　､’ﾞ_､．‐　　 　　._．・/＜　.　.　.　.’ 　　　.　　　､，　..._．¨｀　　　　　　　 ’　　 　.|､。・｀.､’_　 　.，・¨¨“÷　　　，._、-・ﾍ´　　 　.　 ／゛ .．′　　.　　.　　.! 　　　　　　､，。・′・　　　　　　　　､1　　　 }・　.　.　..’　.､，　　　ﾞｶ　　　ﾞ，＾　　　 ’_　　　　　　　.ｿ”　 　.、．．　.　.} 　　　　　　 ；′　.　..’_　　　　.　　　､’　.　...1　　　　､}　　′　　ﾞﾂﾞ|　.　､，　　　　　.’_　　.　　､，・　　　 /　 　.｀､..../ 　　　　　　.；　　 　.　 ’　　　　.　　　､}　.　...l!　　.　.　.|　.　...＼・~ . |　.　.，　　　　　　 ’_　　　 ，’　 　.　 ｀．_　....}_ﾉ｀ 　　　　　　，　　.　　.　.’　　　　　　　ﾞ!　.　､’　　 　　.’　　　　　　､，　　′　　　.　　　､’、-　　.　　.　　.　　.｀¨¨′ 　　.　　.　.i　　　　　　　ﾞ’　　　　　　　　　　　　　　　　　　　　　　､｜ 　　.　　.　.l　　　　　　　　　　　　　　　　　　　　　　　　　　　　￣￣　　　 　.　.　.._ 　.　.　.i 　　　ﾞ，　　.　.　.-_　.　､； 　　　，・ﾅ・_　 　. ｀､　./ 　　､，　 　.)　　　　.｀j.´ 　　､l　、．-’　.　.　./ 　　.　　.　　.l　　　　　　　} 　､＝＝＝＝＝＝＝＝＝＝＝＝- 　　.　　.　　.|　 　. 、　.　..| 　　.　　.　　.’　.　､|　　　ﾞ’ 　　.　.}．-‐………………………， 　　　､|　　 　　.　 |＝＝・　.　.　.　.・ 　　　､’　　　 　　.’._、．｣ 　　　　　.　　　　./ ´ 　　.　　.　　.　　.，¨¨TTﾅﾅﾅ， 　　　　　　　　ﾞ＿_＿＿＿＿｜ 935 名前：１３２人目の素数さん mailto:sage [2007/03/13(火) 08:10:00 ] 12 936 名前：１３２人目の素数さん mailto:sage [2007/03/13(火) 08:11:00 ] 11 937 名前：１３２人目の素数さん mailto:sage [2007/03/13(火) 08:12:00 ] 10 938 名前：１３２人目の素数さん mailto:sage [2007/03/13(火) 08:13:00 ] 9 939 名前：１３２人目の素数さん mailto:sage [2007/03/13(火) 08:14:00 ] 8 940 名前：１３２人目の素数さん mailto:sage [2007/03/13(火) 08:15:00 ] 7 941 名前：Kummer ◆g2BU0D6YN2 [2007/03/14(水) 20:35:37 ] Tonelli-Shanks のアルゴリズム(>>916, >>917) を具体例に 適用してみる。 p = 2281 は素数で p ≡ 1 (mod 8) である。 因みに 2^p - 1 は Mersenne 素数である(岩波数学辞典の付録)。 Jacobi の記号を使って (365/2281) を計算すると、 (365/2281) = (2281/365) = (91/365) = (365/91) = (1/91) = 1 よって x^2 ≡ 365 (mod 2281) には解がある。 p - 1 = 2280 = 8・285 365^285 (mod 2281) を >>912, >>913 のアルゴリズムで電卓をつかって 計算すると、365^285 ≡ -1 (mod 2281) 同様に y = 365^(285+1)/2 = 365^143 ≡ 2139 (mod 2281) よって y^2 = 365^(285+1) ≡ -365 (mod 2281) 小さい数 n で (n/p) = -1 となるものを見つける。 n = 2, 3, 5, 7, ... と試していく。 p ≡ 1 (mod 8) だから >>53 より (2/2281) = 1 (3/2281) = (2281/3) = (1/3) = 1 (5/2281) = (2281/5) = (1/5) = 1 (7/2281) = (2281/7) = (-1/7) = -1 7^285 ≡ 1207 (mod 2281) よって z = 1207 (mod 2281) が (Z/pZ)^* の 2-Sylow 群の生成元 である(>>916)。 z^8 = 1 だから z^4 = -1 a = 365 (mod 2281) とおくと、y^2 = -a = a(z^4) よって y^2(z^4) = a (y(z^2))^2 = a よって x = y(z^2) = 2139*1571 ≡ 456 (mod 2281) が x^2 ≡ 365 (mod 2281) の解である。 942 名前：１３２人目の素数さん mailto:sage [2007/03/15(木) 12:14:00 ] 9 943 名前：１３２人目の素数さん mailto:sage [2007/03/15(木) 12:15:00 ] 8 944 名前：１３２人目の素数さん mailto:sage [2007/03/15(木) 12:16:00 ] 7 945 名前：１３２人目の素数さん mailto:sage [2007/03/15(木) 12:17:00 ] 6 946 名前：１３２人目の素数さん mailto:sage [2007/03/15(木) 12:18:00 ] 5 947 名前：１３２人目の素数さん mailto:sage [2007/03/15(木) 12:19:00 ] 4 948 名前：Kummer ◆g2BU0D6YN2 [2007/03/15(木) 12:56:50 ] Dirichlet の「整数論講義」に従って >>933 の応用として Wilson の定理の拡張(Gauss)を証明する。 その前に Wilson の定理について述べる。 命題(Wilson の定理) p を素数とすると (p - 1)! ≡ -1 (mod p) である。 証明 p = 2 のときは明らかだから p は奇素数とする。 mod p で多項式 X^(p - 1) - 1 を考える。 X^(p - 1) - 1 ≡ (X - 1)(X - 2) ... (X - (p - 1)) (mod p) である。 X = 0 とおくと - 1 ≡ ((-1)^(p - 1))(p - 1)!(mod p) である。 p - 1 は偶数だから (-1)^(p - 1) = 1 である。 よって (p - 1)! ≡ -1 (mod p) である。 証明終 949 名前：１３２人目の素数さん mailto:sage [2007/03/15(木) 18:25:20 ] 　　　　 　　　.， 　　　　 　　　.|　　　　　　　　　　　　　 　　　　　　　　　　　　.　　　　　　　　　　　　 、・　　　　　　ﾞ； 　　　　　　　､′　　　.　　　.　　.　　.′　　　　　　　.　　　　　　　.　　　　　　　._．t~´　　　　 　　　.’ 　　　　　　　ﾞ，　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　.l・^´ . ’　　　.　　　.　　.1　.　.._．・￣＼_ 　　 　　.　　 ；　.　.　.._＞~　　　.　　.，　　　 ，　...→_　　　　　　　　　　　　.l　　　､’ﾞ_､．‐　　 　　._．・/＜　.　.　.　.’ 　　　.　　　､，　..._．¨｀　　　　　　　 ’　　 　.|､。・｀.､’_　 　.，・¨¨“÷　　　，._、-・ﾍ´　　 　.　 ／゛ .．′　　.　　.　　.! 　　　　　　､，。・′・　　　　　　　　､1　　　 }・　.　.　..’　.､，　　　ﾞｶ　　　ﾞ，＾　　　 ’_　　　　　　　.ｿ”　 　.、．．　.　.} 　　　　　　 ；′　.　..’_　　　　.　　　､’　.　...1　　　　､}　　′　　ﾞﾂﾞ|　.　､，　　　　　.’_　　.　　､，・　　　 /　 　.｀､..../ 　　　　　　.；　　 　.　 ’　　　　.　　　､}　.　...l!　　.　.　.|　.　...＼・~ . |　.　.，　　　　　　 ’_　　　 ，’　 　.　 ｀．_　....}_ﾉ｀ 　　　　　　，　　.　　.　.’　　　　　　　ﾞ!　.　､’　　 　　.’　　　　　　､，　　′　　　.　　　､’、-　　.　　.　　.　　.｀¨¨′ 　　.　　.　.i　　　　　　　ﾞ’　　　　　　　　　　　　　　　　　　　　　　､｜ 　　.　　.　.l　　　　　　　　　　　　　　　　　　　　　　　　　　　　￣￣　　　 　.　.　.._ 　.　.　.i 　　　ﾞ，　　.　.　.-_　.　､； 　　　，・ﾅ・_　 　. ｀､　./ 　　､，　 　.)　　　　.｀j.´ 　　､l　、．-’　.　.　./ 　　.　　.　　.l　　　　　　　} 　､＝＝＝＝＝＝＝＝＝＝＝＝- 　　.　　.　　.|　 　. 、　.　..| 　　.　　.　　.’　.　､|　　　ﾞ’ 　　.　.}．-‐………………………， 　　　､|　　 　　.　 |＝＝・　.　.　.　.・ 　　　､’　　　 　　.’._、．｣ 　　　　　.　　　　./ ´ 　　.　　.　　.　　.，¨¨TTﾅﾅﾅ， 　　　　　　　　ﾞ＿_＿＿＿＿｜ 950 名前：１３２人目の素数さん mailto:sage [2007/03/15(木) 18:35:50 ] うんこーーーーーーー 951 名前：Kummer ◆g2BU0D6YN2 [2007/03/15(木) 21:46:58 ] Wilson の定理を一般の mod m の場合に拡張するためには >>948 の 証明ではうまくいかない。 そこで拡張可能な証明を紹介する。 Wilson の定理(>>948)の別証 p = 2 のときは明らかだから p は奇素数とする。 (Z/pZ)^* を以下の同値関係で類別する。 x と y を (Z/pZ)^* の元としたとき y = x^(-1) のとき x と y は 同値と定義する。 x = x^(-1) となるのは x^2 = 1 のときに限る。つまり x = ±1 の時に限る。 x ≠ x^(-1) のとき、つまり x ≠ ±1 のときは x の属す同値類は {x, x^(-1)} である。 よって (Z/pZ)^* の同値類は以下のタイプで尽くされる。 {1}, {-1}, {x, x^(-1)} ここで x ≠ ±1 xx^(-1) = 1 であるから (Z/pZ)^* の ±1 以外の全ての元の積は 1 である。 よって (Z/pZ)^* の全ての元の積は 1(-1) = -1 である。 証明終 952 名前：１３２人目の素数さん mailto:sage [2007/03/15(木) 21:47:27 ] うんこ 953 名前：Kummer ◆g2BU0D6YN2 [2007/03/15(木) 22:07:58 ] m ＞ 2 を有理整数として (Z/mZ)^* を考える。 (Z/mZ)^* を以下の同値関係で類別する。 x と y を (Z/mZ)^* の元としたとき y = x^(-1) のとき x と y は 同値と定義する。 x = x^(-1) となるのは x^2 = 1 のときに限る。 よって (Z/mZ)^* の同値類は以下のタイプで尽くされる。 {a}, {b, b^(-1)} ここで a^2 = 1, b^2 ≠ 1 よって (Z/mZ)^* の元 b で b^2 ≠ 1 となるもの全ての積は 1 である。 よって S = {a ∈ (Z/pZ)^* ; a^2 = 1} とおくと、 (Z/mZ)^* の全ての元の積は S の全ての元の積と一致する。 S を以下の同値関係で類別する。 x と y を S の元としたとき y = -x のとき x と y は 同値と定義する。 x = -x となるのは 2x = 0 のときに限る。 x = c (mod m) とすると 2c ≡ 0 (mod m) である。 gcd(c, m) = 1 だから 2 ≡ 0 (mod m) である。 m ＞ 2 であるからこれはありえない。 よって S の同値類は以下のタイプで尽くされる。 {b, -b} よって S の全ての元の積は b(-b) = -b^2 = -1 の(|S|/2)乗である。 これは |S|/2 が偶数、つまり |S| ≡ 0 (mod 4) のときは 1 そうでないときは -1 である。 954 名前：Kummer ◆g2BU0D6YN2 [2007/03/15(木) 22:33:22 ] >>833 より x^2 ≡ 1 (mod m) の解の個数、つまり |S| は (1) m = p^n または 2p^n のとき |S| = 2 ここで p は奇素数で n ≧ 1 (2) m = 4 のとき |S| = 2 (3) m = 4r、r は奇数 ＞ 1 のとき |S| = 2^(s + 1) ここで s は r の相異なる素因数の個数である。 (4) m = (2^e)r, e ≧ 3, r は奇数のときは |S| = 2^(s + 1) 以上から |S| = 2 となるのは (1) と (2) の場合であり、 (3) と (4) の場合は |S| ≡ 0 (mod 4) である。 よって >>953 より次の命題が得られる。 命題(Wilson の定理の拡張) m ＞ 2 を有理整数とする。 (Z/mZ)^* の全ての元の積は以下のようになる。 (1) m = 4 または m = p^n または 2p^n のとき積は -1 ここで p は奇素数で n ≧ 1 (2) 上記以外の場合、積は 1 955 名前：Kummer ◆g2BU0D6YN2 [2007/03/15(木) 22:40:46 ] >>954 の命題(Wilson の定理の拡張)は Gauss が初めて証明した (Disquisitiones art. 78)。 956 名前：Kummer ◆g2BU0D6YN2 [2007/03/15(木) 22:49:18 ] Wilson の定理(>>948) の逆も成り立つ。 命題 n ＞ 1 を有理整数とする。 (n - 1)! ≡ -1 (mod n) なら n は素数である。 証明 n が素数でないとすると p ＜ n となる素数 p で n を割るものがある。 p ≦ n - 1 だから (n - 1)! ≡ 0 (mod p) である。 一方、(n - 1)! ≡ -1 (mod n) だから (n - 1)! ≡ -1 (mod p) である。 よって -1 ≡ 0 (mod p) である。 これは矛盾である。 証明終 957 名前：１３２人目の素数さん mailto:sage [2007/03/15(木) 23:02:24 ] 　　　　 　　　.， 　　　　 　　　.|　　　　　　　　　　　　　 　　　　　　　　　　　　.　　　　　　　　　　　　 、・　　　　　　ﾞ； 　　　　　　　､′　　　.　　　.　　.　　.′　　　　　　　.　　　　　　　.　　　　　　　._．t~´　　　　 　　　.’ 　　　　　　　ﾞ，　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　.l・^´ . ’　　　.　　　.　　.1　.　.._．・￣＼_ 　　 　　.　　 ；　.　.　.._＞~　　　.　　.，　　　 ，　...→_　　　　　　　　　　　　.l　　　､’ﾞ_､．‐　　 　　._．・/＜　.　.　.　.’ 　　　.　　　､，　..._．¨｀　　　　　　　 ’　　 　.|､。・｀.､’_　 　.，・¨¨“÷　　　，._、-・ﾍ´　　 　.　 ／゛ .．′　　.　　.　　.! 　　　　　　､，。・′・　　　　　　　　､1　　　 }・　.　.　..’　.､，　　　ﾞｶ　　　ﾞ，＾　　　 ’_　　　　　　　.ｿ”　 　.、．．　.　.} 　　　　　　 ；′　.　..’_　　　　.　　　､’　.　...1　　　　､}　　′　　ﾞﾂﾞ|　.　､，　　　　　.’_　　.　　､，・　　　 /　 　.｀､..../ 　　　　　　.；　　 　.　 ’　　　　.　　　､}　.　...l!　　.　.　.|　.　...＼・~ . |　.　.，　　　　　　 ’_　　　 ，’　 　.　 ｀．_　....}_ﾉ｀ 　　　　　　，　　.　　.　.’　　　　　　　ﾞ!　.　､’　　 　　.’　　　　　　､，　　′　　　.　　　､’、-　　.　　.　　.　　.｀¨¨′ 　　.　　.　.i　　　　　　　ﾞ’　　　　　　　　　　　　　　　　　　　　　　､｜ 　　.　　.　.l　　　　　　　　　　　　　　　　　　　　　　　　　　　　￣￣　　　 　.　.　.._ 　.　.　.i 　　　ﾞ，　　.　.　.-_　.　､； 　　　，・ﾅ・_　 　. ｀､　./ 　　､，　 　.)　　　　.｀j.´ 　　､l　、．-’　.　.　./ 　　.　　.　　.l　　　　　　　} 　､＝＝＝＝＝＝＝＝＝＝＝＝- 　　.　　.　　.|　 　. 、　.　..| 　　.　　.　　.’　.　､|　　　ﾞ’ 　　.　.}．-‐………………………， 　　　､|　　 　　.　 |＝＝・　.　.　.　.・ 　　　､’　　　 　　.’._、．｣ 　　　　　.　　　　./ ´ 　　.　　.　　.　　.，¨¨TTﾅﾅﾅ， 　　　　　　　　ﾞ＿_＿＿＿＿｜ 958 名前：１３２人目の素数さん mailto:sage [2007/03/16(金) 01:35:00 ] 11 959 名前：１３２人目の素数さん mailto:sage [2007/03/16(金) 01:36:00 ] 10 960 名前：１３２人目の素数さん mailto:sage [2007/03/16(金) 01:37:00 ] 9 961 名前：１３２人目の素数さん mailto:sage [2007/03/16(金) 01:38:00 ] 8 962 名前：１３２人目の素数さん mailto:sage [2007/03/16(金) 01:39:00 ] 7 963 名前：１３２人目の素数さん mailto:sage [2007/03/16(金) 01:40:00 ] 6 964 名前：１３２人目の素数さん mailto:sage [2007/03/16(金) 06:49:00 ] 5 965 名前：１３２人目の素数さん mailto:sage [2007/03/16(金) 06:50:00 ] 4 966 名前：１３２人目の素数さん mailto:sage [2007/03/16(金) 06:51:00 ] 3 967 名前：１３２人目の素数さん mailto:sage [2007/03/16(金) 06:52:00 ] 2 968 名前：１３２人目の素数さん mailto:sage [2007/03/16(金) 06:53:00 ] 1 969 名前：１３２人目の素数さん mailto:sage [2007/03/16(金) 06:54:00 ] 0 970 名前：１３２人目の素数さん mailto:sage [2007/03/16(金) 07:46:06 ] 次スレ立てておきました。 代数的整数論 005 science6.2ch.net/test/read.cgi/math/1173998720/ 971 名前：Kummer ◆g2BU0D6YN2 [2007/03/16(金) 12:59:01 ] >>970 有難うございます。 972 名前：Kummer ◆g2BU0D6YN2 [2007/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 [2007/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 [2007/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 [2007/03/17(土) 03:31:02 ] >>974 今の場合、2^p - 1 が Mersenne数であるということに特に意味があるわけではない。 適当な大きさの素数が欲しかっただけである。 976 名前：Kummer ◆g2BU0D6YN2 [2007/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 [2007/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 [2007/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 [2007/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 [2007/03/17(土) 20:44:05 ] 訂正 >>978 >さらに、このとき解は順序と符号を除いて一つである。 さらに、このとき解は符号を除いて一つである。 981 名前：Kummer ◆g2BU0D6YN2 [2007/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 [2007/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 [2007/03/18(日) 02:14:29 ] >>981 と >>982 から次の命題が得られる。 命題(Fermat-Euler) p を 3 以外の奇素数とする。 p = x^2 + 3y^2 が有理整数解を持つためには p ≡ 1 (mod 3) が必要十分である。 さらに、このとき解は符号を除いて一つである。 984 名前：Kummer ◆g2BU0D6YN2 [2007/03/18(日) 02:33:12 ] >>978 の命題は Fermat に知られていたが初めて証明したのは Euler らしい。らしいというのは Gauss が Disquisitiones の art. 182 に Lagrange が最初に証明したと書いているからである。 しかもはっきりと Euler は証明に成功しなかったと書いている。 しかし、Weil は「数論」で Euler が証明したと書いている。 985 名前：１３２人目の素数さん [2007/03/18(日) 02:45:40 ] Kummer ◆g2BU0D6YN2 かっこいい 986 名前：１３２人目の素数さん mailto:sage [2007/03/18(日) 02:48:40 ] @ 987 名前：Kummer ◆g2BU0D6YN2 [2007/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 [2007/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 [2007/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 [2007/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 [2007/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 [2007/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) が必要十分である。 上記のいずれの場合も解は符号を除いて一意である。

---

---

[ 新着レスの取得/表示 (agate) ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef