| ■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である。
|