どこかで 非負整数\(a, b\) をつかって \(3a + 4b\)みたいな形で表せる数の最小値を 求めよ, みたいな問題を見たことがある気がして なんとなくやってみたのでメモ. 多分 もうちょっときれいに証明が書けると思う.

考え方から書いてみる. きちんと問題を書こう.

問題 自然数 \(N\)であって条件

任意の\(N\)以上の自然数 \(n\)に対して 自然数\(a\), \(b\)があって\(n = 3a + 4b\) が成り立つ.

を満たす自然数 \(N\)の最小値を求めよ. ☐

まず, 1から順に自然数が\(3a+4b\)の形で書けるかどうかを表にしてみよう.

1 ☓
2 ☓
3 = 3 ×1 ◯
4 = 4 × 1 ◯
5 ☓
6 = 3 × 2 ◯
7 = 3 × 1 + 4 × 1 ◯
8 = 4 × 2 ◯
9 = 3 × 3 ◯
10 = 3 ×2 + 4 × 1 ◯
11 = 3 ×1 + 4 × 2 ◯
12 = 3 × 4 ◯
13 = 3 × 3 + 4 × 1 ◯

この表を見てみると, 6以上の自然数について上のように表されるように見える. \(N = 6\)と取れると予想しよう.

自然数 \(n\)が \(3a + 4b\)で表される, というのは少し考えにくそうだ. 変数の数を減らすように言い換えるとこんな感じになる:

\(\{ n - 4b; b \ge 0, n-4b \ge 0 \}\) のある元は3の倍数である.

こう見てみると, \(n - 4b\)が3の倍数かどうかを見ればいいから, b=0, 1, 2として 3で割った余りで見てやると良さそうだ.

\(n - 4b \ge 0\) だから \(n \ge 8\)じゃないと\(b = 0, 1, 2\)に対して試すことができない. 上でn=8に対して\(3a + 4b\)の形に表せたので, \(n \ge 9\)としておこう. \(n=3s, 3s+1, 3s+2\) のときに調べてみよう.

\(n = 3s\) のとき)

  • \(3s - 4 \times 0 = 3s (OK)\).

\(n = 3s + 1\) のとき)

  • \(3s + 1 - 4 \times 0 = 3s +1\),
  • \(3s + 1 - 4 \times 1 = 3s - 3 = 3(s-1) (OK)\).

\(n = 3s+2\)のとき)

  • \(3s + 2 - 4 \times 0 = 3s + 2\),
  • \(3s + 2 - 4 \times 1 = 3s - 2\),
  • \(3s + 2 - 4 \times 2 = 3s - 6 = 3(s - 2) (OK)\).

これで, N=6以上の自然数は3a+4bの形で書けることが分かった!!