あくまで備忘録なんで雑に記録します合同式の基本
15 ≡ 3 (mod 12) -> ３時と15時は、12時間を法として合同
一次不定方程式ax+by=cの整数解
2x + 4y = 1は存在しない（2, 4 が互いに素じゃない）
3x + 5y = 2は存在する（3, 5 が互いに素）
cが、a,bのGCMの倍数なら存在する！
つまりa,b互いに素なら、「ax+by=1」が存在する
を別の証明で
剰余の基本定理
n, a が互いに素
1a, 2a, 3a, …, na を nで割ったあまりが全て異なる
（例 a, n = 3, 5 で、1a~na：3, 6, 9, 12, 15 余：3, 1, 4, 2, 0）
証明（雑ですけど）：
もし pa ≡ qa (mod n) とすると(つまりnで割った余りが一致するp, qが[1~n]にあるとすると)
(q – p) % n = 0 (つまり差分を取るとnで割り切れる)
その様な異なるp, q(ともに1~nに)、の組み合わせはない
一次不定方程式の証明
a,bが互いに素の時、剰余の基本定理より
1a, 2a, 3a, …, ba をbで割ったあまりが全て異なるから(0 ~ b-1全種類あるから)
ap + qb = 1
右辺は b で割ると余り１
左辺のqbは割り切れるので、ap % b = 1 となる p をあてがえばよい
コメント