前回の定理の証明する。
命題A
a , b を整数、d を a , b の最大公約数とする。
A = {a * x + b * y | x , yは整数}
B = {d * x | x は整数}
とするとA = Bである。
[証明]
ユークリッドの互助法などからも証明できるがここでは違うやり方で証明を使うことにする。
A ⊂ B は明らか。
A ⊃ B を示す。
0を除くAの元の絶対値で最小となるものを m とする。
Aの任意の元kに対し、k = m * q + r ( | m | > | r |) となるように出来る。(要するに剰余)
このとき k - m * q もAの元となっているので r もAの元となる。
しかしmがAの元のなかで絶対が最小であるのでr = 0となる。
コレにより、Aの任意の元はmの倍数であることが分かる。
m = d であることを示そう。
mがdの倍数になっているのは明らか。
さらにa , b ∈Aであるから a , b は mの倍数であることが分かる。
ゆえに m = d である。//
系B
a と b は互いに素な整数とする。
このとき a * x + b * y = 1 となるような整数 x , y が存在する。
系C
aとbが互いに素な整数であるとき、
b * y = 1 (mod a)
となる整数 y が存在する。
[証明] 系Bにおいてmod a で考える。//
補題D
{b , 2 * b , 3 * b , ... , a * b} は mod a で考えると {0 , 1 , 2 , ... , n - 1}と等しい。
[証明]
s = t (mod a)であるならば s * b = t * b であることから
mod aにおいて 任意の数 k に対し、k * b は { 0 , b , 2 * b , ... , (b - 1) * b} の元である。
このことと系Cによりこの補題は示される。//
定理１
a , b を正の整数とし、n が a , a - 1 , a + 1 , b , b - 1 , b + 1 とそれぞれ互いに素とする。
このとき （ i , k + a * i mod n）、（i = 1,2, ... ,n） に （ １ , k ） と同じ記号をいれるとそれは半魔方陣となる。また、（ i , k + b * i mod n）に (1 , k ) と同じ記号をいれるとそれも半魔方陣となる。
[証明]
まず横の行については半魔方陣の条件を満たしているのは明らか。
次に縦の列を考える。
ABC.. の記号を1,2,3..と数値に置き換えて考えると、1行目の数がkである列は
k + b * i (mod n) (i = 0 , 1, 2, .. , n - 1)
のように数が並んでいる。
補題Dによりこれは {0 , 1 , 2 , ... , n - 1}と等しいことが分かる。
すなわち縦の列も半魔方陣の条件を満たす。
残る対角線上の列を考える。
まず左上から右下への対角線上の数は
k + i + b * i (mod n) (i = 0 , 1, 2, .. , n - 1)
となっている。
すなわち k + (b + 1) * i (mod n) であり b + 1 と n は互いに素なので
補題Dによりこれも{0 , 1 , 2 , ... , n - 1}と等しいことが分かる。
逆の対角線も 同様に、b -1 とnが互いに素であることと補題Dを用いれば
{0 , 1 , 2 , ... , n - 1}と等しいことが分かる。
よって示された。//
PR
