雅楽多文書館

2012年12月の記事一覧

合同式の発展

高校生の皆さんは,数学Aでユークリッドの互除法を学習し,最大公約数を求めたり不定方程式を解いたりしたと思います.そんな経験をもう少し発展させましょう.最後に簡単な問題がありますが解けなくとも気にしないでください.そのうち何とかなるさー,そのうち何とかするさーという軽い気持ちでいましょう.計算のミス等ありましたらご容赦のほどを!
(スマートフォンでごらんの方は数式がでるまで時間がかかります.PCでご覧ください.)

命題1 2つの整数 $a$と$m$ が$\ \gcd(a,m)=1\ $ となるための必要十分条件は,$ax+my=1$ となる整数 $x$ ,$y$ が存在することである.
この命題を合同式で表すと
命題2 $a$を整数,$m$を自然数とする.このとき $ax \equiv 1 \ \ (\!\!\!\mod m \ )$ が解をもつための必要十分条件は,$\gcd(a,m)=1$ が成り立つことである.
命題2の証明
定義から  $ax \equiv 1 \ \ (\!\!\!\mod m\ )$ $\ \ \Longleftrightarrow$ $\ \ ax=1+my\ $をみたす整数$\ y$ が存在する.
が成り立っている.右側の式は,$ax-my=1$ と書き直せるので,条件を満たす式があれば直ちに分かる($\because$ $\ a$と $m$ の公約数があれば1を割り切るから)
逆を示すために$\gcd(a,m)=g$ とおき,次の式を満たす集合 $I=\{\ ax+my \ |\ x,y\in Z \ \}$( ただし$Z$ は整数の集合)を考える.$I$ 属する整数の中で正で大きさが最小のものを$d$ とする.このとき$d$ は$I$ の元であるので$d=ax_0+my_0$ をみたす整数$\ x_0,\ y_0$ がある.このとき$g|a$, かつ $g|m$であるから $g|d$ である.次に $a$ を $d$ で割って $a=dq+r$ (ただし$q$ , $r$ は整数で$0 \leqq r < d $ をみたす)となったとする.$r=a-dq=a(1-qx_0)+m(-qy_0)$ と変形できるので,$r$ も$I$ の元である.$r$ は $0 \leqq r < d$ をみたすので,$r=0$ でなければならない.これは,$d|a$ であることを示している.同様に$d|m$ 成り立つ.$d$ は $a$ と$m$の公約数であるので$d|g$である.$g|d$ かつ $d|g$ なので$d=g$ でなければならない.すなわち,$\gcd(a,m)=1$ ならば $ax+my=1$ が成り立つ.      Q.E.D.


命題2を満たす$x$が存在するとき,$m$ を法とした$a$ の逆数とよび,$a^{-1}$ と書き表すことが多い.ちなみに$\ a=5,\  m=12$ のとき$\ a^{-1}=5$ である.
定義 集合 $\{ \ 0,1,2,\cdots,m-1\ \}$ に属する数で $m$ と互いに素なものの個数を$\phi(m)$で表す.
この$\phi(m)$はオイラーの $\phi$ 関数と呼ばれている.
例 $\phi(12)=4$ である.(12と互いに素の数は1,5,7,11の4つであるから)
したがって,$ax \equiv 1 \ \ (\!\!\!\mod 12 \ )$ が解をもつのは $a=1,5,7,11$ の場合だけである.


定理 (オイラー・フェルマーの定理)
\[ \gcd(a,m)=1 \ \ \Longrightarrow \ \ a^{\phi(m)} \equiv 1 \ \ (\!\!\!\mod m\ ) \] が成り立つ.

系 (フェルマーの小定理)
$p$ を素数とする\[ \gcd( a,p)=1\ \ \Longrightarrow \ \ a^{p-1} \equiv 1\ \ (\!\!\!\mod m \  ) \] が成り立つ .
例題 次の合同式を解く.
      $3x \equiv 2 \ \ (\!\!\!\mod 5 \ )$
解 表を作る.
01234
3x03142

$x$の行は5で割ったときの余り,$3x$ の行は,対応する$3x$を5で割った時の余り.
この表から,$3x$ の$2$ に対応している$x$ の値は$4$ だから,$x \equiv 4 \ \ (\!\!\!\mod 5 )$ が解であることが分かる.

問題 次の合同式を解きましょう.
(1) $5x \equiv 2 \ \ (\!\!\!\mod 9 \ )$
(2) $3x \equiv 2 \ \ (\!\!\!\mod 6 \ )$

スポンサーサイト

2012/12/27   整数論     144TB 0   144Com 0  

4 $ n $ + 3の形の素数は無限個ある.


タイトルの命題を合同式を用いて証明してみました.高校生は合同式を使わないで証明に挑戦してください.また,$4n+1\ $という形の素数も無限個あることが証明されてます.なお,スマートフォンの方はPCモードでごらんください.(数式が現れるまで少々時間がかかることがあります.少しだけお待ちください)

命題 $p \equiv 3 \ \ (\!\!\!\mod 4)\ $をみたす素数は無限個存在する.
命題の意味は4で割ると3あまる素数$\ p$は無限に存在する,という意味です.$\ p $は$\ 4n+3\ $という形をしています.

証明 背理法による
有限個しかなかったとする.
    $p_1,p_2, \cdots , p_n$ を4を法として3に合同な素数全体とする.$\cdots$ (1)
ここで,$m=4p_1p_2 \cdots p_n-1$とおくと
\[ m \equiv -1 \equiv 3 \ \ (\!\!\!\mod 4\ ) \cdots (2) \]$m$ が素数ならば証明はここで終わりとなるので($p_1,p_2, \cdots,p_n\ $意外に素数が存在することになるから),$m$ は合成数とする.
$m$ は$\ p \equiv 3 \ \ (\!\!\!\mod 4)$ をみたす素因数を少なくとも1つもつ.
($\because \ $ $m=q_1q_2 \cdots q_k$において$1\leqq i \leqq k$ ですべて $q_{\ i} \equiv 1 \ \ (\!\!\!\mod 4)\ $ならば(2)に反するから)
よって,$m=q_1q_2 \cdots p \cdots q_k$ より $p|m$ また,明らかに $p|p_1p_2 \dots p_n$ より
\[ 1=4p_1p_2 \cdots p_n-m \]なので右辺は$p$ で割り切れる.したがって左辺も$p$ で割り切れなければならない.すなわち$p|1$ となりこれは矛盾である.したがって,$p \equiv 3 \ \ (\!\!\!\mod 4)\ $をみたす素数は無限個存在する.Q.E.D.

2012/12/20   整数論     143TB 0   143Com 0  

合同式の応用


注意  記号$a|b$ は $a$ は$b$ を割り切るという意味である.
次の命題を証明する.
命題「円 $X^2+Y^2=3$ 上には有理数点はない」($X$座標,$Y$座標共に有理数になることはない)

命題を証明する前に次の補題を証明する.
補題 $3|x^2$ ならば $3|x$ である.
補題の証明 
3を法として$x$は$0,1,2$のどれかに合同である.$x \equiv 1,2$ なら$x^2 \equiv 1$ $(\!\!\mod 3)$となるので$x^2$は3で割きれない . したがって $x^2 \equiv 0$ となるためには$x \equiv 0$でなくてはならない.     Q.E.D.

命題の証明 背理法による
等式 $X^2+Y^2=3$・・・ (1) をみたす有理数点$(X,Y)$があると仮定する.
$X$と$Y$は有理数なので,整数 $x,y ,z$ によって
     $X=\displaystyle{\frac{x}{z}}$  $Y=\displaystyle{\frac{y}{z}}$ ・・・(2)
と表すことができる.このとき,さらに
  $x,y,z$ のなかには3で割り切れないものがある・・・(3)
と仮定する.(3つとも3で割り切れたら $X=\displaystyle{\frac{x}{3}}$ , $Y=\displaystyle{\frac{y}{3}}$ ,$Z=\displaystyle{\frac{z}{3}}$ ,で置き換えても(2)が成り立つ)$X$,$Y$ が(1)をみたすので,整数 $x,y,z$ は方程式
    $x^2+y^2=3z^2$・・・(4)
をみたす.ここで,もし$x$ が3で割れたら$x^2$,$3z^2$ が3で割り切れるので$y^2$も3で割り切れる.このことから,補題によって$y$も3で割れることになる.(4)の左辺は$3^2$で割り切れる.つまり,$3^2|3z^2$ となり$3|z$となってしまい $x,y,z$ がすべて3で割り切れることになり(3)に反する.したがって$x$は3で割り切れないと結論できる.同様に$y$も3で割り切れない.ここで方程式(4)を3を法として考える.$x$,$y$ はともに3で割り切れないので,$x ,y \equiv 1,2$ $(\!\! \mod 3)$
よって$x^2,y^2 \equiv 1$ $(\!\! \mod 3)$したがって$x^2+y^2 \equiv 2$ $(\!\! \mod 3)$・・・(5)
となる.しかし,$3z^2 \equiv 0$ $( \!\! \mod 3)$であるので(5)は等式(4)が成り立つことに矛盾する.したがって命題は成り立つ.                               Q.E.D.

高校生のみなさんは $x$ が3で割り切れないを $x=3t+1$ および $x=3t+2$ とおいて($y$も同様),$x^2+y^2$ がどうなるか考えること.背理法の学習のつもりで挑戦してみてください.
                                            

2012/12/16   高校数学     140TB 0   140Com 0  

今日のレッスン


   久しぶりにフルートを吹く
   自然気胸後 初めてのレッスン
   指慣らし むしろ肺慣らし
   ロングトーンで息が苦しい

   演奏家の場合
   一日休めば 自分に分かる
   二日休めば 先生に分かる
   三日休めば 皆なに分かる

   私の場合
   二ヶ月休んだが 誰にも分からない

   本日の練習曲 易しい曲で練習
   『枯葉』J.コスマ 『舟歌』チャイコフスキー
   『組曲2番ロンド』バッハ

2012/12/14   音楽     141TB 0   141Com 0  

合同式の計算

前回,不定方程式についてその解法を学んだ.今回は不定方程式のすぐ隣にある,合同式をとりあげてみた.なお,参考文献が英語なので,そのまま英文で書いた.誤りはご容赦のほどを.
次の例題を考える.
例題 $2^{13} \times 3^{17}+5^{19}\times 7^{24}$ は $11$で割り切れることをしめす.

詳しくはこちらから  雅楽多文書館

2012/12/12   整数論     139TB 0   139Com 0  

不定方程式の一般解

今年度から学習指導要領の数学Aに「整数の性質」が加えられ,1年生で約数と倍数,ユークリッドの互除法,整数の性質の活用を学ぶことになった.整数解を求める特殊な例は,以前から入試問題に出題されていたが,新しい指導要領で整数が取り上げられることになり,入試がどうなるか注目してみたい.まず最初に,もっとも基本的な次の二元一次不定方程式を解いてみる.

問題.$13x-7y=1$の一般解を求めよ.ただし,$x,\,y\, $は整数とする.

解答,解説はこちらから  雅楽多文書館

2012/12/10   高校数学     138TB 0   138Com 0  

人間ドック


人間ドックで健康チェックの健診を受けた.もうずいぶんと健診を受けているが,どうにも苦手な検査がある.腹部超音波検査である.

生温かいゲル状のものを塗られ,機械が体に触れるともうダメ.くすぐったくてしかたがない.検査担当者が,息を止めましょう,と言うのを聞くと,クックックと笑いが出てきて止まらなくなる.一生懸命に笑いを堪えるのだがダメ,吹き出してしまう.そのうち体が震えてきて,クックックがアッハッハとなる.検査担当者の声がだんだんと厳しくなり,息を止めてください,と強い口調になってくる.悪いことに,緊張すべきときに可笑しかったことを思い出すのだ.すると,笑いが笑いを呼び,ますますクックックとなる.胃のレントゲンや採血などは何ともないのだが,この検査は苦手である.

古来多くの哲学者は「人は笑う動物である」と人間を定義した.人が笑うときは,幾つかの笑いの種類があるという,楽しいとき,悲しすぎるとき,感情の表れやそれを慎むため,約束された振る舞いとして,コミュニケーションの道具としての笑いなどがあるという.そうすると,自分のこの笑いとは何だろう? 検査への不安からの逃避,毎年くりかえすことだから,約束された型なのか.どれも違うような気がする.高尚な哲学的笑いなどではなく,単純に動物的反応だろう.どうでもいいけど,こんな事を考えていれば来年の検査のときに笑わないですむかもしれない.来年試してみたい.

腹部超音波検査の結果は,おおかたは要経過観察.あの笑いのせいか,ときどき抽出不明瞭(?)ということもある.毎年同じことの繰り返しである.それで良しとしている.

2012/12/06   雑記     134TB 0   134Com 0  

質問に答えて その6 (累乗根)

累乗根の質問についての回答です.16の4乗根,$\sqrt[\leftroot{1}4]{16}=2$などの解説です.

詳しくはこちらから  雅楽多文書館


2012/12/04   高校数学     136TB 0   136Com 0  

質問に答えて その5 (解答202の1および三角関数プリント12)

解答202と三角関数プリント12番の問題
$0 < \theta < \pi$ で,$\sin \theta-\cos \theta=\displaystyle{\frac{2}{3}}$のとき,$ \sin \theta+\cos \theta$を求める問題,および半角の公式についての補足

詳しくはこちらから 雅楽多文書館

2012/12/03   高校数学     135TB 0   135Com 0  

検索フォーム

.

 

RSSリンクの表示

.

 

ブロとも申請フォーム

この人とブロともになる

.

 

QRコード

QR

.