最終更新日時 2011年03月05日 (土) 21時44分13秒
代数的整数論 004 (851-950)
元スレ： http://science6.2ch.net/test/read.cgi/math/1164286624/851-950
ログ元： http://yomi.mobi/read.cgi/science6/science6_math_1164286624/851-950
ログ元： http://yomi.mobi/read.cgi/science6/science6_math_1164286624/851-950
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 ]
うんこーーーーーーー
