DAY 28 合同式の利用・ユークリッドの互除法

今日は合同式を利用して整数問題をとく方法を学んだ。

問題

自然数nが3で割り切れないとき、2n^6+3nは3で割り切れないことを示せ。(チャート式 改)

回答

n \equiv 1,2の2通りが考えられるから、それぞれについて場合分けをする。

(i)n\equiv 1(mod 3)のとき

2n^6+3n\equiv 2+3 \equiv 5 \equiv 2(mod 3)

(ii)n\equiv 2(mod 3)のとき

2n^6+3n\equiv 256+6\equiv 262 \equiv 1(mod 3)

したがってどの場合でもn\equiv 0とならないから、2n^6+3nは3では割り切れない。

また、ユークリッドの互除法についても学んだ。

定理1-ユークリッドの互除法

自然数a,bについてa=bq+rとかけるときa,bの最大公約数をgcd(a,b)と表したとすると

gcd(a,b)=gcd(b,r)

証明

gcd(a,b)=g,gcd(b,r)=Gとおくと

自然数A,Bに対してa=gA,b=gBとかけるから

r=a-bq=gA-gBq=g(A-Bq)となってgrの約数である。

すなわちgb,rの公約数である。

b,rの「最大」公約数はGであるから

G \geqq g

また同様にa=bq+rよりGaの約数であって

Ga,bの公約数だから

G \leqq g

よってG=g

なお、a=bq+rでなくa=bq-rの形でも成立することは明らかである。

ただこの形の際に注意が必要なのが、a=bq-2という形になったときに成立するのは

gcd(a,b)=gcd(b,2)であることだ。誤ってgcd(a,b)=gcd(b,-2)としないようにしたい。

問題

a,bが互いに素であるとき\frac{3a+10b}{4a+13b}は既約分数であることを示せ。(チャート式 改)

解答

\frac{3a+10b}{4a+12b}が既約分数であることは3a+10b4a+13bが互いに素であることと同値である。

4a+13b=(3a+10b)\cdot 1 +a+3b

3a+10b=(a+3b)\cdot 3 +b

a+3b=b\cdot 3+a

これよりgcd(4a+13b,3a+10)=gcd(3a+10,a+3b)=gcd(a+3b,b)

=gcd(a,b)=1

よって4a+13b3a+10bは互いに素である。

したがって\frac{3a+10b}{4a+13b}は既約分数である。

ちょっといろいろとやって疲れた。 3時間もやれたのは成果だと思う。 もうすぐ春休みが終わるので、終わってもこの勉強時間を続けたい。

今日の勉強時間

  • 新課程チャート式基礎からの数学I+A:3時間12分

合計時間:3時間12分