数学のぶしぎ 3: ユークリッドの互除法: ユークリッドの互除法

摘要

先月号のテーマは、互いに素な2つの整数の組、つまり共通の約数が1だけであるような、相性の悪い2つの整数の組でした。例えば64と105です。しかし、この疎遠な2つの整数の組（a,b）が協力し合い、あらゆる整数を表せるのでした。つまり勝手な整数cに対して、方程式ax+by=cの整数解（x,y）が必ず存在します。さらにこの方程式は、c=1の場合の1組の整数解から全ての整数解が分かってしまうので、ax+by=1を満たす（x,y）を1組たけ求めることが本質的な問題です。