黄昏通信社跡地処分推進室

黄昏通信社の跡地処分を推進しています

増田算額

増田に以下のような問題が出ていた


自然数m以下の数であって、mと互いに素な数をm(j) 1≦j≦rとし、その集合をSとする
このとき、Sの任意の数nに対し、あるm(j)があって、nm(j)はmで割ると1余ることを示せ。
問題を見てもぴんと来なかったが、いくつかの m について試してみたらなかなか面白かったので問題にも挑戦してみた。解けたと思うので、証明を記しておく。

証明

1≦k<m なる k について,F(k) = kn を考える.このとき
F(k) = gm+p (0≦g<n, 0<p<m) と書ける.
この時 F(1) 〜 F(m-1) はそれぞれ違う p を持つ.


(なんとなればもし同一の p を持つ F(a) と F(b) が存在した場合
 F(a) = gm+p
 F(b) = Gm+p
辺々引いて
 F(a)-F(b) = (g-G) m
 n(a-b) = (g-G)m
となってこれは n と m が互いに素という前提に反する*1.ゆえにそれぞれ違う p を持つ.)


すなわち
 kn = gm+1
となる k が必ず存在する.


このとき k と m が共通の因数 c を持っているとすると,この式を辺々 c で割って
 kn/c = (gm/c)+(1/c)
となって,これは左辺は整数だが右辺は明らかに整数ではない.ゆえに k と m は互いに素である.
そして 1≦k<m であるからこの k が題意を満たす m(j) である.


証明終わり.

付記

ということでいいのではないかと思うけど、微妙に自信がない。特に(なんとなれば……)の括弧内は怪しい気がする。
とはいえ解いていて楽しかった。自分にとってはちょうどいい問題だった。
あとはてダには tex 記法があるんだけど、tex 慣れてないのでこれでご勘弁ください。

追記

増田のトラバですぱっと解いてる人がいた。
http://anond.hatelabo.jp/20161024233946
本質的には同じことをやってると思うけど、ずっと手際がいい。かくありたいものである。
あ、そういうわけで、おれの証明もおおむね正しいっぽい。特に(なんとなれば……)の部分は合ってた。感覚的には自明なんだけど、それだけにちょっとだけむずかしい。

*1:n と m が互いに素なら LCM は nm になるが n(a-b) は明らかにそれより小さいので矛盾する.