数学塾variée@吉祥寺

数学塾の中の人の日記

19の倍数判定

最近,2014 年にちなんだ問題を解く機会があって,倍数判定にすこしくわしくなりました。2014 = 2 x 19 x 53 のうち,今日は 19 について,明日は 53 について書きます。

ある数が 19 の倍数である条件は,首位の数字から順に 1倍,2倍,4倍,8倍,…したものの和が 19 で割り切れること。

この性質は割と有名みたいです。生徒も知っていましたが,証明はあまり知られていないはずです。
たとえば 3 桁の数 x = 100a + 10b + c について普通に合同式を使っても


となるだけで,目的の

は得られません。ではどうするのか?

  • 20 = 19 + 1 より 20 ≡ 1 (mod 19)
  • x の桁数から 1 引いた数を n として,「x が 19 の倍数」と「2^n x が 19 の倍数」は同値

を使います。x = 100a + 10b + c でやってみましょう。


これで証明完了。a + 2b + 4c が 19 の倍数なら, x = 100a + 10b + c も 19 の倍数です。
この証明は桁数によりませんし,29 や 39 などの倍数判定にも使えます。たとえば,29 なら 30 = 29 + 1 を利用します。

ある数が 29 の倍数である条件は,首位の数字から順に 1倍,3倍,9倍,27倍,…したものの和が 29 で割り切れること。

我ながら無駄知識w