今回は 2020 年度入試の島根大学／医学部・総合

m > n をみたす自然数 m と n の最大公約数を(3)

理工学部／前期日程の過去問を，少しだけ誘導をd とすると，am と an の最大公約数は ad であるこ削って出題しました．以下，問題を確認してみましょとを示せ．ただし，必要であれば，枠で囲まれたう．

ユークリッドの互除法の説明文で使用されている記号を用いてもよい．

問題

a12345 と a54321 の最大公約数を求めよ．

(4)
自然数 m，n に対し，m と n の最大公約数をまずは，(1) と (2) の解答について考察します．

gcd(m，n) で表す．以下はユークリッドの互除法を用いた最大公約数の求め方である．

［解答］
ユークリッドの互除法(1)m，n を m > n をみたす自然数とし，r1 = m，m，n は m > n を満たす自然数であるから．

m - n ≥ 1 であり

r2 = n とおく．r1 を r2 で割った商を q2，余りを r3

m -1(0 ≤ r3 < r2) とする．もし r3 π 0 ならば r2 を r3 で

am - an =割った商を q3，余りを r4 (0 ≤ r4 < r3) とする．このS 10= 10 n

r1 = mkm - n- 1

S 10kk 0

r2 = nr1 = r2 q2 + r3

(0 < r3 < r2)

r2 = r3 q3 + r4

(0 < r4 < r3)\am - an = 10nam - n B1（証明終）B
rk - 2 = rk - 1 qk - 1 + rk (0 < rk < rk - 1)

《解説》
am は 1 が m 桁，an は 1 が n 桁並ぶので，差をとrk - 1 = rk qk

るとこのとき，m と n の最大公約数について，gcd(m，n) = gcd(r1，r2) = gcd(r2，r3) = …

111B1111B1111…… = gcd(rk - 1，rk ) = rk-が成り立つ．

11B1111
111B1100B0000となり，1 が m - n 桁並んだ後に 0 が n 桁並ぶ数に自然数 n に対し，すべての位の数字が 1 である n 桁なります．後ろに並ぶ n 桁分の 0 を 10 のべき乗のの自然数を an とおく．例えば，a1 = 1，a2 = 11，積で表せば

a3 = 111 であり，すべての n に対して
an = 1 + 10 + 10 + ºº + 102

n -1n -1

=S 10

am - n • 10nkとなります．以上の内容を，数式で表現すればよい

k 0でしょう．

である．次の問いに答えよ．
m > n をみたす自然数 m と n に対し，等式［解答］

am - an = 10n am - n が成り立つことを示せ．
(2)

kk 0

k n

れば，次の関係式が成り立つ．

(1)

kk 0

m -1

=

手順を k - 1 回繰り返したとき，余り rk + 1 が 0 にな

n -1

S 10 - S 10(2)(1) の結果を用いて，m > n をみたす自然数 mgcd(am，an) = G1gcd(an，am - n) = G2と n に対し，gcd(am，an) = gcd(an，am - n) が成とおく．am，an，am - n は 1 の位が偶数でも 5 でり立つことを示せ．

もなく，10 ( = 2 • 5 ) と互いに素であるから1G1，G2 はいずれも 10 と互いに素B2は用いることができます．この考え方を利用した問である．

題が，2016 年度／神戸大学／理系／前期日程の 4 番

まず，G1 は am と an の公約数である．よってでも出題されています．

(1) の 1 の左辺の am - an は G1 を約数にもつから，1 の右辺の 10nam - n も G1 を約数にもつ．2 より，続いて，(3) が証明できれば (4) は簡単なので，まam - n が G1 を約数にもつ．以上より，G1 は an とず (4) の解答を紹介します．

am - n の公約数であるから，G2 の最大性より
G1 ≤ G2

B3［解答］（(3) は証明できたものとして）が成り立つ．

(4)54321 = 12345 • 4 + 4941

次に，
G2 は an と am - n の公約数である．さらに (1)12345 = 4941 • 2 + 2463の 1 より4941 = 2463 • 2 + 15n

am = an + 10 am - n

B42463 = 15 • 164 + 3である．4 の右辺の an + 10 am - n は G2 を約数
n15 = 3 • 5にもつから，4 の左辺の am も G2 を約数にもつ．

であるから，ユークリッドの互除法より以上より，G2 は am と an の公約数であるから，gcd(54321，12345) = 3

G1 の最大性よりG2 ≤ G1である．よって，(3) より
B5gcd(a54321，a12345) = a3 = 111が成り立つ．

である．

よって，3，5 より《解説》G1 = G2すなわちさて，メインである (3) に取り掛かりましょう．

gcd(am，an) = gcd(an，am - n)B6

証明したい命題は，m > n を満たす自然数 m，n にが成り立つことが示された．

対し（証明終）「gcd(m，n) = d⇒gcd(am，an) = ad」

です．また，手前の小問が誘導になっている可能性《解説》が高いので今回の解答と同様にして，ユークリッドの互除法

gcd(am，an) = gcd(an，am - n)B6も証明できますが，今回の証明の中では an と am - nの生かし方を考えてみましょう．6 が表しているのの大小関係は用いていません．よって ，ユークリッは gcd(am，an) を考える際，桁数が多い方から桁数ドの互除法のが少ない方の桁数の分だけ 1 を削って考えても最大

r1 = r2 q2 + r3

B(*)

公約数が一致する，ということです．具体的に考えにおいて，r2 と r3 の大小関係によらずgcd(r1，r2) = gcd(r2，r3)

ると，例えばB(**)

a28 = 1111B1111111111（1 が 28 桁）が証明できます．

a12 = 111111111111（1 が 12 桁）

ユークリッドの互除法を用いる際は，扱う自然数の最大公約数は，28 桁から 12 桁削ってを小さくしていきたいので，r3 がなるべく小さくな

a16 = 1111111111111111（1 が 16 桁）

るように「r1 を r2 で割った余り」として設定するのa12 = 111111111111（1 が 12 桁）が普通ですが，実際には，(*) の形さえ作れれば，(**)

で考えてもよい，ということです．このことは，一2

般に大小関係のある桁数であれば証明できています［解答］から，繰り返し用いることができます！つまり，16(3)桁からさらに 12 桁削って枠で囲まれたユークリッドの互除法の説明文で使用されている記号に対し，r1 = m， r2 = n，a4 = 1111（1 が 4 桁）

rk = d として，r1 ，r2 ，B，rk と q2 ，q3 ，B，

a12 = 111111111111（1 が 12 桁）

qk を定める．k が 3 以上の自然数のとき，i = 1，で考えられる，ということです．12 桁を削るのは 12，B，k - 2 に対して， (2) で示したことを繰回だけではなく，桁数が 12 桁以下になるまで何回り返し用いてªでも削ることができます．このことを文字を用いてºª= gcd ª a , agcd ari , ari + 1 = gcd ari + 1 , ari + 1 - ri

表すと，以下のようになります．

ri + 1ººri + 1 - 2 ri

= ººº

gcd(am，an) = gcd(an，am - n)ªº
= gcd ª a , a º= gcd ari + 1 , ari + 1 - ri qi= gcd(an，am - 2n)= gcd(an，am - 3n)ri + 1=Bri + 2が成り立つ．よって= gcd(an，am - l n)ªº
= gcd ª a , a º= gcd(an，am - (l + 1)n)gcd(am , an ) = gcd ar1 , ar2（ただし l は，m - ln > n を満たす最大の自然数）

r2

r3

= ººº

ªº
= gcd ª a , a º= gcd ª a , a ºm から n を引ける限り引く．これすなわち，m= gcd ark - 1 , ark

を n で割って余りを考えることにほかなりません．ということは，問題で与えられたユークリッドの互除法の記号が活用できそうですね．
加えて，先に挙げた

r k qkrkdqkdとできる．k = 2 のときも，r1 = r2 q2 = dq2 かつ

a4 = 1111（1 が 4 桁）

r2 = d であるから，これでよい．qk が 2 以上の自a12 = 111111111111（1 が 12 桁）

然数であるとき，(2) で示したことを，再度繰り返まで来ると，桁数の大小が入れ替わりましたので，し用いて次は立場を逆にして，a12 から 4 桁ずつ削っていくªºª= gcd ª a , agcd adqk , ad = gcd ad , adqk - d

ことができます．ここでも，できる限り桁数を削っていくと，まず

da4 = 1111（1 が 4 桁）

dqk - 2 d= ºººªa8 = 11111111（1 が 8 桁）

= gcd ad , adの 2 数になります．さらに削るとººº= ada4 = 1111（1 が 4 桁）が成り立つ．qk = 1 のときも，これでよい．以上

a4 = 1111（1 が 4 桁）

よりと同じ数になり，a4 が最大公約数だとわかります．

gcd(am，an) = ad

以上の内容を，問題で与えられた記号を活用しなが成り立つことが示された．

がら，一般に文字で記述してみましょう．

（証明終）

3

《解説》
いかがでしたでしょうか．おそらく，強者たらんとしている皆さんであれば，模範解答を見てしまえば，なんとなく解法の流れの雰囲気を察してしまえるのだと思います．ただ，今回の場合は，大学入試の会場で模範解答なしで，自分の頭の中にある考えを問題で与えられた記号と上手に繋げて説明する力が求められています．他の出題者の皆様も頻繁に話題に出していると思いますが，この問題に限らず，初見の問題（特に数列，確率，整数）は，具体的に実験して様子を確認する手法が有効です．具体例を踏まえて(2) の証明結果から，gcd(am，an) (m > n) を考える際に，桁数について m から n を（大小関係が保たれる限り）引くことができる．
↓
なるべく桁数が小さくなるように考えると，mから n をできる限り引きたい．これはすなわち，割り算である．
↓
am，an の桁数，つまり，添字の番号の部分について，ユークリッドの互除法の記号が使える．と思考を繋げて，問題の記号の生かし方を思いつきたいところです．
今年初めての「共通テスト」が実施され，今後は今まで以上に「共通テスト」用の問題集が出版され，書店などに並ぶことになると思います．その演習をする際，初見の問題に出会ったときはチャンスです！今回のような入試問題で使う力を磨くべく，マークシート形式であってもなるべく記述答案を作成し，初見の問題に対する答案作成能力を高めていきましょう．
（数学科中西）4