17.1
1147=31·37, 329=7·47なのでgcd(329,1147)=1。
またφ(1147)=30·36=1080なので、gcd(113, φ(1147))=1だから、
アルゴリズム17.1によって解を求めることができ、
x≡4521229≡763 (mod 1147)。
17.2
(a)
113, 347, 463は素数だから、アルゴリズム17.1によって解を求めることができ、
x≡347323≡37 (mod 463)。
(b)
588=22·3·72より、φ(588)=168=23·3·7。gcd(139,588)=gcd(275, φ(588))=1なので、
アルゴリズム17.1によって解を求めることができ、
x≡13911≡559 (mod 588)。
17.3
(a)
xk≡b (mod m)の解として、アルゴリズム17.1でのuから得られるu =u0を用いた解
x0≡bu0(mod m)と異なる解x≡x1 (mod m)があったとする。
bu≡x1ku≡x11+φ(m) v (mod m)と書けるので、uはku-φ(m) v=1の解の一つu =u’で、
x0とx1は異なるから、l∈ℕを用いてu’= u0+φ(m)lである。ところが、
x1≡bu’= bu0+φ(m)l= bu0≡x0 (mod m)となるから、xk≡b (mod m)の解はmod mでただ一つである。
(b)
gcd(k,φ(m))=q, k= k‘q, φ(m) = f‘q, k‘u‘=1+ f‘v‘とし、xk≡b (mod m)の解x≡x0がもしあれば、
k‘, u‘, f‘,qを使って別の解が作れることを示すのだと思うが、うまくいかないなあ。
(c)
l∈ℕとする。
一般論として分かること
m=pが素数なので、b=0ならすべてのk≥2に対しx≡0 (mod p)のみが解。
m=pが素数なので、Fermatの小定理からk=(p-1) l=φ(p)l (l>1)のとき
xk≡b (mod p)の解はb=1ならすべてのx≡1,2,.. p-1 (mod p)。b>1なら解はない。
Fermatの小定理によって、k≥pに対してはmod φ(p)で考えれば十分なので、
2≤k≤ p-1としてよい。
m=2のときφ(2)=1なので、すべてのk≥2に対しgcd(k,φ(2))=1
xk≡0 (mod 2)の解はすべてのk≥2に対しx≡0。
xk≡1 (mod 2)の解はすべてのk≥2に対しx≡1。
m=3のときφ(3)=2。k=2l+1に対しgcd(k,φ(3))=1なので解はただ一つ。
また、k=2lに対しgcd(k,φ(3))=lなので解は一つではない。
xk≡0 (mod 3)の解はすべてのk≥2に対しx≡0。
xk≡1 (mod 3)の解は
k=2lに対しx≡1, 2。
k=2l+1に対しx≡1。
xk≡2 (mod 3)の解は
k=2lに対し解なし。
k=2l+1に対しx≡2。
m=5のときφ(5)=4。k=4l+1, 4l+3に対してはgcd(k,φ(5))=1なので解はただ一つ。
また、k=4l , 4l+2に対しgcd(k,φ(5))=4or2なので解は一つではない。
xk≡0 (mod 5)の解はすべてのk≥2に対しx≡0。
xk≡1 (mod 5)の解は
k=4lに対しx≡1,2,3,4。
k=4l+1に対しx≡1。
k=4l+2に対しx≡1,4。
k=4l+3に対しx≡1。
xk≡2(mod 5)の解は
k=4lに対し解なし。
k=4l+1に対しx≡2。
k=4l+2に対し解なし。
k=4l+3に対しx≡3。
xk≡3(mod 5)の解は
k=4lに対し解なし。
k=4l+1に対しx≡3。
k=4l+2に対し解なし。
k=4l+3に対しx≡2。
xk≡4(mod 5)の解は
k=4lに対し解なし。
k=4l+1に対しx≡4。
k=4l+2に対しx≡2,3。
k=4l+3に対しx≡4。
m=7のときφ(7)=6。k=6l+1, 6l+5に対してはgcd(k,φ(7))=1なので解はただ一つ。
また、k=6l , 6l+2, 6l+3, 6l+4に対しgcd(k,φ(7))>1なので解は一つではない。
xk≡0 (mod 7)の解はすべてのk≥2に対しx≡0。
xk≡1 (mod 7)の解は
k=6lに対しx≡1,2,3,4,5,6。
k=6l+1に対しx≡1。
k=6l+2に対しx≡1,6。
k=6l+3に対しx≡1,2,4。
k=6l+4に対しx≡1,6。
k=6l+5に対しx≡1。
xk≡2(mod 7)の解は
k=6lに対し解なし。
k=6l+1に対しx≡2。
k=6l+2に対しx≡3,4。
k=6l+3に対し解なし。
k=6l+4に対しx≡2,5。
k=6l+5に対しx≡4。
xk≡3(mod 7)の解は
k=6lに対し解なし。
k=6l+1に対しx≡3。
k=6l+2に対し解なし。
k=6l+3に対し解なし。
k=6l+4に対し解なし。
k=6l+5に対しx≡5。
xk≡4(mod 7)の解は
k=6lに対し解なし。
k=6l+1に対しx≡4。
k=6l+2に対しx≡2,5。
k=6l+3に対し解なし。
k=6l+4に対しx≡3,4。
k=6l+5に対しx≡2。
xk≡5(mod 7)の解は
k=6lに対し解なし。
k=6l+1に対しx≡5。
k=6l+2に対し解なし。
k=6l+3に対し解なし。
k=6l+4に対し解なし。
k=6l+5に対しx≡3。
xk≡6(mod 7)の解は
k=6lに対し解なし。
k=6l+1に対しx≡6。
k=6l+2に対し解なし。
k=6l+3に対しx≡3,5,6。
k=6l+4に対しx≡2解なし。
k=6l+5に対しx≡6。
bのk乗根はmを法として0かgcd(k, φ(m))個?
0 件のコメント :
コメントを投稿