読者です 読者をやめる 読者になる 読者になる

数学塾variée@吉祥寺

数学塾の中の人の日記

53の倍数判定

昨日の 19 の倍数判定 に引き続き,今日は 53 の倍数判定について書きます。

まずはネットで調べたこと。

1の位を Y,残りの部分を X として 10X + Y から X+16Y を計算していく。これが 53 の倍数ならば,もとの 10X + Y も 53 の倍数。

例)493 → 49 + 3 x 16 = 97 は 53 の倍数ではないので,493 も 53 の倍数ではない。
http://teachers.usd497.org/bvancil/math/factor-tree/factor-rules.html

1の位を Y,残りの部分を X として 10X + Y から X - 37Y を計算していく。これが 53 の倍数ならば,もとの 10X + Y も 53 の倍数。
http://arxiv.org/pdf/math/0001012.pdf

X + 16Y,X - 37Y という謎の数式が出てきます。こんな方法ははじめて知りました。

arxiv の人が巨大なリストを作っている以上,何かシステマティックな作り方があるはずなので,それを考えました。

たとえば


ですから,10X + Y と X + 13Y は 53 を法として合同ではありません。X - 37Y についても同様で,単純な引き算ではもとの数と合同な式は作れません。

arxiv の人が2と5を例外扱いしていることがヒントになりました。


を作り,これが 53 の倍数になるような整数 k を探します。10 と 53 は互いに素ですから,こういう k がみつかれば

が言えます。

実際にやってみましょう。1 - 10k ≡ 0 とすると


これは不定方程式に直せます。


一番簡単な解は 10 x 16 - 1 = 53 x 3 でしょう。X + 16Y はこうやって作ったのだと思います。同じやり方で他の素数の倍数判定法も作れますね。

「倍数判定法を探す」=「合同式の逆元を求める」=「1次不定方程式を解く」と言い換えられるのが面白いと思います。
あと,海外の数ヲタのマニアっぷりに感服しましたw