●1次不定方程式の諸定理の証明

■ユークリッドの互除法による一次不定方程式の解法
この主題は、次のストーリーで証明されます。これ自体が出題されることもあります。

[完全剰余系の基本定理]
⇒［ax+by=1が整数解を持つ⇔aとbは互いに素］
⇒［ax+by=cが整数解を持つ⇔cはgcd(a,b)の倍数］

[完全剰余系の基本定理（整数論の基本定理）]
この定理にはいくつかの形式がありますが、内容は同一です。
（形式1）
a、n が互いに素であるとするとき、n−1個の相異なる整数
　　　1a、2a、3a、· · ·、(n −1)a
をnで割った余りは、1 からn-1までの全ての整数が1回ずつすべて (順不同で) 現れる。
（形式2）
a、n が互いに素であるとするとき、n個の相異なる整数
　　　0a、1a、2a、3a、· · ·、(n−1)a
をnで割った余りは、0 からn-1 までの全ての整数が1回ずつすべて (順不同で) 現れる。

「ax+by=1が整数解を持つ⇔aとbは互いに素」も非常に有用な基本定理です。これは、「完全剰余系の基本定理」を証明したうえで証明します。

●完全剰余系の基本定理の証明
（形式2）の「0a、1a、2a、3a、· · ·、(n−1)aの中で、iaとja（0≦i < j ≦n-1）をnで割った余りはすべて異なる」という「完全剰余系の基本定理」を背理法で証明します。
0a、1a、2a、3a、· · ·、(n−1)aの中で、iaとja（0≦i < j ≦n-1）をnで割った余りが同じだと仮定すると，(j-i)aはnの倍数となりますが、0≤j - i <n-1<nでありかつaとnは互いに素なのでこれは矛盾です。したがって、iaとja　(i>j)　をnで割った余りはすべて異なります。0a、1a、2a、3a、· · ·(n −1)aはn個の整数であり、これらをnで割った余りがすべて異なるならば、余りは0からn-1までn種類有り、余りはすべて異なります。

●「ax+by=1が整数解を持つ⇔aとbは互いに素」の証明
○「ax+by=1が整数解を持つ⇒aとbは互いに素」の対偶を示します。
aとbが2以上の公約数dを持つとすると、ax+byはdの倍数となり、ax+by=1は解を持ちません。したがって「ax+by=1が整数解を持つ⇒aとbは互いに素」が示されました。
○「aとbは互いに素⇒ax+by=1が整数解を持つ」を示します。
aとbが互いに素であるとき、完全剰余系の基本定理により、0a、1a、2a、3a、· · ·、(n−1)bをbで割った余りは全て異なるので、余りが１となるものが存在します。0a、1a、2a、3a、· · ·、(n−1)bの中で余りが１となるものをmaとおき，bで割った商をqとおくと、
ma=bq+1⇔am−bn=1となり、(m,−n)は整数解になっています。
上の定理を拡張して次の定理も証明できます。
●「ax+by=cが整数解を持つ⇔cはgcd(a,b)の倍数」の証明
○「ax+by=cが整数解を持つ⇒cはgcd(a,b)の倍数」を示します。
a、bはgcd(a,b)の倍数なので整数x、yに対してax+byもgcd(a,b)の倍数であり、cはgcd(a,b)の倍数です。
○「cはgcd(a,b)の倍数⇒ax+by=cが整数解を持つ」を示します。
a、bはgcd(a,b)と互いに素な整数p、qを用いて、a=p⋅gcd(a,b), b=q⋅gcd(a,b)と書けます。上で示した結果から、「pm+qn=1は整数解を持つ」ので、この式の両辺をgcd(a,b)倍すると、
　　p・gcd(a,b)・m+q・gcd(a,b)・n=gcd(a,b)⇒am+bn=gcd(a,b)
となり、am+bn=gcd(a,b)も整数解を持ちます。したがって、cがgcd(a,b)の倍数のとき、両辺を整数倍すれば右辺がcとなるのでax+by=cは整数解を持ちます。