 | ■No24739に返信(Sweetさんの記事)
> 任意の整数a,bについて、gcd(a,b)はa,bの最大公約数とする。
>
> (1) gcd(a,b)がgcd(a+b,a-b)を割り切ることを証明せよ。
a=ngcd(a,b)
b=mgcd(a,b)と置けます。
gcd(a+b,a-b)=gcd(ngcd(a,b)+mgcd(a,b),ngcd(a,b)-mgcd(a,b))
=gcd((n+m)gcd(a,b),(n-m)gcd(a,b))
=gcd(a,b)gcd(n+m,n-m)
よってgcd(a,b)はgcd(a+b,a-b)を割り切る。
> (2) gcd(a,b)=1 ならば gcd(a+ab,b)=1であることを証明せよ。
gcd(a+ab,b)=gcd(a(1+b),b)=gcd(a,b)*gcd(1+b,b/gcd(a,b))
=gcd(a,b)*gcd(1+b,b)=1*1=1
> (3) gcd(a,b)=1 ならば gcd(a+b,a-b)=1または2であることを証明せよ。
(1)より、gcd(a+b,a-b)は
gcd((a+b)+(a-b),(a+b)-(a-b))
=gcd((a+b)+(a-b),(a+b)-(a-b))=gcd(2a,2b)=2gcd(a,b)=2
を割り切る。
2の約数は1と2であるから、
gcd(a+b,a-b)=1または2である。
|
