アットランダム≒ブリコラージュ

最小公倍数

3. 最小公倍数

二つ以上の整数 a, b, c,・・・ に共通な倍数をそれらの整数の公倍数という． 0は常に公倍数である． それを除けば公倍数の絶対値は a, b, c,・・・ のいずれの絶対値よりも小さくはないので， 公倍数の中に正で最小のものがある．それを最小公倍数(least common multiple 略して L.C.M.)という．
二つ以上の整数 あ、b、c、・・・ に共通な約数をそれらの整数の公約数という． 1は常に公約数である．公約数の絶対値は a, b, c,・・・ のいずれの絶対値よりも大きくはないので， 公約数の中に最大のものがある．それを最大公約数(greatest common measure 略して G.C.M.)という．

定理
二つ以上の整数の公倍数は，最小公倍数の倍数である．
二つ以上の整数の公約数は，最大公約数の約数である．
a, b の最小公倍数を l ，最大公約数を d とすれば ab=dl
a, b が互いに素で，他の整数 c と b との積 bc が aで 割りきれるなら，実は c が a で割りきれる．
証明

a, b, c,・・・の最小公倍数を l とし, m を任意の公倍数とする． m を l で割った商を q ，余りを r とすると
m=ql+r, 0 ? r < l
となる． l も m も a の倍数であるから l=al', m=am' とおくと
r=m-gl=a(m'-ql')
より, r は a の倍数である．同様に b, c, ・・・の倍数でもあり， r は a, b, c,・・・ の公倍数となる．ところが l は正で最小の公倍数 であったから，もし r が0でないとすると, lより小さい正の公倍数がある ことになり, l の最小性に反する．
∴ r=0
つまり m は l の倍数である．
a, b, c,・・・ の最大公約数を d とし, m を任意の公約数とする． l を d とm の最小公倍数とする． a は m の倍数であり， d の倍数である．つまり m と d の公倍数であるから(1)より a は l の 倍数である．同様にb, c, ・・・ も l の倍数である． つまり l は a, b, c,・・・ の公約数である．d が最大の公約数なので，
l ? d
一方, l はd とm の最小公倍数なので d ? l
∴ l=d
d と m の最小公倍数 l が d に一致した．d は m の倍数， つまり任意の公約数 m は最大公約数 d の約数である．
l は a, b の最小公倍数であるから適当な整数 a' と b' を用いて，
l=ab'=ba'
とおける． ab は a, b の公倍数だから(1)から ab は l の倍数である．
ab=ml
とする．よって
ab=ml=ma'b, ab=ml=mab'
∴ a=ma', b=mb'

つまり m は a, b の公約数である．(2)より最大公約数dの約数なので，d=me とおける．
一方 d は a, b の最大公約数なので a=da", b=db" とおける．よって
a=da"=mea", b=db"=meb"

一方，a=ma', b=mb' であるから，ma'=mea", mb'=meb"が成り立つ．
∴ a'=ea", b'=eb"

その結果，
l=ab'=aeb", l=a'b=ea"b
∴ l/e=ab"=a"b

ところがこれは l/e が a, b の公倍数であることを示している． l が最小の公倍数なのでその最小性により e=1 ．
∴ m=d つまり　ab=dl

a, b の最大公約数が 1 なのでa, b の最小公倍数は ab である． 仮定から bc は a の倍数であり，したがってa と b の公倍数である． よって bc は ab の倍数であり，
bc/ab=c/a が整数

つまりc は a の倍数である．□
この定理の証明において，前節の「除法の原理」が基本定理として用いられてることが わかる．日頃当然のように論証で使っていることが，「除法の原理」を基礎に厳密に示される．

問題
a, b は互いに素な正の整数とするとき，次の問に答えよ．

1. 分数 (7a+2b)/(3a+b) は既約分数である．
2. ps-qr=1 なる正の整数 p, q, r, s に対して， 分数 (pa+bb)/(ra+sb) は既約分数である．
3. (11n-42)/(3n-13) が既約分数にならないような 自然数 n を，小さい方から順に三つ求めよ．

1.
解法１
(7a+2b, 3a+b)=(2(3a+b)+a, 3a+b)=(a, 3a+b)=(a,b)=1

解法2
7a+2b=M, 3a+b=N とおくと逆に解けて
a=M-2N, b=-3M+7N
したがって M とN の最大公約数を d とすれば a も b も d で割れる。
(a,b)=1 なので、d=1 つまり、与式は既約分数。

2.
pa+qb=M, ra+sb=N とおくと逆に解けて
a=sM-qN, b=-rM+pN
したがって M と N の最大公約数を d とすれば a も b も d で割れる。
(a,b)=1 なので、d=1 つまり、既約分数である。

3.
(11n-42, 3n-13)=(4(3n-13)-n, 3n-13)=(-n, 3n-13)=13
分子、分母が13 の倍数になるときのみ既約でない。ゆえに n=13,26,39

画像：原論（幾何学原本）ヴェネツィア, 1482年, 初版.
http://www.kanazawa-it.ac.jp/dawn/148201.html　より Orz〜

ユークリッドの互除法

1.除法
整数aを整数bで割る割り算では，a/b=q+r/b において 0?r/b<1となるので， 商qはa/bを超えない最大の整数である． 一般に実数xに対して，xを超えない最大の整数を[x]と書き表す． この記号を用いると， q=[a/b]と書き表すことができる．

整数の集合 Zでは除法の原理が土台になる． 代数的整数といわれる世界では，この除法の原理は成り立たない． そこでは新たな考え方が必要になる． 一般化された「代数的整数」に対してわれわれの整数を「有理整数」という． 有理整数でない代数的整数は後に「ガウス整数」でその端緒を紹介する． この『整数論入門』は基本的に有理整数の世界の探求である．

これからは，特に断らなければ記号 N, Z, Q, R, C はそれぞれ， 自然数，整数，有理数，実数，複素数の集合を表すものとする．

2. 最大公約数

整数a, b, c, ・・・ の最大公約数を，座標と混同する恐れのないときは(a, b,c,・・・) と書く．
整数a, b, c,・・・ の最大公約数が1であることを簡単に 「公約数をもたない」という．この場合， (a, b, c, ・・・)=1． 特に二つの整数a, b が公約数をもたないとき，つまり (a, b)=1のとき，a, b は互いに素であるという．

3. ユークリッドの互除法

ここで，最大公約数を求める一般的な方法であるユークリッドの互除法をまとめよう．

(ユークリッドの互除法)
a > b > 0 を整数とし, a を b で割った余りを r とする．このとき
(a, b) = (r, b)
が成り立つ．
数列 { r_n } を次のように定める．
r_1=a, r_2=b
n ?2 のとき
　r_n > 0 なら、r_(n+1)=r_(n-1) を r_n で割った余り
　r_n=0 なら、r_(n+1)=0

このときある番号 N で r_N ≠ 0で r_(N+1)=0となるものがあり，このとき
r_N=(a, b)

が成り立つ．

証明は、http://aozoragakuen.sakura.ne.jp/suuronN/node11.html　を参照。Orz〜

これが最大公約数を求める一般的な方法で ユークリッドの互除法 といわれる． このように「必ずできる一般的方法」をアルゴリズムという． ユークリッドの互除法はアルゴリズムの基本例である．

三つ以上の整数a, b, c, ・・・ の最大公約数もこれを応用して求めることができる．

a が a, b, c, ・・・ のなかの最小の数とする． a で他の数を割った余りを b', c', ・・・とする．すると上の定理と同様に
(a, b, c,・・・)=(a, b', c',・・・)


この操作を繰り返すと余りのなかに0が現れる．それを取り除いてさらに同様の操作を繰り返す． ついにはただひとつの数が残る．それが a, b, c, ・・・ の最大公約数である．

問題
(6188, 4709) を求めよ。

(6188, 4709)=(4709, 1479)
=(1479, 272)
=(272,119)
=(119,34)
=(34,17)
=17

問題
(629, 391, 255)=(119,136,255)=(119,17,17)=17

a < b < c のとき、
一番小さい数 c を引いた、a-m*c, b-n*c, c の中に、最大公約数はあるはずということにほかならない分けですよね。


画像：ユークリッド/エウクレイデス　Eucleidesエウクレイデス〔ユークリッド〕 (c. 330-235 B.C.)　
art-random.main.jp/ samescale/090.html　より Orz〜
「・・・一説によると、アテナイで、プラトンに数学を師事したともいわれ、のちプラトンの死後、彼が創始した哲学学校アカデメイアで数学の教師の１人だった時期があると見られている。確実なのは、彼が古代の卓越した数学者で、アレクサンドリアで数学を教えていたこと、またそこで数学の一派をなしたことである。ユークリッド幾何学の祖で、原論では、平面・立体幾何学、整数論、実数論などの当時の数学が公理的方法によって組み立てられているが、これはギリシャ数学の一つの成果として受け止められている。・・・「幾何学原論」は、ピタゴラス以来のあらゆる初期ギリシャの数学的知識を体系的に編集したものである。・・・扱われている内容は、ピタゴラスの定理をはじめとする平面幾何学、相似図形、立体幾何学などのほか、(a+b)a=aa+abのような恒等式や最大公約数、素数といった、今日私たちが代数的に扱っているものも含まれる。中世、近世を通じてユークリッド幾何学は唯一の真なる幾何学とされ、本書は幾何学の教科書として用いられた。19世紀になって、ロバチェフスキーやリーマン等が非ユークリッド幾何学の体系を作り上げたが、現在もなお中学や高校で教えられる図形問題はユークリッド幾何学である。その意味で、世界で最も長く用いられている教科書と言える」。・・・」

９０歳という長命な方だったんですねえ ^^
同じ頃のアルキメデスに関してはまたいずれ。。。v
軍人に殺されたのはアルキメデスでしたよね。。。^^;

文法問

以下のサイトに載ってた問題です。^^v
http://blogs.yahoo.co.jp/miyanishinana/51358593.html#51358593　より Orz〜

次の英文には文法上取り除かなければならない語が1語ある。解答用紙の所定欄に該当する語を記せ。
（次は２００５年度の東大の問題のひとつである。）

In one of the earliest attempts at solar heating, energy from the sun was absorbed
by and large metal sheets covered by double plates of glass.


わかります？
ちなみにわたしゃ分からなかった。。。
論理的に考えれば分かりそうなもんなんだけど。。。^^;

1327：計算

問題1327
http://blogs.yahoo.co.jp/were524labor/26705115.html　より Orz〜

√(１１×√[１０×√(９×√[８×６＋１｝＋１）＋１｝＋１）をなるべく簡単な数で答えよ。
ただし√は該当する（）全体に掛かっているものとする。

* 広中杯の問題らしい。^^



































解答

これは書かないでおきますね ^^
頭の体操にどうぞ ♪

1326：計算

問題1326
http://blogs.yahoo.co.jp/were524labor/26705115.html　より Orz〜

ここに１〜０と＋のかかれたカードがたくさんあり、
１＋２＋・・・・＋９８＋９９＋１００
というように並んでいる。上の数列から＋のカードを一枚取る施行を行う。
例えば２９と３０の間の＋を取り除くと、
１＋２＋・・・・＋２８＋２９３０＋３１＋・・・・となる。
＋のカードを１枚取り除き、その和を計算したとき、答えがちょうど１００００になったという。
どの＋のカードを取り除いたか、小さいほうの数字を答えよ。

* 広中杯の問題らしい。^^































解答

・わたしの

Σ(1〜100)=100*101/2=5050
10000=100a+a+1+5050-2a-1
4950=99a
a=50
実際に、5050-50-51+5051=10000