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

11.9
任意の2つ、例えばx≡a₁ (mod m₁)とx≡a₂ (mod m₂)を解き、その解と第3式を連立させればよい。
すなわちまず、
x=m₁x₁+a₁≡a₂ (mod m₂)から、m₁x₁≡a₂ -a₁(mod m₂)を解き、解x₁(0≤x₁<m₂)を得る。
これより、x≡m₁x₁+a₁ (mod m₁m₂)。この式とx≡a₃ (mod m₃)を連立して、
x=m₁m₂x₂+m₁x₁+a₁≡a₃ (mod m₃)から、m₁m₂x₂≡a₃ -(m₁x₁+a₁)(mod m₃)を解き、
解x₂(0≤x₂<m₃)を得る。以上により、
x=m₁m₂x₂+m₁x₁+a₁ (mod m₁m₂m₃)。


より多くの合同式でも以上を繰り返せば良い。
m₁,m₂,...,m_rの、どの2つも互いに素でなければならない。

11.10

(1) φ(n)が素数の時

φ(n)はn≥3では偶数だから、φ(n)が素数ならφ(n)=2=1·2しかない。

n=lmとして、φ(l)=1のときl=1or2。

φ(m)=2のときm=p^k(k≥1)としてφ(m)=p^k-p^k-1=p^k-1(p-1)=2だから、

p^k-1=2かつp-1=1、または、p^k-1=1かつp-1=2。

したがって、(p,k)=(2,2)または(3,1)なので、m=3 or 4。

φ(n)=φ(l)φ(m)となるにはgcd(l,m)=1でなければならないから、

可能な組み合わせは、n=3,4, or 6。

(2) φ(n)が素数の2乗の時

φ(n)が素数ならφ(n)=4=1·2·2=1·4しかない。

まずφ(n)=4=1·2·2と考えると、n=jlmとして、φ(j)=1に対しj=1or2。

φ(l)=φ(m)=2に対し(1)と同様にl,m=3, 4, or 6。

gcd(j,l,m)=1でなければならないから、可能な組み合わせはn=12。

次に、φ(n)=4=1·4と考えると、n=lmとして、φ(l)=1に対しl=1or2。

φ(m)=4に対しm=p^k(k≥1)としてφ(m)=p^k-p^k-1=p^k-1(p-1)=4だから、

p^k-1=1かつp-1=4、または、p^k-1=4かつp-1=1、または、p^k-1=2かつp-1=2。

最後の場合は解がない。したがって、(p,k)=(5,1)または(2,3)なので、m=5 or 8。

gcd(l,m)=1でなければならないから、可能な組み合わせはn=lm=5, 8, or 10。

以上をまとめて、n=5, 8, 10 or 12。