・剰余類を作る                          空舟氏

 適当な思いつきですが、mod p に還元した問題 を考えてみました。すなわち、

 1から始めて 2を掛ける、または、3を掛けて1を足すという操作を繰り返し、pを法とするす
べての剰余類を作ることができるかという問いです。

 問題以上のことは、特に思いついて無いですが、提示してみました。


 DD++さんからのコメントです。(平成27年10月14日付け)

 p=3 のときは、0が明らかに作れないので不可能。

 p≧5 の場合は、a から出発し、「3倍して+1」を p-2 回、「2倍」を p-2 回、「3倍して+1」を
1 回、「2倍」を 1 回

という操作で、a+1 になるので、これをひたすら繰り返せばよく、可能。

 ただ、許可されるのは「2を掛ける」ではなく「2の逆数をかける」ではないんですかね?
その場合でも a から a+2^(-1)-1 になり、繰り返せば全部出てきますが。


 空舟さんからのコメントです。(平成27年10月14日付け)

 そんな方法がありましたか。提示して良かったです。どちらの操作も(p-1)回でループする
ので、(p-2)回で逆演算を得て、 a -> (a-1)/3 -> (a-1)/6 -> (a+1)/2 -> a+1 というわけで
すね


                         投稿一覧に戻る