1東北大学オープンキャンパス 2006 数学クイズ解答黒木玄(東北大学大学院理学研究科数学専攻)
2006 年 7 月 28 日 (木)〜29 日 (金)

1

問題と解答
a, b は整数であり, n は 0 でない整数であるとする. a − b が n で割り切れるとき,a≡b(mod n)と書き, a と b は n を法として合同であると言うことにする. たとえば 1 ≡ 4 (mod 3),
2 ≡ −3 (mod 5) である. a ≡ b (mod n) は a と b を n で割った余りが互いに等しいことだと考えてもよい.
問題 1 以上の準備のもとで以下の問題に挑戦せよ.

1. n = 7, 11, 13 のとき 175342 ≡ −175 + 342 (mod n) が成立することを両辺を n =7, 11, 13 で割った余りを実際に計算することによって確認せよ.
2. 一般に, 6 桁の数 a の上位 3 桁と下位 3 桁のれぞれを b, c と書く (a = 1000b + c).
このとき a と −b + c を n = 7, 11, 13 で割った余りが互いに等しくなることを証明
せよ.
ヒント. 一般に a ≡ a0 (mod n) かつ b ≡ b0 (mod n) のとき a + b ≡ a0 + b0 (mod n) とab ≡ a0 b0 (mod n) が成立する. 実際 a − a0 = kn, b − b0 = ln のとき, a + b − (a0 + b0 ) =a − a0 + b − b0 = kn + ln = (k + l)n であり, ab − a0 b0 = (a0 + kn)(b0 + ln) − a0 b0 =a0 ln + kb0 n + kln2 = (a0 l + kb0 + kln)n である. したがって a ≡ b (mod n) をあたかも通常の等号のごとく扱って構わない.
解答. 1. 175342, −175 + 342 = 167 を 7 で割った余りはともに 6 になり, 11 で割った余りはともに 2 になり, 13 で割った余りはともに 11 になる.
2 の証明. 7 · 11 · 13 = 1001 であるから n = 7, 11, 13 のとき 1000 ≡ −1 (mod n) である.
よって 1000b ≡ −b (mod n) である. したがって a = 1000b + c ≡ −b + c (mod n).
問題 2 10222 を 23 で割った余りを求めよ.
解答. 直接的計算もしくはフェルマーの小定理より 1022 ≡ 1 (mod 23) であることがわかる. (直接的計算で 10k ≡ 1 (mod 23) となる k を見付けるためには 10, 100, 1000, 10000, . . .
を 23 で割った余りが 1 になるまで計算を続けて最後に 0 の個数を数えればよい. 筆算による割り算の計算で余りが 1 にならないとき割られる数の一番右に 0 を追加して計算を続けることは易しいので, 実際にやってみれば見掛けより手間がかからないこともわかる. フェルマーの小定理を知っていれば面倒な計算抜きで 1022 ≡ 1 (mod 23) であることがわかる. フェルマーの小定理については解説の節を見よ.)1022 ≡ 1 (mod 23) を使って10222 ≡ (1022 )10 · 102 ≡ 110 · 102 ≡ 100 ≡ 8
したがって 10222 を 23 で割った余りは 8 である.

(mod 23).

2問題 3 9, 99, 999, 9999 のように 9 だけが並んでいる数を素因数分解してみよう:

9 = 32 ,99 = 32 · 11,99999 = 32 · 41 · 271,999 = 33 · 37,9999 = 32 · 11 · 101,999999 = 33 · 7 · 11 · 13 · 37,......

これで 9 だけが並んだ数の素因数として少なくとも 3, 7, 11, 13, 37, 41, 101, 271 が現われることがわかった. (9 だけが並んだ数は 2, 5 で割り切れないので 2, 5 が現われないのは当然である.) 13 の次の素数 17 やその次の素数 19 で割り切れる 9 だけが並んでいる数は存在するだろうか? さらにそれ以降の素数についてはどうなっているのだろうか?

1. 17 で割り切れる 9 だけが並んでいる数をひとつ見付けよ.
2. 19 で割り切れる 9 だけが並んでいる数をひとつ見付けよ.
3. 2 と 5 以外の任意の素数 p に対して, p で割り切れる 9 だけが並んでいる数が存在することを証明せよ.
解答. 1, 2 の解答. 9, 99, 999, 9999, . . . を 17 (もしくは 19) で割った余りを次々に計算し,余りが 0 で無ければ一番右側に 9 を追加して桁数を一つ増やし (割り算の筆算の途中で一番右側に 9 を追加することは易しい), 割り切れるまで計算を続行すれば良い. その結果, 9999999999999999 = (9 が 16 個並んだ数) は 17 で割り切れ, 999999999999999999 =(9 が 18 個並んだ数) は 19 で割り切れることがわかる.
3 の証明. p で割った余りの可能性は 0, 1, . . . , p − 1 の p 通りしかないので, p + 1 個の数 1, 10, 102 , . . . , 10p を p で割った余りを考えると, それらのうちどれか 2 つの余りは一致している (鳩の巣論法). それらを 10i , 10j , i < j と書くことにする. 10i と 10j を p で割った余りは一致しているので 10j − 10i = 10i (10j−i − 1) は p で割り切れる. p は 2 と 5以外の素数なので 10j−i − 1 = (9 が j − i 個並んだ数) が p で割り切れなければいけない.
実は完全に同じ方法によってより一般的に次が成立していることを示せる.

4. 2 つの自然数 a と n の最大公約数が 1 ならばある正の整数 k で ak − 1 が n で割り切れるものが存在する (オイラーの定理の弱形).
証明. n で割った余りの可能性は 0, 1, . . . , n − 1 の n 通りしかないので, n + 1 個の数
1, a, a2 , . . . , an を n で割った余りを考えると, それらのうちどれか 2 つの余りは一致している. それらを ai , aj , i < j と書くことにする. ai と aj を n で割った余りは一致しているので aj − ai = ai (aj−i − 1) は n で割り切れる. a と n の最大公約数は 1 であると仮定したので aj−i − 1 が n で割り切れなければいけない.
より強い形の本来のオイラーの定理については解説の節を見よ. 上の弱形では k として具体的にどのような数が取れるかわからないが, もともとのオイラーの定理ではその点が明らかになっている.
1, 2, 3 の別解. フェルマーの小定理より p が 2 と 5 以外の素数ならば 10p−1 − 1 =(9 が p − 1 個並んだ数) は p で割り切れることがわかる. 特に (9 が 16 個並んだ数) は17 で割り切れ, (9 が 18 個並んだ数) は 19 で割り切れる. フェルマーの小定理については解説の節を見よ.

32

解説

2.1

問題 1 について

問題 1 の解答と同様にして,1000k ak + · · · + 1000a1 + a0 ≡ (−1)k ak + · · · − a1 + a0

(mod n),n = 7, 11, 13が成立することがわかる. 特に自然数 a が n = 7, 11, 13 で割り切れるための必要十分
条件は a を下位から 3 桁ごとに区切ってそれらを交互に ±1 倍して足し上げた結果がn = 7, 11, 13 で割り切れることである. 3 桁以上の数の足し算と引き算を高速にできる人
は n = 7, 11, 13 で割った余りを容易に計算できることになる.
n = 3, 9 のとき 10 ≡ 1 (mod n) なので問題 1 の解答と同様にして

10k ak + · · · + 10a1 + a0 ≡ ak + · · · + a1 + a0(mod n),n = 3, 9が成立することもわかる. 特に自然数 a が n = 3, 9 で割り切れるための必要十分条件はa のすべての桁を足し上げた結果が n = 3, 9 で割り切れることである. n = 3, 9 で割り切れるかどうかに関するこの判定法は有名である. しかしその判定法が常に成立することの理由 (証明) について知っている人はどれだけいるだろうか? 合同式 a ≡ b (mod n) を導入すればその証明は非常に簡単になる.
n = 3, 9 で割り切れるかどうかの楽な判定法や n = 7, 11, 13 で割り切れるかどうかの上の判定法を知っていれば計算が楽になる. そして計算を楽にする方法の裏には合同式a ≡ b (mod n) に関する一般論という数学的一般法則が隠されている. 大学の数学科ではそのような裏に隠された数学的一般法則について学ぶことになる.
数学の歴史は数千年以上あるのだが, そのあいだに多くの数学的一般法則が明らかにされ, 努力さえすれば誰にでも利用できるように整備されている. (しかも無料で好きなだけ使える!)
我々のデジタル文明社会においては生活のあらゆる場面で数学的一般法則が利用されている. たとえば CD を聴いている人は CD のデジタル符号化や誤り訂正の基礎になる数学的一般法則を利用しており, 携帯電話を使っている人も同様である. そのようなデジタル機器で利用されている数学的一般法則の多くは問題 1 で使われた合同式の話を発展させたものになっている. たとえば次の節で説明するフェルマーの小定理は最も基礎的な一般法則としてよく使われている.

2.2

問題 2 について10222 を 23 で割った余りを直接計算しようとした方がいたとすれば御苦労様!
数学において重要なのは「楽をするための方法」である. しかも特定の場合ごとに楽をするための方法を見付けることよりも広い範囲に適用できる裏に隠された数学的一般法則を見付けることが重要である. 数学の研究とはまだ発見や証明がされていな
いそのような法則を発見したり証明したりすることである.
問題 2 の解答で使われているそのような一般法則は問題 1 のヒントに書かれている合同式の計算に関する一般法則と次のフェルマーの小定理であると考えて良い. もちろんフェルマーの小定理を知らなくても直接的計算で 1022 ≡ 1 (mod 23) を確認できるがかなり面倒である. 次のフェルマーの小定理を知っていれば計算抜きで 1022 ≡ 1 (mod 23) であることがわかる.

4
フェルマーの小定理. p が素数であり, a が p で割り切れない整数であれば ap−1 ≡ 1(mod p) が成立している.
たとえば 26 ≡ 1 (mod 7), 44 ≡ 1 (mod 5) が成立していることは容易に確かめられる.
他の場合についても色々計算してみよ.
フェルマーの小定理の証明を知りたければ, 大学生向けの数学の教科書を参照したり,インターネットで「フェルマーの小定理 証明」を検索してみたり, 自分が数学を習っている先生に参考書を紹介してもらうのが良いだろう. もちろん大学の数学科に入学するまで待つという手もあるが, 興味を持ったことは自分の力を使ってすぐに調べてみた方が良い.
あなたが利用できる書籍, 資料, 人脈, コンピューターのすべてがあなたの力である. 数学の研究も自分自身が利用できるすべての力を用いて行なわれている.
注意. フェルマーの小定理と次のフェルマーの最終定理を混同しないようにして欲しい.
フェルマーの最終定理. n が 3 以上の整数のとき X n +Y n = Z n を満たす正の整数 X, Y, Zは存在しない.
フェルマー (1601–65) はこの定理を実際に証明できたと思っていたようだが実際には証明できていなかったので, この定理は「フェルマー予想」と呼ばれることが多い. 「フェルマー予想」はアンドリュー・ワイルスによって証明された. ワイルスは谷山豊によって予想された有理数体上の楕円曲線のモジュラー性を証明することフェルマー予想を証明した. フェルマー予想は楕円曲線のモジュラー性という谷山が予想した数学的一般法則から導かれるのである.

2.3問題 3 について問題 3 も本質的にフェルマーの小定理の応用問題だと考えて構わない. 計算を楽にするためにはフェルマーの小定理を積極的に使うべきである.
問題 3 の解答ではオイラーの定理の弱形を紹介・証明しているが, 強い形の本来のオイラーの定理は次のように述べられる.
オイラーの定理. n は正の整数であるとする. n の素因数分解を n = pe11 · · · perr (pi は互いに異なる素数, ei は正の整数) と書き, オイラー函数 ϕ(n) をµ¶ µ¶11e1e1 −1er −1er··· 1 −ϕ(n) = (p1 − p1 ) · · · (pr − p1 ) = n 1 −p1prと定める. このとき整数 a と n の最大公約数が 1 ならば aϕ(n) ≡ 1 (mod n).
たとえば n = 112 のとき ϕ(n) = 112 − 11 = 110 であるから, オイラーの定理より10110 − 1 は 112 で割り切れる. (実際には 1022 ≡ 1 (mod 112 ) が成立している.)
n = p = (素数) のとき ϕ(n) = ϕ(p) = p − 1 であるからオイラーの定理はフェルマーの小定理の一般化になっていることもわかる.
n が 2 でも 5 でも割り切れない正の整数であるとき, オイラーの定理を a = 10 に適用
すれば 10ϕ(n) − 1 = (9 が ϕ(n) 個並んだ数) が n で割り切れることがわかる.
群論を使えばオイラーの定理の証明はかなり易しくなる. 実際の証明を知りたい人はフェルマーの小定理の証明と同様に自分の力で色々調べてみて欲しい.