15342：n^2≡1 (mod 120)を満たす120以下の正の整数nはいくつある？...

問題15342・・・http://www.kyoto-be.ne.jp/koukyou/cms/?action=common_download_main&upload_id=13999 より 引用 Orz〜

解答

・わたしの...

明らかに、120-1=119 と 1は満たす...

120=2^3*3*5 なので...

2^2*3*5なら...

(2^2*3*5±1)^2=2^3*3*5*m+1 なので満たす...

つまり...59,61

けっきょく...

1,59,61,119 の4個ね ^^

↑

嘘でしたわ ^^; Orz...

↓

・鍵コメT様からのもの Orz〜

120=(2^3)*3*5であり，120で割って1余る条件は
「2^3で割って1余り，3で割って1余り，5で割って1余る」ことです．

n^2が2^3で割って1余るのは，nが奇数のとき，
n^2が3で割って1余るのは，nが3の倍数以外の数のとき，
n^2が5で割って1余るのは，nが5で割って1または4余るとき
であり，
「2,3,5で割った余りを指定すると，30で割った余りが1つ定まる」
(中国の剰余定理)
ことから，30で割った余りが1*2*2=4(通り)だけ得られます．
(具体的には，1,11,19,29)

連続30数の内に適するものが4つあるので，
120以下の正の整数では16個ありますね．

*なるほどぉ〜勉強になります ^^♪