当ＨＰがいつもお世話になっているＨＮ「ＧＡＩ」さんからの出題です。
（平成２７年４月１７日付け）
1から1000までの自然数ｎに対し、ｎを120で割った余りが1であるものの個数は、ｎが
{1,121,241,361,････,961} の計９個ある。では、同じくこの範囲で、
n2を120で割った余りが1であるものの個数は？
n3を120で割った余りが1であるものの個数は？
n4を120で割った余りが1であるものの個数は？
をコンピュータなしで知る方法を教えて下さい。
（答え） らすかるさんが考察されました。（平成２７年４月１７日付け）
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個。