[5]の説明
[5] \(10x\equiv1\equiv24\equiv47\equiv70\)
では、1に23を３回足して70になり、10で割り切れる数が現れました。実は、足し算を最大で9回行えば10で割り切れる数が現れます。このことは次の定理から導かれます。
（定理）
\(b\)を整数、\(a\)を正の整数とし、\(p\)を\(a\)と互いに素な整数とする。このとき、\(0\)以上\(a-1\)以下の整数\(k\)のうち次の合同式をみたすものがただ一つ存在する。
\(b + kp \equiv 0 (mod a)\)
この定理を証明する準備として、次の補題を証明することにします。
（補題）
\(a\)を正の整数とし、\(p\)を\(a\)と互いに素な整数とする。このとき、\(0\)以上\(a-1\)以下の整数\(i,j\)について次が成り立つ。
\(i \neq j \Longrightarrow ip \not\equiv jp (mod a)\)
（補題の証明）
\(0 < |i – j| \leq a-1\)より、\(i – j \not\equiv 0 (mod a)\)である。\(a\)と\(p\)は互いに素であるので、\((i – j)p \not\equiv 0 (mod a)\)である。従って、\(ip \not\equiv jp (mod a)\)である。（証明終）
この補題を用いて、定理を証明します。
（定理の証明）
補題より、\(a\)個の整数
\(0, p, 2p, 3p, \cdots , (a-1)p\)
を\(a\)で割った余りは互いに異なるので、\(-b \equiv kp\)をみたす0以上\(a-1\)以下の\(k\)はただ一つ存在する。従って、題意は示された。（証明終）
コメント