累乗の余り                                 戻る

 当HPがいつもお世話になっているHN「GAI」さんからの出題です。
                                       (平成27年4月17日付け)

 1から1000までの自然数nに対し、nを120で割った余りが1であるものの個数は、nが
{1,121,241,361,・・・・,961} の計9個ある。では、同じくこの範囲で、

 n2を120で割った余りが1であるものの個数は?

 n3を120で割った余りが1であるものの個数は?

 n4を120で割った余りが1であるものの個数は?

をコンピュータなしで知る方法を教えて下さい。
































(答え)  らすかるさんが考察されました。(平成27年4月17日付け)

 n2を120で割った余りが1であるものの個数は?

 n2≡1 (mod 120)であるためには、

 n2≡1 (mod 3) かつ n2≡1 (mod 8) かつ n2≡1 (mod 5)

でなければならない。逆に、これが成り立てば、n2≡1 (mod 120) が成り立つ。

 n2≡1 (mod 8) から、 n≡±1、±3 (mod 8) つまり、奇数。

 n2≡1 (mod 5) から、n≡±1 (mod 5)

これを合わせて、n≡±1 (mod 10) すなわち、一の位が、1か9である数。

 また、n2≡1 (mod 3) から、n≡±1 (mod 3) つまり、3の倍数以外。

従って、n2≡1 (mod 120) となる数は、一の位が、1か9であり、3の倍数でない数なので、

列挙すると、

n≡1,11,19,29,31,41,49,59,61,71,79,89,91,101,109,119  (mod 120)

(列挙しなくても、120までで、12×2×(2/3)=16個 であることはわかる)

よって、960までで、16×8=128個、961〜1000までで5個なので、全部で133個。

 n3を120で割った余りが1であるものの個数は?

上と同様に、

n3≡1 (mod 3) かつ n3≡1 (mod 8) かつ n3≡1 (mod 5) でなければならないので、

n≡1 (mod 3) かつ n≡1 (mod 8) かつ、n≡1 (mod 5)  →  n≡1(mod120)

n≡1 (mod 120) である数の個数は問題文に書いてあるように、9個。

 n4を120で割った余りが1であるものの個数は?

同様に、n4≡1 (mod 3) かつ n4≡1 (mod 8) かつ n4≡1 (mod 5) でなければなら

ないので、

n≡±1 (mod 3) かつ n≡±1、±3 (mod 8) かつ (n≡0 (mod 5) でない)

 従って、n4≡1 (mod 120) となる数は、一の位が1、3、7、9で、3の倍数でない数なので、

120まででは、12×4×(2/3)=32個

そして、961〜1000を調べるために40以下を列挙すると、

  1、7、11、13、17、19、23、29、31、37 の10個

よって、960までで、32×8=256個、961〜1000までで10個なので、全部で266個。