互いに素

任意の整数nにおいて、28n+5と21n+4が互いに素であることを証明せよ。

大阪市立大の入試問題。

【証明】

2つの数の共通の約数をgとして、28n+5 = ga, 21n+4=gbと置く。a, bは整数。

二式からnを消去する。

3(28n + 5) = 3ga　→　3x28n + 15 = 3ga　・・・(1)

4(21n + 4) = 4ga　→　4x21n + 16 = 4gb ・・・(2)

両辺の差を取って(2) - (1)とすると

16 - 15 = 4gb - 3ga → 1 = g(4b - 3a)

ここで、g, b, aは整数なので、g = 1, 4b -3a = 1となり、28n+5と21n+4の公約数は1となることから、この2つの数値は互いに素である。