問題
どのような負でない2つの整数とをもちいてもとは表すことができない正の整数をすべて求めよ．
出典：大阪大学 2000年度 前期日程 第2次学力試験 理系 第3問
方針
まず小さい正の整数を直接調べ、表せない候補を拾う。その後は、3で割った余りごとに 、、 の3場合へ分ける。 なら、余り0は 、余り2は 、余り1は と表せる。これにより、調べるべき小さい数だけが残る。別解として、 が表せることを確認し、そこから3を足し続ける帰納的な説明もできる。
解答
まず小さい正の整数を調べる。 は負でない整数なので、表せる数は である。 は明らかに表せない。 は表せる。 は、 を使うと大きすぎ、 だけでは なので表せない。、 は表せる。 は なら3の倍数でなく、 なら残りが2で3の倍数でなく、 なら となるので表せない。
したがって、ここまでで表せない候補は である。
次に の正の整数はすべて表せることを示す。 を3で割った余りで分ける。 のときは と書けるので、 とすればよい。 のとき、 だから であり、しかも は3で割り切れる。したがって と書ける。 のとき、 かつ余り1である最小の数は10なので、実際には である。このとき で、 は3で割り切れる。したがって と書ける。
以上より、 以上の正の整数はすべて の形に表せる。したがって、求める正の整数は である。
別解。まず はいずれも表せる。ある数が と表せれば、それに3を足した数は と表せる。したがって から3ずつ足していけば、 以上のすべての整数を表せる。あとは から までを直接調べれば、表せないものは だけである。