A�T� ここで ��~B(�7r�\e!�B�%��6� ユークリッドの互除法、2進法の足し算引き算かけ算がなかなか理解しにくいです 何かコツありますかあと34日ほどで数学a範囲の準2級受けます小学校というか、その前から使っているので、十進法をわかった気になっている、ということだと あなたは、教科書・参考書などで、次のような問題を見たことがありますか？「\( 37x + 32y = 1 \)を満たす整数解を求めよ」そして、解答を見ると、いきなりユークリッドの互除法が使われていたり。そう思ったことはありませんか？ここでは、そこで、まずは、教科書・参考書ではどのような解答がされているかを見ていきます。\( 37x + 32y = 1 \)のような方程式が１つ与えられても、未知数が\( x,y \)の２つあるので、普通は解くことはできません。このような方程式をしかし、未知数\( x,y \)を整数に限定した場合、方程式の解をいくつか求めることができます。そこで、次の問題を考えてみましょう。（問題）次の方程式の整数解をひとつ求めよ。\[ 37x + 32y = 1 \]まず、教科書や参考書に一般的に載っている解答を紹介します。\( 37 \) と \( 32 \) に対して、ユークリッドの互除法を繰り返し用いると\begin{align*}\( (1) \) ～ \( (3) \) の式は、それぞれ\begin{align*}のように式変形できる。そして、\( (3) \) の式の下線を引いた\( 2 \)に、\( (2) \) の式を代入し、係数 \( 32 \) と \( 5 \) の項をそれぞれまとめる。\begin{align*}そして、いま計算した式の下線を引いた\( 5 \)に、\( (1) \) の式を代入し、係数 \( 37 \) と \( 32 \) の項をそれぞれまとめる。\begin{align*}以上より\[ 1 = 37 \cdot 13 \ + 32 \cdot (-15) \]であるから、\( x = 13 \)、\( y = – 15 \) は \( 37x + 32y = 1 \)を満たす整数解のひとつである。この解答を見た時って思いませんでしたか？参考書によっては、”ユークリッドの互除法を逆にたどって”などと書いているものもありますが、「正直、わかりにくいよな…」というのが本音です。なので、そのためにも、教科書や参考書の解答は忘れて、初めて不定方程式の問題に出会ったつもりで一緒に考えていきましょう。たとえば、\( x = 1, y = -1 \)のときは\[ 37 – 32 = 5 \]より満たさない。\( x = 4, y = -5 \)のときは\begin{align*}より満たさない。\( x = -6, y = 7 \)のときは\begin{align*}より満たさない。いま、３つほど計算してみましたが、計算も大変ですし、何度も計算してたらしんどいですよね。たとえば、実際、\( x = 1, y = -2 \)のとき\begin{align*}となり、方程式を満たす整数解が簡単に求められます。では、それは、未知数\( x,y \)の係数の大小が大きく関わっています。実際、\( x,y \)の係数は、\( 37x + 32y = 1 \)では\( 37 \)、\( 32 \)と２桁なのに対して、\( 5x + 2y = 1 \)では\( 5 \) と \( 2 \) で１桁です。桁数が少ないほうが簡単に計算を行えますよね。つまり、そう考えたとき、参考になるのが、具体的には、\( 56 \)を\[ 56 = 36 + 20 \]のように分けたところです。この考え方に基づいて、係数を小さくしていくことを考えましょう。\begin{align*}と式変形できます。ここで、\( z = x + y \)と置くと\[ 32z + 5x = 1 \]となります。つまり、そこで、同様の操作を繰り返し、方程式\( 32z + 5x = 1 \)の大きい方の係数\( 32 \)は\[ 32 = 5 \times 6 + 2 \]と分けることができるので、\begin{align*}ここで、\( w = 6z + x \)と置くと\[ 5w + 2z = 1 \]となります。よって、係数が小さくなった方程式\( 5w + 2z = 1 \)が解ければ、方程式\( 32z + 5x = 1 \)も解けます。また、\( w,z \)の係数が十分小さくなったので、方程式\( 5w + 2z = 1 \)の整数解をいくつか求めることができます。実際、\( w = 1, z = -2 \)は方程式\( 5w + 2z = 1 \)を満たします。以上より、方程式\( 37x + 32y = 1 \)を満たす\( x ,y \)には\begin{cases}を満たすものがあるということがわかります。\( w = 1 \)、\( z = -2 \) をそれぞれの式に代入すると\begin{cases}よって、元の不定方程式\( 37x + 32y = 1 \)の整数解のひとつとして\begin{cases}があります。

��!�Be���������55���5 ��~�C���/'=G�_Qe��ى8��݋���ϖ� ��٠���(�Bs��h�`��FQ�7��`�l�B� 8������T����'n��ь~ݡ��J�\��87u殅�/� V�~ ! すなわち 2 つの自然数 a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。 よって、最大公約数は21である。 こんにちは、ウチダショウマです。突然ですが、皆さんはこういった悩みを抱えてはいませんか？整数の性質における最大の鬼門。それが「よって本記事では、「の僕がわかりやすく解説します。ユークリッドの互除法の原理を一言でまとめるならば…これに尽きます。ただ、これだけだとわかりづらいと思うので、図解して説明します。割り算の等式 $a=bq+r$ を繰り返して考えていくことによって、値はどんどん小さくなっていきます。よって、最初はわかりづらかった $GCD( \ a \ , \ b \ )$ であっても、と繰り返していけば、必ずいつかは簡単に求めることができる、という原理なわけです。等式 $GCD( \ a \ , \ b \ )=GCD( \ b \ , \ r \ )$ を示すコツとして、の $2$ つに分ける、という発想があります。この発想は、知らないと中々出てこないと思います。ということで、証明ついでに押さえておきましょう。一々書くのが面倒なので、$GCD( \ a \ , \ b \ )=G$，$GCD( \ b \ , \ r \ )=G’$ と定義し直す。①　$G≦G’$ を示す。$a$ と $b$ の最大公約数が $G$ であるから、ある互いに素な自然数 $k$，$l$ を用いて$$a=Gk \ , \ b=Gl$$と表すことができる。これを等式「 $a=bq+r$ 」に代入すると、$Gk=Glq+r$ となり、$r$ についてまとめると$$r=G(k-lq)$$ここで、$k-lq$ は整数なので $G$ は $r$ の約数となり、$G$ は $b$ の約数でもあるので、$b$ と $r$ のよって、$b$ と $r$ の”②　$G’≦G$ を示す。ほとんど同じ方針で示すことができるので省略します。式だけ書くと、ある互いに素な自然数 $m$，$n$ を用いて$$a=G'(mq+n)$$を導くことができればOKです。したがって①，②より、$G≦G’$ かつ $G≧G’$ なので、$G=G’$ が成り立つ。これで、「さて、原理は理解できたので、次に考えるのは活用方法です。ユークリッドの互除法の活用は、主にの $2$ つですので、順に解説していきます。まあ、ユークリッドの互除法の原理の中に最大公約数が出てきたので、活用としても当然出てきますよね。もし素因数分解ができるのであれば、最大公約数は簡単に求めることができました。ただこの問題のように、(1)　互除法を使ってどんどん割っていくと、$6499=1261×5+194$$1261=194×6+97$$194=97×2$したがって、$GCD(6499 \ , \ 1261)=GCD( \ 194 \ , \ 97 \ )=97$ と求まる。(2)　互除法を使ってどんどん割っていくと、$1073=527×2+19$$527=19×27+14$$19=14×1+5$$14=5×2+4$$5=4×1+1$したがって、$GCD( \ 1073 \ , \ 527 \ )=GCD( \ 4 \ , \ 1 \ )=1$、つまり互いに素である。(2)の場合、$GCD( \ 19 \ , \ 14 \ )=1$ の時点でわかるので、そこで止めても構いません。ただ、余りが $1$ になるまで互除法を行ったのには深いわけがあります。それは…次の方程式を満たす $1$ 組の簡単な解のことを「ここでは、さっきの「最大公約数を求める問題」で行ったユークリッドの互除法を用いて、(1)(2)それぞれを満たす特殊解を求めていきましょう。(1)　互除法を逆の順番で書き、かつ両辺を入れ替えて、かつ移項すると、$$97×2=194 \ ⇔ \ 97=194-97　…①$$この $3$ つの式から、よって、$x=7$，$y=-36$ が整数解の $1$ つ（特殊解）である。(2)　互除法を逆の順番で書き、かつ両辺を入れ替えて、かつ移項すると、$$5=4×1+1 \ ⇔ \ 1=5-4×1　…①$$$$14=5×2+4 \ ⇔ \ 4=14-5×2　…②$$$$19=14×1+5 \ ⇔ \ 5=19-14×1　…③$$この $5$ つの式から、よって、$x=111$，$y=-226$ が整数解の $1$ つ（特殊解）である。…やっていることは理解できましたか？ユークリッドの互除法を使うことでのように、地道な道のりですが数字を変換していくことができるのです！また、ここで仮に「 $1073x+527y=2$ 」という一次不定方程式の特殊解について考えてみると、(2)より$$1073×111-527×226=1$$なので、両辺を $2$ 倍することで$$1073×222-527×452=2$$となり、$x=222$，$y=452$ と特殊解がすぐに求まります。以上より、こんなことも判明してしまいます。ここまで理解できると、いろんな知識が結びついてきて面白いのではないでしょうか＾＾あとの話は「さて、ユークリッドの互除法についての重要な部分の解説は終わりました。あとはコラム的なお話です。具体的にはこの $2$ つについて解説します。さきほど、ユークリッドの互除法を実際にやってみて、と多くの方が感じたと思います。でもご安心ください。僕もそう感じていますので。(笑)そこで、書く量をもう少し抑えるために、何にも変なことはしていません。割り算を、筆算の形で計算しただけです。筆算の方がので、慣れてきたらこの裏ワザを使ってみるのもオススメです♪もちろん、$1$ 辺が $1 \ (cm)$ の正方形であれば、$377×319$ 個使って敷き詰めることができますが、ここで聞かれているのは「実はこの問題は、ユークリッドの互除法で計算することに対応しているのです！なるべく大きな正方形をどんどん除いていく方針で考えていこう。すると、以下のアニメーションのようになる。つまりこの操作は、$377=319×1+58$$319=58×5+29$$58=29×2+0$と、よって、$377$ と $319$ の最大公約数が $29$ であることがわかったので、条件を満たす正方形で最大のものは、$1$ 辺が $29 \ (cm)$ の正方形である。代数的な計算が、図形と結びつく瞬間はたまらなく気持ちいいですね！本記事の要点を改めて $3$ つまとめます。ユークリッドの互除法をしっかり理解して、整数マスターになろう！！終わりです。© 2019 遊ぶ数学.