読者です 読者をやめる 読者になる 読者になる

ユークリッドの互除法について

数学

a,bの最大公約数を{\rm gcd}(a,b)と表す.

定理.(ユークリッドの互除法
a, b(a \geq b)を整数として,abで割った余りをrとする.
このとき,{\rm gcd}(a,b)={\rm gcd}(b,r)

教科書の証明はなんだか文章ばかりで難しかった覚えがある.
今ならできるだろうか…?

(証明)
abで割った商をqとするとa=bq+rと表せる.
右辺をみるとb,rの公約数はaの約数となっており,
a,bの公約数になっていることがわかる.
またr=a-bqと変形するとa,bの公約数はrの約数となっており,
b,rの公約数になっていることがわかる.
つまりa,bの公約数の集合とb,rの公約数の集合は等しいので,
最大公約数は等しい.(証明終)

あっさり解決できた.少しくらいは簡単な整数論が身についているようだ.
このユークリッドの互除法は使いかたが問題である.

例えば73, 17の最大公約数を求める場合は,「どんどんスライドさせて割っていく」のである.
73=17 \times 4 + 5(割り算の原理)
17=5 \times 3 + 2 (割る数と余りで割り算する.以下繰り返す.)
5=2 \times 2 + 1
2=2 \times 1(割り切れたら終了)
よって最大公約数は1である.

ひとまずユークリッドの互除法の使いかたはいいだろう.
ところで上の証明を見ると,結局は次の問題に帰着される.

問.
{\rm gcd}(a,b)={\rm gcd}(a-b,b)を示せ.

証明はa=(a-b)+bとすれば,上の証明となんら変わらない議論で示せる.
これがいわゆる,ユークリッドの互除法の原理と呼ばれるものである.

二次形式って何ですか?

日記

正直に告白すると、二次形式というものを勉強したことがない。
使ったことが全くない。

Wikipediaによれば、二次形式は多方面で中心的な地位を占めるもののようだ…。
全く知らない。

いままで中心を回避して勉強していたということなのだろうか。
まるで複素積分のようである。

カップル成立の確率

数学

安田亨先生の伝説の良問100を読んでいたら,次の問題があった。

問.
男性が2人,女性が2人いる。各々は自分の異性をでたらめに1人指名する。
互いに相手を指名すればカップルが成立するものとして,
ちょうど1組カップルが成立する確率を求めよ。

n人まで一般化する方法も書いてあり,包除原理で計算している。

広告を非表示にする

岩手大学2016農学部第5問を解く

数学 岩手大学

(1)は座標の決定なのでなるべく低い次数の方程式に帰着させるほうがよいと思う.
(2)はいくつかの方針が考えられる.
代入することでxの方程式にするか,yの方程式にするか,rの方程式にするか.
そのあとは定数を分離するか,判別式か.

5.
放物線y=x^2と円x^2+(y-3)^2=\frac{r^2}{4}について,次の問いに答えよ.
ただし,rは正の定数である.
(1)r=6のとき,放物線と円の共有点の座標をすべて求めよ.
(2)rがすべての正の実数値をとって変化するとき,放物線と円の共有点の個数はどのように変わるか,調べよ.

(解)
(1)
r=6を代入するとx^2+(y-3)^2=9である.
x^2=yを代入して整理するとy(y-5)=0からy=0,5を得る.
y=0のときx=0y=5のときx= \pm \sqrt{5}となる.
共有点の座標は(-\sqrt{5},5),(0,0),(\sqrt{5},5)である.

(2)
y=x^2x^2+(y-3)^2=\frac{r^2}{4}に代入して整理すると,x^4-5x^2+9=\frac{r^2}{4}…(☆)となる.
ここでk=f(x)=x^4-5x^2+9およびk=\frac{r^2}{4}とする.
f'(x)=4x^3-10f'(x)=0とするとx=0, \pm \frac{\sqrt{10}}{2}である.
関数fは偶関数なのでx=0のとき極大値9x=\pm \frac{\sqrt{10}}{2}のとき極小値\frac{11}{4}である.
xk座標上に上記2関数のグラフを描くことで,次のことが分かる.
0<\frac{r^2}{4}<\frac{11}{4}すなわち0 < r <\sqrt{11}のとき,方程式(☆)の解の個数は0個,
\frac{r^2}{4}=\frac{11}{4},\frac{r^2}{4}>9すなわちr=\sqrt{11},r>6のとき,方程式(☆)の解の個数は2個,
\frac{r^2}{4}=9すなわちr=6のとき,方程式(☆)の個数は3個,
\frac{11}{4} < \frac{r^2}{4} < 9すなわち\sqrt{11} < r < 6 のとき,方程式(☆)の解の個数は4個となる.
方程式(☆)の解の個数と放物線と円の共有点の個数は一致するので,解が得られた.(終)

岩手大学2016農学部第4問を解く

数学 岩手大学

(3)の面積比で少しだけ驚いた.
試験会場で余裕がなくなっているとがむしゃらに計算することになるだろう.
実際には曲線と接線で囲まれた部分の面積なので,
被積分関数因数分解できることを考えるとそうでもない.


4.
曲線y=-x^3+3x^2+x-3Cとし,曲線C上の点(3,0)における接線を\ellとする.
(1)接線\ellの方程式を求めよ.
(2)pを実数とし,点(p,q_1)は接線\ell上にあり,点(p,q_2)は曲線C上にあるとする.
 p<3の範囲をpが動くとき,q_1 - q_2の最大値を求めよ.
(3)接線\ellと曲線Cで囲まれた図形は,y軸によって2つの部分に分けられるが,
 それらの面積のうち小さいほうをS,大きいほうをTとするとき,\frac{T}{S}の値を求めよ.
(解)
(1)
y'=-3x^2+6x+1からx=3のときy'=-8である.
よって\ell y=-8(x-3)=-8x+24である.

(2)
f(p) = q_1 - q_2と定める.
f(p)=(-8p+24)-(-p^3+3p^2+p-3)=p^3-3p^2-9p+27となる.
微分して
f'(p)=3p^2-6p-9=3(p+1)(p-3)
であるからp<3の範囲では増減表をかくことでp=-1で最大値をとることが分かる.
つまりq_1 - q_2p=-1のとき最大値32をとる.

(3)
直線\ellと曲線Cの差はf(x)=x^3-3x^2-9x+27=(x+3)(x-3)^2である.
f因数分解からy軸よりも左側の積分区間-3 \leq x \leq 0であり,
y軸よりも右側の積分区間0 \leq x \leq 3である.
(左側)\displaystyle =\int_{-3}^0(x+3)(x-3)^2dx
\displaystyle =\int_{-3}^0(x-3+6)(x-3)^2dx
\displaystyle =\int_{-3}^0((x-3)^3+6(x-3)^2)dx
\displaystyle = [  \frac{1}{4}(x-3)^4 + 2(x-3)^3 ]_{-3}^0
\displaystyle =\frac{1}{4}((-3)^4-(-6)^4)+2((-3)^3-(-6)^3)
\displaystyle =\frac{297}{4}

(右側)\displaystyle =\int_0^3(x+3)(x-3)^2dx
\displaystyle =\int_0^3(x-3+6)(x-3)^2dx
\displaystyle =\int_0^3((x-3)^3+6(x-3)^2)dx
\displaystyle = [  \frac{1}{4}(x-3)^4 + 2(x-3)^3 ]_0^3
\displaystyle =\frac{1}{4}(0^4-(-3)^4)+2(0^3-(-3)^3)
\displaystyle =\frac{135}{4}

つまり\displaystyle S=\frac{135}{4},T=\frac{297}{4}であり,\displaystyle \frac{T}{S}=\frac{11}{5}

岩手大学2016農学部第3問を解く

数学 岩手大学

3.
89も29も素数なので,(1)はすぐ1であることが分かる.
(2)以降の右辺が-20である意味がつかめないのが悔しい.
おそらく何か由来があると思うのだが….

次の問いに答えよ.
(1)ユークリッドの互除法を用いて,89と29の最大公約数を求めよ.
(2)2元1次不定方程式89x+29y=1の整数解を1組求めよ.
(3)2元1次不定方程式89x+29y=-20の整数解として現れるxの値のうち,
 正のものを小さい順にx_1, x_2, x_3,\cdotsとする.このとき自然数mに対して,
 x_mmで表せ.
(4)(3)で定めたx_mに対し,89x_m+y=-20を満たすyの値をy_mとするとき,
 自然数nに対して,\displaystyle \sum_{m=1}^n (3x_m+y_m)^2nで表せ.

(解)
(1)
割り算することで89 = 29 \cdot 3 + 2,および29 = 2 \cdot 14 + 1となる.
よって最大公約数は1である.

(2)
(1)の1つ目の式を2=89 - 29 \cdot 3と変形し2つ目の式に代入することで,
89 \cdot (-14) + 29 \cdot 43 =1を得るからx=-14,y=43が整数解のうちの1組である.

(3)
89 \cdot (-14) + 29 \cdot 43 =1の両辺を-20倍することで,89 \cdot 280 + 29 \cdot (-860) = -20となる.
つまり89x+29y=-20の整数解は\ellを整数としてx=280-29 \ell, y=-860+89 \ellである.
ここでx>0が最小となるのは\ell=9のとき19をとる.
ゆえにx_mは初項19,公差29の等差数列で表現できるので
x_m = 19 + 29(m-1)=29m-10が得られる.

(4)
89 x_m +29 y_m =-20x_m =29m-10を代入すると,
29y_m=-2581m+870よりy_m = -89m + 30を得る.
これより3x_m + y_m =-2mとなる.以上より
\displaystyle \sum_{m=1}^n (3x_m+y_m)^2 = \sum_{m=1}^n 4m^2 = 4 \cdot \frac{1}{6}n(n+1)(2n+1) = \frac{2}{3}n(n+1)(2n+1).(終)

素元と既約元

数学

何度考えても混乱するのでまとめてみる.
こういうところで書いておけば少しは頭に入るだろう.

R可換環とする.
p \in R素元とはp|abならばp|aまたはp|bが成り立つことを言う.
m \in R既約元とはm=abならばaまたはbのいずれか一方が単元であることを言う.
単元とは可換な元のことを言う.

素元という言葉から,素数を連想すると思う.
中学校で素数を習う際には,上記の既約元の形で定義するが,素元の定義と必要十分条件なので問題ない.
このことを証明していこう.

可換環Rについて,a, b \in Rに対し
ab=0ならばa=0またはb=0が成り立つとき,R整域という.

整域はつまり零因子が存在しない,ということである.
通常の整数の集合や有理数の集合は整域である.
行列は零因子があるので,そのままでは整域にはならないことが分かる.

以下Rは整域とする.

まず整数の話に限らず「素元ならば既約元」を証明する.
(証明)
pを素元とし,p=abであるとする.
左辺がpの倍数ゆえ右辺もpの倍数である.
素元の定義からp|abならばp|aまたはp|bが成り立つ.
p|aであると仮定すると,a=pa'となるa' \in Rがとれる.
元の式に代入するとp=pa'bであるが移行してpでくくるとp(a'b-1)=0となる.
Rは整域でp \not= 0からa'b-1=0,つまりa'b=1である.
これはbが単元であることを意味する.
p|bの場合も全く同様の議論で証明できる.(証明終)

広告を非表示にする