問題
を0以上の整数とする。直線 上の点 で，， がともに0以上の整数であるものの個数を とする。
(1) を証明せよ。
(2) を証明せよ。ただし， は 以下の最大の整数を表すものとする。
出典：東京工業大学 2003年度 後期 後期・理系 後期第2問
方針
(1)は の解 を に移すと の解になることを使う。逆に の解のうち のものはすべてこの形であり，残りの の中にちょうど1つ解があることを剰余で示す。(2)は右辺を とおき， を確認し， を直接調べて(1)と合わせる。
解答
(1)
を満たす0以上の整数の組 に対し， は を満たす。これにより， の解のうち であるものは， の解と一対一に対応する。
残るのは の場合である。合同式 を3で割った余りで見ると， は と同じ余りをもつ必要がある。 の中にこの条件を満たすものはちょうど1つあり，そのとき は0以上の整数である。したがって である。
(2)
とおく。整数 に対して
である。
一方， について， の0以上の整数解の個数は順に である。これは同じ順に の値と一致する。(1)と より，すべての0以上の整数 について である。