計算問題 gcd(135, 35)

1.gcd(135, 35) //n>0
2.gcd(35, 135 mod 35) //n=30
3.gcd(30, 35 mod 30) //n=5
4.gcd(5, 30 mod 5)＝30 //n=0
→4.でn=0になるまでの計算の過程を,
今まで数学を勉強してきていない人向けに解説をできますでしょうか。。。

No.3 回答者： alice_44 回答日時： 2012/10/20 18:57

互除法の計算過程自体は、そう難しいものではないので、

整数の余り付き除算ができていれば、実行はできるでしょう。

135＝35×3＋30 だから、135,35 を共に割り切る数と
35,30 を共に割り切る数は、135,35,30 の公約数であり、
一致する。公約数が共通だから、最大公約数も共通。(1.→2.)
同じようにして、35＝30×1＋5 より、
135,35 の最大公約数は、30,5 の最大公約数とも共通。(2.→3.)
30÷5 は割り切れるから、30,5 の最大公約数は 5。(3.→4.)
よって、135,35 の最大公約数は 5。

このやり方をなぞって、２～３例、自分で計算してみれば、
たいていの子ができるようになるのでは？
それを「理解した」というかどうかは、微妙ではあるけれど。



小学校では、最大公約数を見つけるのに、
互除法ではなく、縦式の共除法でやりますね。

＿１３５＿＿３５＿｜＿５　　← 135 と 35 の公約数のひとつ 5 を勘で見つける
ーーーーーーーーーー
＿＿２７＿＿＿７＿　　← 135 と 35 を、その 5 で割る

これを、公約数がなくなるまで繰り返すのですが、
27 が九九に出てくる数であることを思い出せば、
7 とは素であることがすぐ判ります。

見つけた公約数の積を作って、最大公約数＝５ です。
こっちが、小学校流。

No.2 回答者： ereserve67 回答日時： 2012/10/20 16:31

整数aを自然数b>0で割った時の商をq，あまりをrとすると

a=bq+r(0≦r<b)

はよろしいでしょうか．このとき

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

が成り立ちます．（整数論の本にのっています）よって

∴gcd(135, 35),135=35・3+30
∴gcd(135, 35)=gcd(35,30),35=30・1+5
∴gcd(35, 30)=gcd(30,5),30=5・6
∴gcd(30,5)=5

通常はこう書くのではないですか．

No.1 回答者： f272 回答日時： 2012/10/20 16:24

数学を勉強していない小学生にでも，手順を教えることはできるだろう。