xを自然数として x=qk+r (0≦r<k) とおく。 この時、φをオイラー関数として φ(x)≦

xを自然数として
x=qk+r (0≦r<k)
とおく。
この時、φをオイラー関数として
φ(x)≦qφ(k)+rとなることを示してください。

No.1 回答者： mtrajcp 回答日時： 2018/12/14 21:24

x=5

k=4
とすると
q=1
r=1

5=1*4+1

1～4の内
5と互いに素な数は1,2,3,4の4個だから
φ(x)=φ(5)=4
1～3の内
4と互いに素な数は1,3の2個だから
φ(k)=φ(4)=2

φ(5)=4>3=2+1=φ(4)+1
だから
φ(x)≦qφ(k)+rとなりません

1～7の内
7と互いに素な数は1,2,3,4,5,6の6個だから
φ(7)=6
1～5の内
6と互いに素な数は1,5の2個だから
φ(6)=2

φ(7)=6>3=2+1=φ(6)+1
だから
φ(x)≦qφ(k)+rとなりません