第228問の解答


1.問題 [整数の性質

問題図
図のような、1〜36番号の書かれた36個で出来た首飾りがあります。
この首飾りから、まず1番を、その後はp番ごとにを取り外していき、その場所にがなかったらそこで終了とします。
また、途中で36を越えてしまった場合には、その数から36を引いた番号を取り出し、その後同じように続けます。

例えば、p=10の場合に取り出すは、
 1番→11番→21番→31番→5番→15番→25番→35番→9番→19番→29番 →3番→13番→23番→33番→7番→17番→27番→1番
のようになりますね。

このとき、全ての玉がなくなってしまうような全て求めてください。
ただし、36以下整数とします。

2.解答例1ταροさん、澪桜葵美翔さん、萬田銀次郎さん、ありっちさん、noetherさん、Gouさん、きょえぴさん、柚奇神太郎さん、香川仁志さん、高橋道広さん、すなさん、DrKさん、清川育男さん、他多数)

全ての玉がなくなるとは、p、2p、3p、・・・、36pのそれぞれを36で割った余りが全て異なることを意味します。
これは、36互いに素のときに限ることを、次のように示すことができます。

もし、36が公約数n>1を持つと仮定します。
p=qn36=mn1<q、m<36とかけるので、
mp=mqn=36q36の倍数となります。
(m+1)p−p=mpですから、(m+1)p36で割った余りが等しくなり、しかも、1<m+1≦36なので、p、2p、3p、・・・、36pの中に36で割った余りが等しいものがあることになります

(例)p=15の場合
参考図1

逆に、36は互いに素とします。
もし、p、2p、3p、・・・、36pの中に余りが等しいものnp、mpがあったとします。1<n<m<36
mp−np=(m−n)p=36kとなりますが、36の約数を持たないので、(m−n)36の倍数となります。これは、1<n<m<36に反します。
従って、p、2p、3p、・・・、36pは、36で割った余りが全て異なります。

(例)p=7の場合
参考図2

さて、36=22・32と素因数分解できるので、1、2、3、・・・、36の中で36互いに素なものは、2の倍数でも3の倍数でもないものとなります。

従って、求める解は、下表の1の列、5の列の12個となります。

 参考図3


答:1、5、7、11、13、17、19、23、25、29、31、35