| ■45438 / inTopicNo.2) |
Re[1]: 合同式
|
□投稿者/ WIZ 付き人(58回)-(2013/07/14(Sun) 15:45:14)
 | a ≡ b (mod m)より、ある整数kが存在して、a = b+kmと表せます。
u = gcd(a, m), v = gcd(b, m)とすると、u, vは自然数です。
v|mかつv|bより、v|(b+km)、即ちv|aです。
よって、vはmとaの公約数でもあるので、v|uより、v ≦ u・・・(1)
です。
u|mかつu|aより、u|(a-km)、即ちu|bです。
よって、uはmとbの公約数でもあるので、u|vより、u ≦ v・・・(2)
です。
(1)(2)が同時に成立しなくてはいけないので、u = vである必要があります。
|
|