FC2ブログ

典型題演習59~ユークリッドの互除法

ユークリッドの互除法-問題
難易度B、時間30分。誘導にしたがっていきましょう。

しっかりと学習したい方は下のリンクの「今日の一問」の項目からテキストをダウンロードして、先に印刷してから動画を見てください。書き込むスペースを作ってあるので、動画中に出てくるまとめの部分や、自分が必要だと思ったことを書き込むと後で復習しやすいはずです。
PDFテキストダウンロードページ


(1)は背理法です。互いに素であることを示すのに、最大公約数をgとおいて矛盾を導くのは有名です。
ユークリッドの互除法-1

(2)はa_3がgの倍数であることと、a_2とa_3がgより大きい公約数を持たないこと、すなわちa_2/gとa_3/gが互いに素であることに分けて示します。後者は(1)が使えそうですね。
ユークリッドの互除法-2

(3)はアタリマエです。数列{a_n}は余りで定義されているので単調減少していきます。それゆえ例えばa_2=5ならば5つ進んだa_7は存在するなら0以下です。ただ一応小問になっているので背理法で示しました。
ユークリッドの互除法-3

(4)はl=m-1です。0はすべての整数の倍数なので、0とgの最大公約数はgとなることに注意です。
ユークリッドの互除法-4

ユークリッドの互除法-考察-1
ユークリッドの互除法-考察-2

さらに勉強を進めたい方は次の問題にチャレンジしてみましょう。この問題があまり出来なかった人は値変え問題を、よくできた人は発展問題を解くとよいでしょう。
ユークリッドの互除法-復習問題

容量的にこれらの解答はアップすることができないので、これらの問題の解答が欲しい、もしくは解いた解答を採点して欲しい方は、申し訳ありませんが下記から当塾の無料添削会員に登録してください。
無料添削会員申し込みはこちら
※無料とはいいながら登録手数料が年間3150円かかります
※東京大学合格を目指す方のみを対象とさせていただきます
※万が一30問以上添削を提出した場合は当塾の合格実績に含めさせていただきます
スポンサーサイト

Comment

Comment Form
公開設定

Trackback


→ この記事にトラックバックする(FC2ブログユーザー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。