$a$, $b$, $c$ を整数, $m$ を正の整数とし, $$ ca\equiv cb\pmod{m} $$ が成り立つとする. また, $d = \gcd(c,\,m)$ とおく. このとき, $$ a\equiv b\pmod{\frac{m}{d}} $$ が成り立つことを証明せよ.
解答例 1
$ca\equiv cb\pmod{m}$ のとき, ある $t\in\mathbb{Z}$ が存在して, $$ c(a-b) = mt. $$ $c=dc'$, $m=dm'$ とおくと, $$ c'(a-b)=m't. $$ よって, $$ m'\mid c'(a-b). $$ $\gcd(c',\,m')=1$ であるから, $m'\mid (a-b)$ でなければならない. ゆえに, $$ a\equiv b\pmod{m'}. $$
最終更新日：2011年11月02日