長方形ポリオミノの色分け問題～数学編（全三回）その２

利用した結果

私たちは結果20230928-1の証明を試みますが, その前に補題$${1}$$を証明しようと思います. その証明において, 合同式を計算する場面があるのですが, そこでは次のような結果を利用しています.

結果$${1}$$. 整数$${a}$$,$${b}$$,$${m}$$, ただし$${m≥2}$$について, 正整数$${k}$$により$${ka≡kb \pmod {km}}$$が成り立つなら, $${a≡b \pmod m}$$が成り立つ.

結果$${2}$$. 整数$${a}$$,$${b}$$,$${m}$$, ただし$${m≥2}$$について, $${m}$$と互いに素な整数$${k}$$により$${ka≡kb \pmod m}$$が成り立つなら, $${a≡b \pmod m}$$が成り立つ.

補題1の証明

補題$${1}$$は以下のような, $${0}$$から始まる等差数列を色分けするといった問題で, おなじみのものですが, これが実際本丸の証明にかなり役立ちました.

補題$${1}$$:
$${m}$$を$${2}$$以上の任意の整数, $${a}$$を任意の整数, ただし$${a≠0}$$とする. $${m}$$と$${a}$$の最大公約数を$${d}$$, ただし$${m>d}$$とする. 集合$${A}$$を$${A=\{0,a,2a,\dots,(\frac{m}{d}-1)a\}}$$と定義する. このとき, 任意の$${x,y∈A}$$について, $${x≠y}$$のときは$${x \not\equiv y \pmod m}$$.

証明:
始めに, $${m>d}$$なので, $${m\rq≥2}$$である整数$${m\rq}$$により, $${m=dm\rq}$$と表せる. このときは

$$
\frac{m}{d}=m\rq≥2
$$

が確認できる. そこで私たちは, $${x}$$と$${y}$$を$${A}$$の任意の要素とし, $${x≠y}$$を仮定する. このとき, $${x \not\equiv y \pmod m}$$であることを背理法によって示す. それでは, もし仮に$${x≡y \pmod m}$$だったとする. $${x}$$と$${y}$$は$${A}$$の元なので, 整数$${i}$$,$${j}$$, ただし$${0≤i<{m\rq}}$$,$${0≤j<{m\rq}}$$により, $${x=ia}$$,$${y=ja}$$とおくことができる. よって

$$
ia≡ja \pmod m
$$

が成立する. そこで整数$${a\rq}$$により, $${a=da\rq}$$とおく. このとき

$$
ida\rq≡jda\rq \pmod {dm\rq}
$$

であり, したがって

$$
ia\rq≡ja\rq \pmod {m\rq}
$$

が成立する. $${a\rq}$$と$${m\rq}$$は互いに素なので,

$$
i≡j \pmod {m\rq}
$$

だと結論できる. $${0≤i<{m\rq}}$$かつ$${0≤j<{m\rq}}$$であることから, よって$${i=j}$$が成立する. するとこのとき,

$$
x=ia=ja=y
$$

となり矛盾する. $${\blacksquare}$$