受験数学わんこらスクール
京大理学部で数学をやったわんこらが中学生や高校生、受験生に数学の公式や問題を解説します。

a,bを互いに素な自然数とする。 0以上の整数m,nを用いてX=am+bnとあらわすことできる自然数Xをすべて求めよ。
ちょっと整数問題で殺されかけたから説明したいと思います。

もう整数問題をやってる間は、整数問題しか見えてない状態やからな。
だから整数問題をやることでしか、愛を確かめられへんねん。



今日扱いたい問題は

[問題]
a,bを互いに素な自然数とする。
0以上の整数m,nを用いてX=am+bnとあらわすことできる自然数Xをすべて求めよ。


これはちょっと抽象的やから、もっと具体的な問題から考えてみよ。
[問題]
0以上の整数m,nを用いてX=3m+5nとあらわすことできる自然数Xをすべて求めよ。


[解説]
これはX=3m+5nの3mの作用によってmが1増えると3増えるから

…→9→12→15→18→21→24→…(3で割り切れるグループ)

…→7→10→13→16→19→22→…(3で割ると1余るグループ)

…→8→11→14→17→20→23→…(3で割ると2余るグループ)

と言うように変化していくと考えるねん。

3つの動き方があるわけやな。



それで始まる値が3で割るとどんな余りになるかによって、どのグループの変化になるか決まるけど、

それは5nの作用によって決めることが出来て、5×0=0は3で割り切れて、5×1=5は3で割ると余り2,2×5=10は3で割ると余り1だから、

n=0の0から始めれば3で割り切れるグループの変化をして
n=1の5から始めれば3で割ると2余るグループの変化をして
n=2の10から始めれば3で割ると1余るグループの変化をするねん。

0→3→6→9→12→15→18→21→24→…(3で割り切れるグループ)

10→13→16→19→22→25→28→31→…(3で割ると1余るグループ)

5→8→11→14→17→20→23→26→…(3で割ると2余るグループ)

それでn≧3はX=3m+5n≧5×3=15でXは15以上になるけど、15以上の自然数は上で全部出てきてしまってるから考えなくてええわけやねんな。

だから答えは
0,3,5,6と8以上の自然数
やな。



もっと数学的な解答を作るなら、

[解答]
n=0の時X=3m
n=1の時X=3m+5=3(m+1)+2
n=2の時X=3m+10=3(m+3)+1

でXは0以上の3の倍数と、5以上の3で割ると2余る自然数と、10以上の3で割ると1余る自然数をとる。
つまり
0,3,5,6と8以上の自然数をとり

n≧3ではX=3m+5n≧5×3=15だからXのとる値は上の場合に含まれる。//


この問題では5nの5×0と5×1と5×2が3で割ると余りが上手いこと0,2,1ってすべて出てきますが、これは3と5が互いに素だから必ずこうなります。


こういう有名な定理があって覚えていて欲しいねんな。

「a,bが互いに素な整数でb≧2の時、a,2a,3a,…,(b-1)a,baをbで割った余りは、全て異なる」

[証明]
i,jを1≦i<j≦bとなる整数として、iaとjaがbで割った余りが等しいと仮定すると
ja-ia=(j-i)a
がbの倍数でaとbは互いに素よりj-iはbの倍数。
ところが0<j-i≦b-i<bより矛盾。
よってiaとjaはbで割った余りは等しくない。//


この証明も覚えたってくれ。
大学の代数でもちょこっと最初の方使うし。


このa,bが互いに素な整数でb≧2の時、a,2a,3a,…,(b-1)a,baをbで割った余りは、全て異なるって定理から余りはb個存在するけどbで割った余りは0,1,2,3,…,b-1のb個しかないから余りには0,1,2,…,b-1が全部出てくることがわかるねんな。

だからa=5,b=aの時、0×5と5×1と2×5は3で割ると全部違う余りになるから0,1,2が全て出てくることになるねん。


もう疲れてきたから寝たいけど、もうちょっと続けよか。

だから最初の一般的な問題

[問題]
a,bを互いに素な自然数とする。
0以上の整数m,nを用いてX=am+bnとあらわすことできる自然数Xをすべて求めよ。

[解答と解説]
kを0≦k≦a-1を満たす整数としてbkをaで割った余りをr_kとすると
n=kの時,X=am+bkでbk以上のaで割るとr_k余る自然数をとることがわかります。

だからbkの最大値のb(a-1)以上の整数ならXは全てとると言う性質もわかるわけやな。

aとbを反対にして考えてもいいから、またはa(b-1)以上の整数でもいけます。


色々わかってきたとこで、もしm,nが0以上と言う制限をなくしてただの整数としたら、
「aとbが互いに素の時、am_1+bn_1=1となる整数m_1,n_1は存在する」って言う定理から任意の整数pに対して
p=p(am_1+bn_1)
=a(pm_1)+b(pn_1)

なのでX=am+bnは任意の整数pに対してm=pm_1,n=pn_1とすればX=pをとれるからX=am+bnは全ての整数をとることがわかります。


もうしんどいけど。もうちょっと続けよか。

さっきサラっと使った定理
「a,bが互いの素な整数の時、am_1+bn_1=1となる整数m_1,n_1が存在する」
って言うのはどうやって証明するかと言うと

[証明]
さっきの「a,bが互いに素な整数でb≧2の時、a,2a,3a,…,(b-1)a,baをbで割った余りは、全て異なる」
の定理を使って、aとb両方負の場合は-aを-bで割った余りを考えればいいからaとbのうちbが正の場合を示せば十分で
b=1の時a×0+b×1=1
b≧2の時iaをbで割った余りが1になるような整数iが存在して、商をqとすると
ia=bq+1⇔ai+b(-q)=1
だからam_1+bn_1=1となる整数m_1,n_1が存在することになります。

参考→aとpは互いに素の時am+pn=1となる整数m,nが存在する証明
証明の仕方が大学の代数を参考にしてます。

高校数学の公式や問題の解説

整数問題の解法の解説と問題演習




テーマ:算数・数学の学習 - ジャンル:学校・教育

▲ページトップへ
この記事に対するトラックバック
トラックバックURL
→http://kazuschool.blog94.fc2.com/tb.php/362-e58c2b2e
この記事にトラックバックする(FC2ブログユーザー)
▲ページトップへ
プロフィール

Author:わんこら
京都大学理学部で数学と物理を勉強し、数学を専攻しました。
東京で数学と物理の講師やってます

わんこら日記で日記とか勉強の仕方とか書いています

わんこら式数学の勉強法

メール
迷惑メールにされる危険性があるので出来るだけ
kazuyuki_ht○guitar.ocn.ne.jp
(○を@にしてください)に送ってください
勉強とかでどんな悩み持ってるかなど色々と教えてくれると嬉しいです。
わんこら式のやり方についてのメールはわんこら式診断プログラムを参考にしてください

詳しいプロフィール

人気blogランキングへ



にほんブログ村 受験ブログへ



学生広場

相互リンクも募集してます。

何かあれば
kazuschool_ht★yahoo.co.jp
かメールフォームからメールください。
(★を@にしてください)

カテゴリー

メールフォーム

名前:
メール:
件名:
本文:

FC2カウンター

リンク

このブログをリンクに追加する

お勧めの参考書、ノート

数学でお勧めのノートは
KOKUYOの無地
理由




センター試験は過去問が大切


チャートが終わったらお勧め
大学への数学1対1シリーズ
数学1


数学A


数学2


数学B


数学3


数学C

月別アーカイブ

ブログ内検索

RSSフィード

最近のトラックバック

ブロとも申請フォーム

この人とブロともになる

  1. 無料アクセス解析