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

一次不定式、am+bn=dの整数解の求め方
今日は一次不定方程式の整数解を説明しますわ。


こういう問題な。


n,mを整数として
5n+3m=1
となる(n,m)を求めよ。


こういう問題はどうすればいいかと言うとまずは

「一つの解を見つける」

ことをするねん。

たくさん解はあるねんけど、どれでもいいから一つ解を見つけるねん。


適当にn=2,m=-3なら
5×2+3×(-3)=1
でちゃんと解になってるな。

こうやって一つの解を見つけると
5n+3m=1
5×2+3×(-3)=1
を辺々引いて

5(n-2)+3(m+3)=0

5(n-2)=-3(m+3)

で3(m+3)は5の倍数やけど、5と3は互いに素だかm+3が5の倍数のはずやから、kを整数として
m+3=5k⇔m=5k-3
と表せるねん。

このとき,m+3=5kを5(n-2)=-3(m+3)に代入すれば

n-2=-3k⇔n=2-3k

で、(m,n)=(5k-3,2-3k)って一般解が求まります。


このやり方は、漸化式で特性方程式が一つの解になってて差をとると一般解がわかるって言う流れと同じような感じやな。
こうやって、先にどんどん進めて勉強すれば同じような概念が出てきて関連性が見えてきて数学がわかってくるようになったりするねんけどな。


よし、そしたら練習問題いっとこか。

n,mを整数として
79n+63m=1
となる(n,m)を求めよ。


まずは一つの解を求めてと…

ってノートに計算しまくってると、おかんがえらいあの子部屋から出てないなって部屋を覗いたら

091006_m1.jpg

うへ~って追いかけあいっこしてることになって、すぐに病院につれていかれます。


これには解法があって以前ユークリッドの互除法に書いてるけど、今回はやってることは同じ方法やけど文字を置いていってやる方法を解説します。

まあなんとなく機械的に出来るから便利かもしれんな。
ただこっちの弱点は文字がめちゃめちゃ多くなっていくことやねんけど。

と言うことでやり方を説明すると

79n+63m=1

で79よ63で小さいの方の69で割ってm=…の形にします。

m=(1-79n)/63

それで整数を前に出して分子の各整数を63未満にします。

m=-n+(1-16n)/63

これでmとnは整数だから、(1-16n)/63も整数で1-16nは63の倍数になります。

だから
1-16n=63k(kは整数)
とけます。

今度は16が小さいから16で割って

n=(1-63k)/16
=-3k+(1-15k)/16

よって1-15kは16の倍数なので

1-15k=16p(pは整数)

とおけます。

今度は15が小さいから15で割って

k=(1-16p)/15
=-p+(1-p)/15

で1-pは15の倍数だから

1-p=15q(qは整数)

とおけます。
だから
p=1-15q
でこうやって、係数が1になったら終了で後は次々に元の式に代入していってqでm,nを表します。

p=1-15qをk=(1-16p)/15に代入して

k=-1+16q

今度はn=(1-63k)/16に代入して

n=4-63q

これをm=(1-79n)/63に代入して

m=79q-5

よって(m,n)=(79q-5,4-63q)って求まりました。


ただこれは係数が1になるまで繰り返さなくても途中で一つの解が見付かればよくて例えばさっきのでは
1-16n=63k
でk=-1,n=4が解だから
1-16×4=63×(-1)
辺々引いて

16(n-4)=-63(k+1)

よって16と63は互いに素だから
n-4=-63q(qは整数)
とけて
k+1=16q

だからm=(1-79n)/63よりm=79q-5って求められます。


そしたら適当に問題でも作って解いてください。

86n+27m=56

とか、

54n+91m=2

とか。

ちなみに、an+bm=dでaとbが互いに素ならば解が存在します。

aとbが互いに素やったら、an'+bm'=1と言う解が存在して両辺d倍すれば

a(dn')+b(dm')=d
でn=dn',m=dm'が一つの解になるからな。


aとbが互いに素やったら、an'+bm'=1と言う解が存在すると言うことについては

a,bを互いに素な自然数とする。 0以上の整数m,nを用いてX=am+bnとあらわすことできる自然数Xをすべて求めよ。の記事に書いてるから興味あったら見といてください。

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

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




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

▲ページトップへ
この記事に対するトラックバック
トラックバックURL
→http://kazuschool.blog94.fc2.com/tb.php/372-9175a24f
この記事にトラックバックする(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. 無料アクセス解析