入試数学のユークリッドの互除法 数学入試問題 | 京極一樹の数学塾

HOME > 大学入試問題のツボ2 > 入試数学のユークリッドの互除法 数学入試問題

入試数学のユークリッドの互除法

新学習指導要領において、整数問題が数Aに登場した際に、この主題も登場しました。

●ユークリッドの互除法
ユークリッドの互除法とは、「自然数a,b (a≥b)に対して、aをbで割った余りをrとおくとき

  • gcd(a,b)=gcd(b,r)

が成立し,これを繰り返し用いるとaとbの最大公約数が求まる」というものです。

これの何が便利かというと、2つの数の最大公約数を求める際に、素因数分解を利用して求めることもできますが、大きな数字の場合は、素因数分解よりもユークリッドの互除法を利用した割り算の方が圧倒的に計算量が容易です。またこの互除法から、一次不定方程式ax+by=dの解を求めることができます。
ユークリッドの互除法の証明

●ユークリッドの互除法による最大公約数の計算
[例1]

  • a=390
  • b=273

とすると、素因数分解ではa=390=3・10・13、b=273=3・7・13ですが、ユークリッドの互除法では

  • 390=273・1+117
  • 273=117・2+[39]
  • 117=[39]・3+0

したがって、390と273の最大公約数は39です。これくらいではまだ威力がわかりにくいのですが…。
[例2]

  • a=2013
  • b=1159

とすると、素因数分解ではa=2013=3・11・61、b=1159=19・61となり、19も61も見つけるにはかなり大変です。しかしユークリッドの互除法では、次の計算で容易に61が見つかり、その後に素因数分解することも容易になります。

  • 2013=1159・1+854
  • 1159=854・1+305
  • 854=305・2+244
  • 305=244・1+[61]
  • 244=[61]・4

[例題]
ユークリッド分数Q.gif

●ユークリッドの互除法による一次不定方程式ax+by=dの解法

この主題は、次のようなストーリーで証明されます。これ自体が出題されることもあります。
[完全剰余系の基本定理]
⇒[ax+by=1が整数解を持つ⇔aとbは互いに素]
⇒[ax+by=cが整数解を持つ⇔cはgcd(a,b)の倍数]

[完全剰余系の基本定理(整数論の基本定理)]
個の定理にはいくつかの形式がありますが、内容は同一です。
(形式1)
a、n が互いに素であるとするとき、n−1個の相異なる整数
   1a、2a、3a、· · ·、(n −1)a
をnで割った余りは、1 からn-1までの全ての整数が1回ずつすべて (順不同で) 現れる。
(形式2)
a、n が互いに素であるとするとき、n個の相異なる整数
   0a、1a、2a、3a、· · ·、(n−1)a
をnで割った余りは、0 からn-1 までの全ての整数が1回ずつすべて (順不同で) 現れる。

[x,yに関する二元一次不定方程式]
これにも2つの定理があります。
ax+by=1が整数解を持つ⇔aとbは互いに素
ax+by=cが整数解を持つ⇔cはgcd(a,b)の倍数(ベズーの等式)

1次不定方程式の諸定理の証明

[例題]
ユークリッド不定方程式例題Q.gif

[入試問題]

[B]既約分数の問題(2017年横浜市大/医)
2017年横浜市大/医11Q.gif
[B]ユークリッドの互除法の問題(2016年慶応大/医12)
2016慶応大/医12Q.gif
[B]ユークリッドの互除法の問題(2017年慶応大/医12)
2017慶応大/医12Q.gif
[C]整数総合問題(2015年センター試験IA5)
2015年センターIA問題5Q.gif
[C]複素数とユークリッド互除法の問題(2016年慶応大/理工3)
2016慶應・理工4Q.gif

京極一樹数学塾.gif

京極一樹の物理塾
京極一樹の化学塾
----------------------------
[入試問題解説]
●センター試験数学入試問題
センター試験数学
●医大・難関大の数学入試問題
東京大 数学入試問題過去問一覧
京都大 数学入試問題過去問一覧
大阪大 数学入試問題過去問一覧
一橋大 数学入試問題過去問一覧
東工大 数学入試問題過去問一覧
国公立医大 数学入試過去問一覧
私立医大 数学入試過去問一覧
難関私大 数学入試問題一覧
国公立大 数学入試問題一覧
----------------------------
[難関大・医大合格の教材2017年版]
最新刊:入試直前対策3点
----------------------------
東大理科
日大/医
横浜市大/医
東大・京大・一橋大の文系数学
----------------------------
完全対策 微積分応用問題
完全対策 微積分基礎問題
完全対策 複素数平面・2次曲線問題
完全対策 数列・漸化式の極意
完全対策 整数問題の極意
完全対策 空間図形問題の極意
注文のご案内・簡易製本のご案内
入試問題解説書の販売条件一覧

京極一樹が貴方のための
受験大学の入試問題の学びやすい分野別解説・傾向分析書
をおつくりします!
センター試験数学対策問題集
センター試験化学対策問題集
ほんとうの数学入試試験対策
-------------------------------------
[個人指導]
京極一樹が個人指導・家庭教師お引き受けします。
受験生・高校生・大学生はこちら
受験生の遠隔指導引き受けます!
中学生・中高一貫校生はこちら
-------------------------------------

●分野別の数学入試問題
大学入試 数学入試問題の良問集大成
(数Ⅰ・数Ⅱ・数Ⅲ)

(数Ⅲ)

(数A)

(数B・数Ⅲ)

行列と一次変換(旧数C)
難関大学突破のためのトピックス

---------------------------------
東大数学入試問題を突破する方法
初めて見る問題を解く方法
どうして勉強するのか
---------------------------------
「数学以外のコンテンツ」は削除しました。
入試数学トップへ戻る
京極一樹の数学塾トップページへ戻る