中国の剰余定理についての詳しい記述はこちら↓
http://ja.wikipedia.org/wiki/%E4%B8%AD%E5%9B%BD%E3%81%AE%E5%89%B0%E4%BD%99%E5%AE%9A%E7%90%86
一般に
a≡b mod m
はaとbをmで割った余りが等しいことを表します
こういった式を合同式といいます
（定理）中国の剰余定理
m_1,m . . . 本文を読む
ユークリッド互除法については下記参照 http://blog.goo.ne.jp/kaizo01/e/4c9311a2939c9bfdf686c666757620a8
（定理）拡張ユークリッド互除法
ユークリッド互除法をa,b≧0に適用したときの剰余数列を
r_0=a,r_1=b,r_2,r_3,・・・・・・,r_(n+1)
商数列を q_1,q_2,q_3,・・・・・・q_n . . . 本文を読む
(定理)ユークリッド互除法 整数a,bについて、ある整数q,rが存在して a=bq+r を満たすならば gcd(a,b)=gcd(b,r) ここでgcd(a,b)はaとbの最大公約数です qはaをbで割った商、rは余りです (証明） gcd(a,b)=d_1 とすると a=a´・d_1 b=b´・d_1 と書ける r=a . . . 本文を読む