※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 件のコメント :
コメントを投稿