自然数aに対し、a＋1は互いに素であることを証明せよ。を教えてください

自然数aに対し、a＋1は互いに素であることを証明せよ。を教えてください

No.2 回答者： rnakamra 回答日時： 2018/01/12 10:51

ユークリッドの互除法を使う。

aとa+1の最大公約数はaと(a+1)-aの最大公約数と等しい。
(a+1)-a=1であるからaと(a+1)-aの最大公約数は1である。
aとa+1の最大公約数は1、よってaとa+1は互いに素である。

No.1 回答者： はなはなはなは 回答日時： 2018/01/11 23:48

背理法で

互いに素でない＝公約数があると仮定して 公約数をnとしてa/nは割り切れるので自然数。a+1/n=a/n+1/n
a/nは自然数で1/nは分数で自然数にならない。よってa,a+1は互いに素
簡単に書くとこんな感じです