※MathJaxの数式表示に少し時間がかかります。
10.1
(a)
m=2のときはB=1\pmod{2}で明らか。以下m\geq3とする。
S=\{b_1,b_2,..,b_{\varphi(m)}\}を1とmの間でmと互いに素な整数の集合とする。Sについてまず次の補題を証明する。
補題1:b_{\varphi(m)}\equiv-1\pmod{m}。
(証明) \gcd(m,m-1)=dなら、d\mid[m-(m-1)]=1だから、d=1。故にm-1\in Sで、明らかにSの最大元だから、b_{\varphi(m)}=m-1\equiv-1\pmod{m}。
補題2:\mid S\mid=\varphi(m)は偶数である。
(証明) Eulerの公式a^{\varphi(m)}\equiv1\pmod{m}において、補題1によりa=-1とおけるから、(-1)^{\varphi(m)}\equiv1\pmod{m}。m\geq3なので\varphi(m)は偶数。
補題3:b\in Sなら(m-b)\in Sである。
(証明) \gcd(m-b,m)=d>1とすれば、m-b=db', m=dm' (\gcd(b',m')=1)だが、b=m-db'=d(m'-b')だからd\mid bとなるので、\gcd(b,m)\geq d>1となり\gcd(b,m)=1と矛盾。
補題4:b\in Sに対し、b^2\equiv1\pmod{m}であるか、またはbb^{-1}\equiv1\pmod{m}となるb^{-1}\not\equiv b\pmod{m} (b^{-1}\in S)がただ一つ存在するかのいずれかである。
(証明) mが素数の場合については、すでに練習問題9.2の解答で示したので、mは合成数とする。\gcd(b,m)=1だから、bx+my=1の整数解が存在する。つまりあるx\equiv b^{-1}\pmod{m}が存在してbb^{-1}\equiv1\pmod{m}かつ\gcd(b^{-1},m)=1となるから、b^{-1}\in S。b^{-1}\not\equiv b\pmod{m}の場合、別の解x\equiv b'^{-1}\pmod{m}が存在したとすると、bb^{-1}\equiv bb'^{-1}\pmod{m}だが\gcd(b,m)=1なので練習問題8.2によりb^{-1}\equiv b'^{-1}\pmod{m}。
練習問題10.1の証明:
mが素数の場合と違い、b^2\equiv1\pmod{m}となるb\not\equiv\pm1\pmod{m}があってもよいのだが、そのようなbについて、補題3によりm-bもSの元で(m-b)^2\equiv b^2\equiv1\pmod{m}となり、b(m-b)\equiv-b^2\equiv-1\pmod{m}である。補題4と合わせると、Sの元はb^2\not\equiv1\pmod{m}, (b^{-1})^2\not\equiv1\pmod{m}, bb^{-1}\equiv1\pmod{m}となる2つ組(b,b^{-1})と、b^2\equiv(m-b)^2\equiv1\pmod{m}, b(m-b)\equiv-1\pmod{m}となる2つ組(b,m-b)とからなる。
補題2により偶数の元を持つSは、これらの、積がmを法として\pm1となる2つ組で尽くされる。したがって、Sの元すべての積B=b_1b_2...b_{\varphi(m)}\equiv\pm1\pmod{m}。
さらに詳細な性質が練習問題12.4で調べられている。
(b)
mがm\geq3の素数の場合はWilsonの定理(練習問題9.2)によりB=(m-1)!\equiv-1\pmod{m}。m=2ならB=1\equiv1\pmod{2}。
合成数のm\leq100について
B\equiv1\pmod{m}となるm:
8,12,15,16,20,21,24,28,30,32,33,35,36,39,40,
42,44,45,48,51,52,55,56,57,60,63,64,65,66,68,
69,70,72,75,76,77,78,80,84,85,87,88,90,91,92,93,95,96,99,100
B\equiv-1\pmod{m}となるm:
4,6,9,10,14,18,22,25,26,27,34,38,46,49,50,54,58,62,74,81,82,86,94,98
B=b_1b_2...b_{\varphi(2m)}\equiv-1\pmod{2m}となるのは、
mが素数の冪
mが素数の冪の2倍
mが奇数の平方数
になりそう?
10.2
3750=2\cdot3\cdot5^4なので、\gcd(3750,n)\ne1となるn\in\mathbb{N}は2,3,5の倍数で、\mathrm{LCM}(2,3,5)=30ごとに繰り返し現れる。30までの自然数の中に2,3,5の倍数は22個あるから、\varphi(3750)=(3750/30)\cdot(30-22)=1000。
条件(a)について、\gcd(3750,7)=1なのでEulerの公式から、a\equiv7^{3003}=(7^{\varphi(3750)})^3\cdot7^3\equiv7^3=343\pmod{3750}。7\mid343なので条件(c)からa\ne343。次に条件(a)を満たすのはa=343+3750=4093となり、4093は条件(b)(c)を共に満たす。条件(b)を満たすのは4093だけなので、a=4093。
10.3
(a)
Fermatの小定理により、3,11,17のいずれを法としても0に合同でない数aについて、a^{560}=(a^2)^{280}\equiv1\pmod{3}, a^{560}=(a^{10})^{56}\equiv1\pmod{11}, a^{560}=(a^{16})^{25}\equiv1\pmod{17}が成り立つ。これよりa^{560}=3q_1+1=11q_2+1=17q_3+1 (q_1,q_2,q_3\in\mathbb{N})と書けるので、a^{560}=3\cdot11\cdot17q+1=561q+1 (q\in\mathbb{N})。したがってa^{560}\equiv1\pmod{561}となり、561はCarmichael数。
(b)
561, 1105, 1729, 2465...無数にある。
詳しくはウィキペ。
10.1
(a)
m=2のときはB=1\pmod{2}で明らか。以下m\geq3とする。
S=\{b_1,b_2,..,b_{\varphi(m)}\}を1とmの間でmと互いに素な整数の集合とする。Sについてまず次の補題を証明する。
補題1:b_{\varphi(m)}\equiv-1\pmod{m}。
(証明) \gcd(m,m-1)=dなら、d\mid[m-(m-1)]=1だから、d=1。故にm-1\in Sで、明らかにSの最大元だから、b_{\varphi(m)}=m-1\equiv-1\pmod{m}。
補題2:\mid S\mid=\varphi(m)は偶数である。
(証明) Eulerの公式a^{\varphi(m)}\equiv1\pmod{m}において、補題1によりa=-1とおけるから、(-1)^{\varphi(m)}\equiv1\pmod{m}。m\geq3なので\varphi(m)は偶数。
補題3:b\in Sなら(m-b)\in Sである。
(証明) \gcd(m-b,m)=d>1とすれば、m-b=db', m=dm' (\gcd(b',m')=1)だが、b=m-db'=d(m'-b')だからd\mid bとなるので、\gcd(b,m)\geq d>1となり\gcd(b,m)=1と矛盾。
補題4:b\in Sに対し、b^2\equiv1\pmod{m}であるか、またはbb^{-1}\equiv1\pmod{m}となるb^{-1}\not\equiv b\pmod{m} (b^{-1}\in S)がただ一つ存在するかのいずれかである。
(証明) mが素数の場合については、すでに練習問題9.2の解答で示したので、mは合成数とする。\gcd(b,m)=1だから、bx+my=1の整数解が存在する。つまりあるx\equiv b^{-1}\pmod{m}が存在してbb^{-1}\equiv1\pmod{m}かつ\gcd(b^{-1},m)=1となるから、b^{-1}\in S。b^{-1}\not\equiv b\pmod{m}の場合、別の解x\equiv b'^{-1}\pmod{m}が存在したとすると、bb^{-1}\equiv bb'^{-1}\pmod{m}だが\gcd(b,m)=1なので練習問題8.2によりb^{-1}\equiv b'^{-1}\pmod{m}。
練習問題10.1の証明:
mが素数の場合と違い、b^2\equiv1\pmod{m}となるb\not\equiv\pm1\pmod{m}があってもよいのだが、そのようなbについて、補題3によりm-bもSの元で(m-b)^2\equiv b^2\equiv1\pmod{m}となり、b(m-b)\equiv-b^2\equiv-1\pmod{m}である。補題4と合わせると、Sの元はb^2\not\equiv1\pmod{m}, (b^{-1})^2\not\equiv1\pmod{m}, bb^{-1}\equiv1\pmod{m}となる2つ組(b,b^{-1})と、b^2\equiv(m-b)^2\equiv1\pmod{m}, b(m-b)\equiv-1\pmod{m}となる2つ組(b,m-b)とからなる。
補題2により偶数の元を持つSは、これらの、積がmを法として\pm1となる2つ組で尽くされる。したがって、Sの元すべての積B=b_1b_2...b_{\varphi(m)}\equiv\pm1\pmod{m}。
さらに詳細な性質が練習問題12.4で調べられている。
(b)
mがm\geq3の素数の場合はWilsonの定理(練習問題9.2)によりB=(m-1)!\equiv-1\pmod{m}。m=2ならB=1\equiv1\pmod{2}。
合成数のm\leq100について
B\equiv1\pmod{m}となるm:
8,12,15,16,20,21,24,28,30,32,33,35,36,39,40,
42,44,45,48,51,52,55,56,57,60,63,64,65,66,68,
69,70,72,75,76,77,78,80,84,85,87,88,90,91,92,93,95,96,99,100
B\equiv-1\pmod{m}となるm:
4,6,9,10,14,18,22,25,26,27,34,38,46,49,50,54,58,62,74,81,82,86,94,98
B=b_1b_2...b_{\varphi(2m)}\equiv-1\pmod{2m}となるのは、
mが素数の冪
mが素数の冪の2倍
mが奇数の平方数
になりそう?
10.2
3750=2\cdot3\cdot5^4なので、\gcd(3750,n)\ne1となるn\in\mathbb{N}は2,3,5の倍数で、\mathrm{LCM}(2,3,5)=30ごとに繰り返し現れる。30までの自然数の中に2,3,5の倍数は22個あるから、\varphi(3750)=(3750/30)\cdot(30-22)=1000。
条件(a)について、\gcd(3750,7)=1なのでEulerの公式から、a\equiv7^{3003}=(7^{\varphi(3750)})^3\cdot7^3\equiv7^3=343\pmod{3750}。7\mid343なので条件(c)からa\ne343。次に条件(a)を満たすのはa=343+3750=4093となり、4093は条件(b)(c)を共に満たす。条件(b)を満たすのは4093だけなので、a=4093。
10.3
(a)
Fermatの小定理により、3,11,17のいずれを法としても0に合同でない数aについて、a^{560}=(a^2)^{280}\equiv1\pmod{3}, a^{560}=(a^{10})^{56}\equiv1\pmod{11}, a^{560}=(a^{16})^{25}\equiv1\pmod{17}が成り立つ。これよりa^{560}=3q_1+1=11q_2+1=17q_3+1 (q_1,q_2,q_3\in\mathbb{N})と書けるので、a^{560}=3\cdot11\cdot17q+1=561q+1 (q\in\mathbb{N})。したがってa^{560}\equiv1\pmod{561}となり、561はCarmichael数。
(b)
561, 1105, 1729, 2465...無数にある。
詳しくはウィキペ。
0 件のコメント :
コメントを投稿