シルヴァーマン 「はじめての数論」第3版 第17章練習問題2

17.4

(a)

p,qを素数とし、m=pq、gcd(m,b)=pとする。

もしq|bならb=pq≡0 (mod m)だから、gcd(b,q)=1である。

gcd(p,q)=1だからku=1+φ(m)=1+φ(p) φ(q)。

x≡b^u(mod m)とすると、mod qではq|mより

x^k≡ b^ku(mod q) = b^{1+φ(p) φ(q)}= b (b^φ(q) ) ^φ(p)≡b(mod q)           (1)

またmod pではp|mとgcd(m,b)=pより

x^k≡ b^ku≡0(mod p)                                                           (2)。

(1),(2)をx^kについての連立合同式とみるとgcd(p,q)=1だから、

中国の剰余定理により解はmod pqで唯一に定まる。

具体的に解くと、(2)より

x^k =pi (0<i<q)

(1)に代入して

pi≡b(mod q)

つまり0≤j<pとして

pi=b+qj

gcd(p,q)=1より、py=1+qzの解yが存在するから、このyを用いてi=byと書ける。

よってmod pqで(1)(2)の解は

x^k ≡pby=b(1+qz) ≡b (gcd(m,b)=pよりp|bだからbq≡0(mod pq))。

したがって、x≡b^u(mod m)はx^k ≡b(mod m)の唯一の解である。

(b)

(a)でp=q=3と考えると、φ(9)=6 ≠φ(3) φ(3)=4だから(a)の方法はうまくいかない。

17.5

(a) φ(1279)=1278なので、gcd(2, φ(1279))=2≠1となりアルゴリズム17.1が使えない。

(b)

p=2のときはアルゴリズム17.1でgcd(2, φ(p))= gcd(2,1)=1だが、

b≠0ならx≡1 (mod 2)しかないので自明となる。

pがp≥3の素数ならpは奇数だから、gcd(2, φ(p))= gcd(2, p-1)=2≠1なので、

アルゴリズム17.1は使えない。

(c)

ku=1+φ(m)vに解が存在しないからである。