[ 掲示板に戻る ]
記事No.58296に関するスレッドです
★ オイラーのφ関数 / KJ
質問失礼します。
画像にある通りなのですが、
60に互いに素な 16個の自然数を順にa[k]としたとき、(kは16以下の自然数)
a[k]の60で割った余りはa[5]a[k] の集合であるということを示したいです。

もちろんmodをつかって17^n=(-11)^(n/2)=1 (mod60)
とすれば(2)は一瞬で解けるのですが…
(すいません、三重イコールが出せないので、普通のイコールで代用しています)

どなたかご教授願います。
いつもありがとうございます。
No.58296 - 2019/05/15(Wed) 17:44:12
☆ Re: オイラーのφ関数 / KJ
補足質問 自然数N とkが互いに素ならば、
N•1 , N•2 ……,N•(k-1),N•k を N で割った余りはすべて異
なるでしょうか？
No.58297 - 2019/05/15(Wed) 17:51:34
☆ Re: オイラーのφ関数 / らすかる
> a[k]の60で割った余りはa[5]a[k] の集合であるということを示したいです。
a[5]もa[k](1≦k≦16)も60と互いに素なので
a[5]a[k]も60と互いに素。よってa[5]a[k]を60で割った余りは
a[1]〜a[16]のどれかと一致する。
もしa[5]a[i]を60で割った余りとa[5]a[j]を60で割った余りが
等しかったとすると、a[5]a[i]-a[5]a[j]=60m(mは整数)すなわち
a[5](a[i]-a[j])=60m
a[5]は60と互いに素なので、a[i]-a[j]は60の倍数。
|a[i]-a[j]|＜60なのでa[i]-a[j]=0。
よってa[5]a[i]を60で割った余りとa[5]a[j]を60で割った余りが等しければ
a[i]=a[j]すなわちi=jだから、i≠jならばa[5]a[i]を60で割った余りと
a[5]a[j]を60で割った余りは異なり、a[5]a[1]〜a[5]a[16]を
60で割った余りはすべて異なることになる。
従ってa[5]a[1]〜a[5]a[16]を60で割った余りの集合は
a[1]〜a[16]の集合と一致する。

> 三重イコールが出せないので
「ごうどう」を変換すれば出せるのではないでしょうか。

> 補足質問
N・1,N・2,…,N・kをNで割った余りはすべて0ですから、
余りが異なることはありません。
No.58298 - 2019/05/15(Wed) 18:04:25