問題
は3より大きい素数とする．
(1) 以上の整数は，0以上の整数と0以上の整数を用いて
と表すことができることを示せ．
(2) 0以上の整数と0以上の整数を用いて
と表すことができないような0以上の整数の個数を求めよ．
方針
は3より大きい素数なので，3で割ると1または2余る。したがって の中から が3の倍数になるものを選べる。(1)では により，この選択で も保証される。(2)は(1)から，表せない数は に限られる。そこでこの範囲で と により表せる数を， に分けて数える。
解答
(1)
は3より大きい素数であるから，3で割り切れない。したがって， を3で割った余りは1または2である。よって を3で割った余りは， の3種類すべてになる。
したがって，任意の整数 に対して， のいずれかを選べば が3で割り切れる。いま であり， だから である。そこで とおけば， は0以上の整数であり， と表せる。よって(1)が示された。
(2)
(1)より， 以上の整数はすべて表せる。したがって，表せない可能性があるのは の範囲だけである。この範囲で表せる数を数える。 のとき，表せる数は3の倍数である。 のとき，表せる数は で， 未満のものに限られる。 のときは となるので， の範囲には現れない。
まず の場合を考える。 にある3の倍数は であり，個数は である。また は と同値なので， が可能であり，個数は である。両者は3で割った余りが異なるので重複しない。よって表せる数は 個である。
次に の場合を考える。 にある3の倍数は であり，個数は である。また は と同値なので， が可能であり，個数は である。したがって表せる数は 個である。
いずれの場合も， にある 個の整数のうち，表せるものは 個である。したがって表せないものの個数は である。