方程式ax + by = cが整数解を持つための条件とその証明

整数解を持つ線形方程式についての問題です。問題は、「方程式 ax + by = c（a, b, c は整数）が整数解を持つための必要十分条件は、cがaとbの最大公約数で割り切れることを示せ」という内容です。この問題を理解し、証明していきます。

1. 方程式の整理

まず、与えられた方程式 ax + by = c について考えます。ここで、x と y は整数であり、a, b, c も整数です。この方程式が整数解を持つための条件を求めることが目的です。

整数解が存在するためには、a と b の最大公約数（gcd）によって、c が割り切れる必要があります。すなわち、c が gcd(a, b) で割り切れることが必要十分条件となります。

まず、a と b の最大公約数を g とすると、g = gcd(a, b) と定義されます。このとき、a と b は次のように表すことができます。

a = g * a’、b = g * b’ としたとき、gcd(a’, b’) = 1 となります。これにより、方程式は次のように変形できます。

g * (a’x + b’y) = c となり、ここで a’x + b’y が整数解を持つ場合、c は g で割り切れることがわかります。逆に、c が g で割り切れない場合、この方程式に整数解は存在しません。

したがって、方程式 ax + by = c が整数解を持つためには、c が a と b の最大公約数 g で割り切れる必要があります。これが整数解の存在するための必要十分条件です。