年東大理科の問題. 問題文が短くてよいし, さして難しくない. (ピタゴラス数とか知っていれば, 法 で考えることはすぐに思いつく.)
【問】
を 以上の整数とする.
と の最大公約数 を求めよ.
は整数の 乗にならないことを示せ.
【解】
だが, は法 で または にしかなれないので, で割れきれるということはない. したがって, が偶数のとき で, 奇数のとき, である.
は整数の 乗になると仮定する.
が偶数のとき:
, は互いに素なので, 互いに素な より大きな整数 , によって,
と書けるが,
となって, 整数 の存在は矛盾する.
が奇数のとき:
, の最大公約数は なので, 互いに素な 以上の整数 , によって,
と書けるが, 番目の式で
()
から, ( と は互いに素なので で割ることができて)
()
となるが, 法 における平方剰余は, , , がすべてであるので矛盾する.
以上, いずれの場合も矛盾するので, は整数の 乗にならない.
//