合同式

　数を見て２、３、５、７、１１、１３などで割れるかどうかはどうしたら分かるのでしょうか。余りに注目する合同式を使って考えましょう。

　２で割れるかどうかは、一桁目が２で割れるかどうか(０、２、４、６、８のどれか)で決まります。何故かというと、１０が２で割れるからです。(mod ２)が２で割った余りを考えるという意味で、≡は余りが同じだという記号だとすると、

１０≡０(mod ２)

と表せます。余りが同じものを同一視するという意味は、２を足し引きしたものを同一視するという意味で、時計で１５時のことを(１２を引いて)３時と言うような感じです。そういう意味では、０と１しか数字がない時計で考えているような感じです。

　両辺を２乗、３乗していけば、

１０≡１００≡１０００≡…≡０(mod ２)

が分かります。これが一桁目だけが問題になる理由です。例えば２３４なら、

２３４≡２×０＋３×０＋４≡４≡０(mod ２)

と割り切れます。１００と１０が０なので、一桁目が２で割れればその数は２で割れます。

　５で割れるかどうかも、一桁目が５で割れるかどうか(０か５のどちらか)で決まります。先ほどと同様に、

１０≡０(mod ５)

なので、両辺を２乗、３乗していけば、

１０≡１００≡１０００≡…≡０(mod ５)

となり、例えば２３４なら、

２３４≡２×０＋３×０＋４≡４(mod ５)

となり、余りは４です。

　３で割れるかどうかですが、

１０≡１(mod ３)

なので、両辺を２乗、３乗していけば、

１０≡１００≡１０００≡…≡１(mod ３)

となり、例えば２３４なら、

２３４≡２×１＋３×１＋４≡９≡０(mod ３)

と割り切れます。つまり、全ての位の数を足して３で割れれば元の数も３で割れる訳です。

　１１で割れるかどうかですが、

１０≡ー１(mod １１)

なので、両辺を２乗、３乗していけば、マイナス掛けるマイナスはプラスなので、

１０≡１０００≡１０００００≡…≡ー１(mod １１)

１００≡１００００≡１００００００≡…≡１(mod １１)

となり、例えば２３４なら、

２３４≡２×１＋３×(ー１)＋４≡３(mod １１)

となり、余りは３です。つまり、全ての位の数を交互に足し引きして、１１で割れれば元の数も１１で割れる訳です。ここで、余りの話でー１が出て混乱しているかもしれませんが、１１を足して、

－１≡１０(mod １１)

とすればプラスになります。つまり、ここでは－１を１１で割ると余りは１０になる、という考えのもとで計算しています。

　７と１３で割れるかどうかは、少し難しくなります。

１０≡３(mod ７)

１０≡ー３(mod １３)

として、両辺を３乗すると、

１０００≡２７≡ー１(mod ７)

１０００≡ー２７≡ー１(mod １３)

となります。ここで、

２８≡７×４≡０(mod ７)

２６≡１３×２≡０(mod １３)

を使いました。この３乗した式を更に２乗、３乗していくと、

１０００≡１０００００００００≡…≡ー１(mod ７)

１０００≡１０００００００００≡…≡ー１(mod １３)

１００００００≡１００００００００００００≡…≡１(mod ７)

１００００００≡１００００００００００００≡…≡１(mod １３)

となり、例えば１２０２１なら、

１２０２１≡１２×(－１)＋２１≡９≡２(mod ７)

１２０２１≡１２×(－１)＋２１≡９(mod １３)

となり、７で割った余りは２、１３で割った余りは９になります。つまり、三桁ずつ交互に足し引きして、７で割れれば元の数も７で割れ、１３で割れれば元の数も１３で割れます。例えば、９９９９９９や、２３４２３４などは、三桁ずつ交互に足し引きすると０になるので、７でも１３でも割れます。実は、一桁ずつ交互に足し引きしても０になるので、１１でも割れます。これは、

１００１＝７×１１×１３

であることを示唆しています。なぜなら、

９９９９９９＝９９９×１００１

２３４２３４＝２３４×１００１

だからです。実際、７と１１と１３を掛けると確かに１００１になります。

　今回は、≡を使った計算を見てきました。≡は「合同」と読み、これを使った式を合同式と言います。私は合同式を使えるようになって、１０進法がいかに優れているかを知り、１０進法に愛着が持てるようになりました。