問1
方程式 が整数解をもたないことを示しなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
左辺 はいつも偶数で、右辺 は奇数なので、等号は成り立たない。
自己採点：
記録を読み込み中…
目次 ／ 整数の性質 ／ 数学A
第3章 一次不定方程式
—— 互除法を逆にたどって、方程式の整数解をすべて見つける ——
$3x + 5y = 1$ のように、文字が2つあるのに式が1つしかない方程式は、解が1つに定まりません。けれども $x$，$y$ を整数に限ると、解は規則正しく並びます。この章では、まず整数解があるかどうかを最大公約数で見分け、次に第2章の互除法を逆にたどって解を1組見つけます。そこから「すべての整数解」を1つの式で表し、最後に自然数に限る場合や文章題へと進みます。
一次不定方程式とは
第2章の最後に、互除法の式を逆にたどると のように、最大公約数を「」の形に表せることを見ました。この章では、これを方程式の側から考えます。
たとえば、方程式
を満たす整数 ， を探してみます。， とすると で、確かに成り立ちます。ほかにも探すと、次のような組が見つかります。
解は1つではなく、しかも が ずつ増えるたびに が ずつ減る、という規則正しい並び方をしています。
，， を整数（， は でない）として、 を満たす整数 ， を求める問題を一次不定方程式といいます。「不定」は、解が1つに定まらないという意味です。この分野では、とくに断らないかぎり文字は整数を表すので、単に「解」といえば整数解のことです。この章では、次の3つを順に考えます。
- そもそも整数解があるのか
- あるなら、1組をどうやって見つけるか
- 1組から、残りの解をすべてどう表すか
整数解をもつ条件
公式1：整数解をもつ条件
と の最大公約数を とする。方程式
が整数解をもつのは、 が の倍数であるときであり、そのときに限る。
とくに と が互いに素なら、どんな整数 に対しても整数解をもつ。
理由は2つに分けて考えます。
- が の倍数でないと解はない も も の倍数なので、， にどんな整数を入れても、左辺 は の倍数です。右辺 が の倍数でなければ、等号は成り立ちません。
- が の倍数なら解がある 第2章の厳密定義 定理4 で、 を満たす整数 ， が必ずあることを示しました。 なら、その ， をそれぞれ 倍すれば の解になります。
たとえば は、 と の最大公約数が で、 は の倍数ではないので、整数解をもちません。一方 は、 が の倍数なので整数解をもちます（， など）。
「 マス進むカード」と「 マス進むカード」だけで遊ぶすごろくを考えます。カードを使うたびに、進むか戻るかを自分で選べるとします。何枚使っても、動いたマス数は と を足したり引いたりした数なので、必ず偶数です。これでは、スタートから マス先には一生止まれません。カードが「 マス」と「 マス」なら、 マス進むを 回、 マス戻るを 回で、ちょうど マス先に行けます。止まれるマスを決めているのは、カードの数の最大公約数なのです。戻ることを「負の回数だけ進む」と考えると、これはそのまま の話になります。
はいつも と の最大公約数の倍数なので、右辺 がその倍数かどうかで、整数解があるかどうかが決まるということです。
例題1：整数解があるかどうか
(1) 方程式 が整数解をもたないことを示しなさい。
(2) 方程式 の整数解を1組求めなさい。
【解答】
(1) で、 は整数なので、， がどんな整数でも左辺は の倍数です。一方、 は の倍数ではありません。よって等号が成り立つことはなく、この方程式は整数解をもちません。（証明終）
(2) 両辺を で割ると です。 とすると で なので
が1組の解です（）。ほかにも ， などがあり、答えは1つではありません。
互除法で解を1組見つける
のように係数が小さいときは、あてずっぽうでもすぐに解が見つかります。けれども となると、試すだけでは大変です。そこで、第2章の互除法を使います。
公式2：互除法で解を1組見つける
， が互いに素な自然数のとき、 の整数解は次の手順で1組見つかる。
- と に互除法を行う。
- 各段の余りを、「余り 割られる数 割る数 商」として、上の段から順に「」の形で表す。
- 余り にたどり着いたときの ， の係数が、， である。
の解は、 の解を 倍すれば得られる。
で実際にやってみます。まず互除法です。
余りが になったので、ここで止めます（ と は互いに素です）。次に、， として、余りを上から順に と で表していきます。
最後の行から で、， が1組の解です。確かめると となっています。
途中で と をわざわざ ， と書いたのには理由があります。数のまま計算を進めると、 や がいつの間にかふつうの数に埋もれて、最後に「 が何個、 が何個」だったのかが分からなくなってしまうからです。文字にしておけば、 と の個数が最後まで見失われずに残ります。
童話『ヘンゼルとグレーテル』で、兄のヘンゼルは森の奥へ連れて行かれるとき、白い小石を少しずつ落としていきました。夜になっても、月明かりに光る小石をたどって家に帰れました。公式2の手順も同じで、互除法で数を小さくしながら進むときに、各段の余りに「 をいくつ、 をいくつ使ったか」という目印を付けておきます。余り にたどり着いたとき、答えはもう目印に書かれているのです。
第2章の厳密定義のように、互除法の式を下から逆にたどって代入していく方法でも、同じ解が得られます。どちらを使ってもかまいませんが、上から順に進める方法は、互除法の計算と同時に進められて、書き間違いにも気づきやすいのが利点です。
互除法の各段の余りを と の式で表しながら進めば、余りが になったところで の解が手に入るということです。
例題2：互除法で解を見つける
(1) 方程式 の整数解を1組求めなさい。
(2) 方程式 の整数解を1組求めなさい。
【解答】
(1) と に互除法を行います。
， として、余りを上から順に表します。
よって で、 が1組の解です（）。
(2) (1) の式の両辺を 倍すると、 です。よって が1組の解です。
(2) の解はずいぶん大きな数になりました。次の公式3を使うと、， のような小さい解に取りかえることもできます。
すべての整数解
1組の解が見つかったら、次は残りの解です。章の最初の表で見た「 が 増えると が 減る」という規則が、そのまま答えになります。
公式3：一次不定方程式の一般解
と が互いに素で、， が の整数解の1つであるとき、すべての整数解は
と表される。
1組の解を特殊解、すべての解をまとめて表した式を一般解といいます。
一般解は、式を覚えるよりも、毎回次のように導くほうが確実です。 と を辺ごとに引くと
となります。右辺は の倍数なので、左辺の も の倍数です。ところが と は互いに素で、 の素因数は には1つも含まれていません。だから の素因数はすべて のほうに含まれていて、 が の倍数になります（第1章の厳密定義 定理5(2)）。 とおいて元の式に入れると、 より です。
逆に、， を代入すると
となり、どの でも解になっています。章の最初の表は、 の一般解 ， で としたものだったのです。
と が互いに素でないときは、公式1で解があることを確かめたうえで、先に両辺を最大公約数で割って、係数を互いに素にしてから考えます。
3分の曲と5分の曲を並べて、ちょうど41分のプレイリストを作るとします。3分の曲 曲と5分の曲 曲で、 分です。ここから3分の曲を 曲抜いて、代わりに5分の曲を 曲入れても、抜いた 分と入れた 分が同じなので、合計は41分のままです。3分の曲 曲と5分の曲 曲です。 と は互いに素なので、合計を変えずに入れかえられる最小の単位は「5曲と3曲」で、これより少ない曲数ではうまく入れかえられません。一般解の は、この入れかえを何回行ったかを表しています。
1組の解 が見つかれば、あとは に ずつ、 に ずつ加える入れかえで、すべての解が得られるということです。
例題3：すべての整数解を求める
(1) 方程式 の整数解をすべて求めなさい。
(2) 方程式 の整数解をすべて求めなさい。
【解答】
(1) 本文で求めた の両辺を 倍すると、 です。 から辺ごとに引くと
と は互いに素なので、 は の倍数です。 とおくと で
です。ここで を におきかえると、， となり、数が小さくなります。よって
です。 のとき で、確かに解になっています。
(2) と の最大公約数は で、 は の倍数なので解があります。両辺を で割ると
， とすると なので、これが1組の解です。辺ごとに引くと
と は互いに素なので、 は の倍数です。 とおくと より で
です。
(1) のように、一般解の表し方は1通りではありません。 の置き方がずれているだけで、表している解の集まりは同じです。(2) は の係数が負なので、公式3に当てはめると符号を間違えやすいところです。辺ごとに引いて導けば、符号で迷うことはありません。
条件つきの整数解
実際の問題では、， が個数や人数を表していて、「自然数に限る」「0 以上に限る」といった条件がつくことがよくあります。
公式4：条件をみたす整数解の求め方
， に範囲の条件がついた一次不定方程式は、次の手順で解く。
- 一般解 ， を求める。
- 条件（たとえば ，）に一般解を代入し、 の不等式を作る。
- 不等式を満たす整数 をすべて求め、， にもどす。
を満たす自然数 ， を求めてみます。， が解なので、一般解は ， です。
は整数なので で、 の3組です。
座標平面で見ると、 は直線で、その整数解は直線上の「 座標と 座標がともに整数の点」です。こうした点を格子点といいます。一般解の形から、格子点は直線上に等間隔に並んでいて、条件の範囲に入るものだけを数えればよいことが分かります。
道路沿いに m おきに木が植えられた並木道で、「公園の入口から出口までの区間に何本あるか」を数えるとき、全部の木を1本ずつ調べる人はいません。1本の木の位置と間隔 m が分かっていれば、入口と出口の位置から、区間に入る木の番号の範囲がすぐに決まります。一般解の は木の番号、条件の不等式は区間の入口と出口にあたります。
整数解は一般解の で番号づけされて等間隔に並ぶので、条件を の不等式に直せば、条件に合う解がもれなく見つかるということです。
例題4：条件つきの整数解（文章題）
1本 円のジュースと1本 円のお茶を、どちらも1本以上買って、代金の合計をちょうど 円にしたい。
(1) ジュースとお茶の本数の組をすべて求めなさい。
(2) 買う本数の合計が最も少なくなる買い方を求めなさい。
【解答】
(1) ジュースを 本、お茶を 本とすると、， は自然数で
です。 とすると で なので、， が1組の解です。辺ごとに引くと
と は互いに素なので、 とおけて、 です。一般解は
です。 より で 、 より で です。よって で
です。（確かめ）， です。
(2) 本数の合計は 本と 本なので、 です。
(1) の特殊解は、ここでは を と試して見つけました。試しても見つからないような大きな数のときは、公式2の互除法で の解を作り、 倍してから一般解を求めても、同じ答えにたどり着きます。
この章では、整数解があるかどうかを最大公約数で見分け、互除法で1組の解を見つけ、そこからすべての解を一般解として表す流れを学びました。一般解の は、「 を で割った余りはいつも同じ」ということも表しています。この「余りに注目する」見方は、第5章の合同式で本格的に扱います。次の第4章では、ふだん使っている10進法をはなれて、2進法や5進法など、ほかの数の表し方を学びます。
基礎確認問題（全5問）
まずは公式をそのまま使う、ごく簡単な問題で確認しましょう。
問2
方程式 の整数解を1組求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
（例），（ほかに ， など）
自己採点：
記録を読み込み中…
問3
方程式 の整数解をすべて求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
，（ は整数）（ で、 と は互いに素なので は の倍数）
自己採点：
記録を読み込み中…
問4
方程式 の整数解をすべて求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
，（ は整数）（特殊解 ， から ）
自己採点：
記録を読み込み中…
問5
互除法を用いて、方程式 の整数解を1組求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
（例），（， より ，）
自己採点：
記録を読み込み中…
実践問題（全20問）
難易度マークは ★＝基礎、★★＝標準、★★★＝入試レベルです。★から順に取り組みましょう。
問1 ★
方程式 の整数解をすべて求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
，（ は整数）
解説
， とすると なので、これが1組の解です。 と を辺ごとに引くと
と は互いに素なので、 は の倍数です。 とおくと、 より です。よって
です。
自己採点：
記録を読み込み中…
問2 ★
方程式 の整数解をすべて求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
，（ は整数）
解説
， とすると なので、これが1組の解です。辺ごとに引くと
と は互いに素なので、 は の倍数です。 とおくと より です。よって
です。 の係数が負なので、 と は同じ向きに増えます。
自己採点：
記録を読み込み中…
問3 ★
方程式 の整数解をすべて求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
，（ は整数）
解説
と の最大公約数は で、 は の倍数なので解があります。両辺を で割ると
， が1組の解です。辺ごとに引くと で、 と は互いに素なので とおけて、 です。よって
です。割らずに から進めると、「 と は互いに素」とは言えないので、先に最大公約数で割っておくのが大切です。
自己採点：
記録を読み込み中…
問4 ★
(1) 互除法を用いて、方程式 の整数解を1組求めなさい。
(2) 方程式 の整数解をすべて求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
(1)（例）， (2) ，（ は整数）
解説
(1) 互除法を行います。
， として、余りを上から順に表します。
よって で、 が1組の解です（）。
(2) 辺ごとに引くと です。 と は互いに素なので とおけて、 です。よって
です。
自己採点：
記録を読み込み中…
問5 ★
方程式 の整数解をすべて求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
，（ は整数）（， などと表しても同じ）
解説
実践問題 j04 の の両辺を 倍すると、 です。辺ごとに引くと
と は互いに素なので とおけて、 です。一般解は ， です。
を におきかえると、数が小さくなって
です。 のとき で、確かに解になっています。
自己採点：
記録を読み込み中…
問6 ★
方程式 を満たす自然数 ， の組をすべて求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
解説
なので、， が1組の整数解です（自然数ではありませんが、特殊解として使えます）。辺ごとに引くと
と は互いに素なので、 は の倍数です。 とおくと で、， です。
より で 、 より です。 で
です。右辺が一方の係数の倍数のときは、このように片方を にした特殊解がすぐ見つかります。
自己採点：
記録を読み込み中…
問7 ★
1枚 円の切手と1枚 円の切手を、どちらも1枚以上買って、代金の合計をちょうど 円にしたい。それぞれの枚数の組をすべて求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
（ 円切手， 円切手）
解説
円切手を 枚、 円切手を 枚とすると
， が1組の整数解です。辺ごとに引くと で、 と は互いに素なので は の倍数です。 とおくと です。
より で 、 より です。 で 、 で なので、（ 円切手， 円切手）の枚数の組は
です。（確かめ）， です。
自己採点：
記録を読み込み中…
問8 ★
方程式 が整数解をもつような、 以下の自然数 の個数を求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
個
解説
と の最大公約数は です。公式1より、整数解をもつのは が の倍数のときで、そのときに限ります。
以下の の倍数は （ から まで）なので、 です。
たとえば なら、 となっています。
自己採点：
記録を読み込み中…
問9 ★★
で割ると 余り、 で割ると 余る2けたの自然数を、すべて求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
解説
求める数を とすると、整数 ， を用いて と表せます。よって
， が1組の解です。辺ごとに引くと で、 と は互いに素なので とおけます。すると
です。 より なので
です。条件を満たす数は ずつ（ と の最小公倍数ずつ）の間隔で並びます。
自己採点：
記録を読み込み中…
問10 ★★
方程式 の整数解をすべて求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
，（ は整数）
解説
互除法を行います。
， として、余りを上から順に表します。
よって で、， が1組の解です（）。
辺ごとに引くと で、 と は互いに素なので とおけて、 です。よって
です。
自己採点：
記録を読み込み中…
問11 ★★
方程式 を満たす自然数 ， の組をすべて求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
解説
特殊解を探します。 と順に試して、 が で割り切れるものを探すと
で、 のとき です。辺ごとに引くと で、 と は互いに素なので とおけて、 です。一般解は ， です。
より で 、 より で です。 で
です。
を から まで試せば、必ずどこかで割り切れます（ を で割った余りが 通りすべて異なるから。実践問題 j19）。試すのが大変なときは、互除法で の解を作って 倍してもかまいません。
自己採点：
記録を読み込み中…
問12 ★★
分数 を、整数 ， を用いて の形に表す。 が最も小さくなるような ， を求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
，（）
解説
なので、条件は
です。， とすると なので、これが1組の解です。辺ごとに引くと で、 と は互いに素なので とおけて、 です。一般解は
です。 は と ずつの間隔で並ぶので、 が最も小さいのは のときの です。このとき なので
です。（確かめ） です。
自己採点：
記録を読み込み中…
問13 ★★
たこ焼きが7個入りのパックと12個入りのパックで売られている。いくつかのパックを買って、たこ焼きをちょうど 個にしたい。ただし、一方のパックを買わなくてもよい。7個入りと12個入りのパックの数の組をすべて求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
7個入り パック、12個入り パックの1通りだけ
解説
7個入りを パック、12個入りを パックとすると、， は 以上の整数で です。
まず互除法で の解を作ります。
， として
より です。 倍して なので、辺ごとに引くと です。 と は互いに素なので とおけて、 です。
より 、 より なので、 だけです。このとき ， なので、7個入り 、12個入り の1通りです。（確かめ） です。
特殊解が大きな数になっても、条件の不等式でしぼれば正しい答えにたどり着けます。
自己採点：
記録を読み込み中…
問14 ★★
整数 ， が を満たすとき、 の最小値と、そのときの ， を求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
最小値 （，）
解説
， とすると なので、これが1組の解です。辺ごとに引くと で、 とおけて、 です。一般解は ， です。
これは の二次式で、 で最小になる形です。 は整数なので、これに近い と を比べます。
が より小さい、または より大きいと値はさらに大きくなるので、最小値は です。
最初に見つけた解 が最小とは限りません。一般解にしてから調べるのが大切です。
自己採点：
記録を読み込み中…
問15 ★★
座標平面上の直線 上にあり、 座標と 座標がともに正の整数である点の個数を求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
個
解説
求める点の個数は、 を満たす自然数 ， の組の個数です。 なので、， が1組の整数解です。辺ごとに引くと で、 と は互いに素なので は の倍数です。 とおくと です。
より で 、 より なので、 の です。
点は で、直線上に等間隔に並んでいます。
自己採点：
記録を読み込み中…
問16 ★★
整数 ， が を満たすとき、 を で割った余りと、 を で割った余りを、それぞれ求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
を で割った余りは 、 を で割った余りは
解説
， とすると なので、これが1組の解です。辺ごとに引くと で、 とおけて、 です。
， なので、 を で割った余りは 、 を で割った余りは です。
のままでは余りが に見えますが、余りは 以上にそろえるので（第2章 公式1）、 を1つくり出して とします。どの解を選んでも余りは変わりません。
自己採点：
記録を読み込み中…
問17 ★★★
以上の整数 ， を用いて と表せる自然数を考える。
(1) は の形に表せないことを示しなさい。
(2) 以上の自然数は、すべて の形に表せることを示しなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
(1)(2) 解説を参照（(1) を調べる (2) 〜 の5つが表せれば、 を足していける）
解説
(1) を満たす 以上の整数 ， があったとします。 なので は のどれかで、そのとき
となります。どれも の倍数ではないので、 は整数になりません。よって は表せません。（証明終）
(2) まず、連続する5つの数 から が表せることを確かめます。
で表せる数に を足すと、 を 増やすだけなので、やはり表せます。 以上の自然数 は、 を で割った余りを 、商を として （，）と書けます。 は上の5つのどれかなので表せて、そこに を 回足した も表せます。（証明終）
実際に調べると、表せない自然数は の 個です。最大の は で、一般に互いに素な ， では が表せない最大の数になります（厳密定義 定理5）。
自己採点：
記録を読み込み中…
問18 ★★★
ある施設の入場料は、大人1人 円、子ども1人 円、幼児1人 円である。大人・子ども・幼児がそれぞれ1人以上いる 人の団体の入場料の合計が、ちょうど 円であった。大人・子ども・幼児の人数の組をすべて求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
（大人，子ども，幼児）
解説
大人を 人、子どもを 人、幼児を 人とすると、，， は自然数で
です。2つめの式を で割ると で、ここから1つめの式を引いて を消すと
となります。 なので、， が1組の整数解です。辺ごとに引くと で、 と は互いに素なので は の倍数です。 とおくと で
です。， より 、 より で です。 で、（大人，子ども，幼児）の人数の組は
です。（確かめ） なら です。
文字が3つでも、式を1つ使って文字を1つ消せば、ここまでの一次不定方程式に帰着します（小話1の「百鶏問題」と同じ形です）。
自己採点：
記録を読み込み中…
問19 ★★★
， を互いに素な自然数とし、 とする。
(1) 個の数 を で割った余りは、すべて異なることを示しなさい。
(2) (1) を用いて、方程式 が整数解をもつことを、互除法を使わずに示しなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
(1)(2) 解説を参照（(1) 余りが等しい2つの差 が の倍数になり矛盾 (2) 余りが 通りすべて現れるので、余り のものがある）
解説
(1) として、 と を で割った余りが等しかったとします。余りを として ， と書くと、引いて
なので、 は の倍数です。 と は互いに素なので、 の素因数はすべて に含まれ、 は の倍数になります（第1章の厳密定義 定理5(2)）。ところが なので、 は の倍数ではありません。これは矛盾です。よって余りはすべて異なります。（証明終）
(2) で割った余りは の 通りしかありません。(1) より 個の数 の余りはすべて異なるので、 通りの余りがちょうど1回ずつ現れます。とくに、余りが になる （）があります。 とすると
なので、， が の整数解です。（証明終）
たとえば ， なら、 を で割った余りは で、すべて異なります。余り の から、 が得られます。
自己採点：
記録を読み込み中…
問20 ★★★
で割ると 余り、 で割ると 余り、 で割ると 余る自然数について、次の問いに答えなさい。
(1) このような自然数のうち、最小のものを求めなさい。
(2) このような 以下の自然数の個数を求めなさい。
つまずいたときは：
答えを見る答えを閉じる
答え
(1) (2) 個
解説
(1) 条件を2つずつ組み合わせていきます。求める数を とします。
4 と 7 の条件 より です。， が1組の解で、辺ごとに引くと なので とおけます。
9 の条件を加える より です。 とすると で なので、これが1組の解です。辺ごとに引くと で、 と は互いに素なので とおけます。
が自然数となる最小のものは のときで、 です。（確かめ） です。
(2) より なので、 で、 の です。
で、，， はどの2つも互いに素なので、条件を満たす数は ごとにちょうど1つずつ現れます（厳密定義 定理4）。
自己採点：
記録を読み込み中…
数学小話コーナー
百羽のにわとりを百枚の銭で——百鶏問題
中国の数学書『張丘建算経』（5世紀ごろ ※成立年代は諸説あり）に、次のような問題があります。
「おんどりは1羽5銭、めんどりは1羽3銭、ひよこは3羽で1銭。100銭で、ちょうど100羽のにわとりを買いたい。おんどり、めんどり、ひよこをそれぞれ何羽買えばよいか。」
これが「百鶏問題」と呼ばれる有名な問題です。おんどりを 羽、めんどりを 羽、ひよこを 羽とすると
と、文字が3つなのに式は2つしかありません。2つめの式を3倍して1つめの式を引くと、 が消えて
という、この章の一次不定方程式になります。， が1組の解なので、一般解は ， で、ひよこは 羽です。3種類とも1羽以上買うとすると で
の3通りになります。『張丘建算経』にも、この3通りの答えが載っています。答えが1つに決まらない問題に、きちんとすべての答えを挙げている点がみごとです。
中国ではその後、13世紀の秦九韶が『数書九章』（1247年）で「大衍求一術」という方法をまとめました（数と式 第12章の小話で、組立除法の話に登場した人物です）。「ある数を掛けて、別の数で割ると 余るようにする」数を求める手順で、中身は の解を互除法で見つける公式2とほとんど同じです（※手順の細部は解釈に諸説あり）。
豆知識
一次不定方程式のように整数解を求める方程式は、英語で Diophantine equation（ディオファントス方程式）と呼ばれます。3世紀ごろのアレクサンドリアの数学者ディオファントスの『算術』にちなむ名前です（ただし『算術』が扱ったのは、おもに有理数の解でした）。17世紀のフェルマーは、この『算術』の本の余白に「この定理の驚くべき証明を見つけたが、余白が狭すぎて書けない」と書き込みました。これが、350年以上も解かれなかった「フェルマーの最終定理」の始まりです。
3リットルと5リットルで4リットルを量る——水がめパズル
目盛りのない3リットルの容器と5リットルの容器があり、水はいくらでも使えます。ちょうど4リットルの水を量るにはどうすればよいでしょうか。
映画『ダイ・ハード3』（1995年）では、主人公たちが公園の噴水の前でこの問題を出され、時限爆弾を止めるために大急ぎで解く場面があります（映画では単位がガロンです）。答えの1つは次のとおりです。
- 5リットルの容器を満たし、3リットルの容器に注ぐ（5リットルの容器に2リットル残る）。
- 3リットルの容器を空にし、残りの2リットルを移す。
- 5リットルの容器をもう一度満たし、3リットルの容器がいっぱいになるまで注ぐ（3リットルの容器にはあと1リットルしか入らない）。
- 5リットルの容器に、ちょうど4リットルが残る。
この手順では、5リットルの容器を2回満たし、3リットル分を2回捨てています。つまり で、方程式 の解 ， にあたります。別の解 ，（）を使うと、「3リットルの容器で3回くみ、5リットル分を1回捨てる」という別の手順も作れます。容器で水を足したり捨てたりする操作が、そのまま一次不定方程式の ， になっているのです。
日本でも、江戸時代の算術書『塵劫記』（1627年）に、よく似た「油分け算」が載っています。1斗（10升）の油を、7升ますと3升ますだけを使って5升ずつに分ける、という問題です（『塵劫記』は、指数関数・対数関数 第2章の小話の「ねずみ算」や、数列 第1章の小話の「俵杉算」でも登場しました）。
豆知識
容器が6リットルと9リットルだったら、どうがんばっても4リットルは量れません。何回注いでも捨てても、扱う水の量は の形で、いつも の倍数だからです（公式1）。逆に、2つの容器の大きさが互いに素なら、大きいほうの容器の大きさ以下の量は、1リットル単位で何でも量れることが知られています。
2026年は丙午——干支が60通りしかないわけ
今年、2026年の干支は「丙午（ひのえうま）」です。干支は、10種類の十干（甲・乙・丙・丁・戊・己・庚・辛・壬・癸）と、12種類の十二支（子・丑・寅・卯・辰・巳・午・未・申・酉・戌・亥）を、1年ごとに1つずつずらしながら組み合わせたものです。
西暦からは、次のように割り算で干支が分かります。
- 十干：西暦を で割った余りが なら甲、 なら乙、 なら丙、……（ なら庚）
- 十二支：西暦から を引いて で割った余りが なら子、 なら丑、……、 なら午
を で割った余りは で丙、 を で割った余りは で午なので、丙午です。
では、丙午の年はほかにいつあるのでしょうか。西暦 年が丙午になる条件は、整数 ， を用いて
と書けることです。整理すると 、両辺を で割って という一次不定方程式になります。， が1組の解なので、一般解は で、 です。丙午は 年ごとにめぐってきて、前回は1966年でした。60歳を「還暦」と呼ぶのは、生まれた年の干支に還る（戻る）からです。
十干が10種類、十二支が12種類なら、組み合わせは 通りありそうです。ところが干支は60通りしかありません。たとえば「甲丑」という年は決して来ないのです。甲の年を 、丑の年を とおくと、 となりますが、左辺はいつも偶数なので解がありません。 と の最大公約数が なので、公式1により、上の割り算の余りが「十干も十二支も偶数」か「どちらも奇数」の組み合わせしか現れないのです。互いに素でない と の最小公倍数が であることが、干支のひと回りが60年である理由です。
1966年の丙午には、「この年に生まれた女性は気性が激しい」という根拠のない迷信が広まり、この年の出生数は約136万人と、前の年より4分の1ほども減りました。数の組み合わせの周期が、社会に大きな影響を与えた例です。
豆知識
歴史の出来事の名前にも干支が残っています。1868年の「戊辰戦争」、672年の「壬申の乱」は、それぞれ起きた年の干支です。兵庫県の阪神甲子園球場は、甲子の年である1924年に完成したことからこの名前がつきました。甲子は干支の1番目で、 の年、つまり1924年・1984年・2044年……です。
厳密定義（発展）
※ここは発展ページです。本文では、公式1〜3を具体的な数で確かめながら使いました。ここでは、係数が負の場合も含めてそれらを定理として証明し、さらに2つの応用として、割り算の余りの条件を組み合わせる「中国の剰余定理」と、「 以上の整数 ， で と表せない最大の数」を求める定理を扱います。
このページでは、とくに断らないかぎり文字は整数を表します。第1章・第2章の厳密定義で導入した整除の記号 と、第2章 定理4（最大公約数は の形に書ける）を使います。
一次不定方程式と解の存在
定義1：一次不定方程式
， を でない整数、 を整数とする。等式 を満たす整数の組 を求める問題を一次不定方程式といい、そのような組を整数解という。整数解の1つを特殊解、整数解全体を1つの文字 を用いて表したものを一般解という。
と の最大公約数は、第2章 定義1 のとおり と の最大公約数です。また を におきかえれば の符号を変えられるので、係数の符号は整数解の有無には影響しません。
定理1：整数解をもつ条件
， の最大公約数を とする。 が整数解をもつための必要十分条件は、 である。
証明 （必要性）整数解 があるとする。， なので、第1章 定理1(2) より 、すなわち である。
（十分性） とし、 とおく。第2章 定理4 を自然数 ， に使うと、 を満たす整数 ， がある。 が負なら の符号を、 が負なら の符号を変えたものを ， とすると である。両辺を 倍して、 は の整数解である。（証明終）
本文 公式2 の手順は、第2章 定理4 の証明で「余りがすべて の形に書ける」ことを示した道すじを、そのまま計算に移したものです。
一般解
定理2：一般解（係数が互いに素な場合）
と が互いに素で、 が の整数解の1つであるとする。このとき、 が整数解であることと、ある整数 を用いて
と表されることは同値である。さらに、異なる からは異なる解が得られる。
証明 （表されるなら解） である。
（解なら表される） と を辺ごとに引いて
を得る。 なら、 より で、 とすればよい。 のとき、両辺の絶対値をとると で、 は自然数 を割り切る。 と は互いに素なので、第2章 定理5(1)（または第1章 定理5(2)）より 、したがって である。 とおくと で、 より である。
（異なる は異なる解） なら、 より である。（証明終）
一般解の表し方は1通りではありません。特殊解を別のもの に取りかえても、 が にずれるだけで、表している解の集まりは同じです。本文 例題3(1) で を におきかえたのは、この取りかえにあたります。
定理3：一般解（一般の場合）
， の最大公約数を とし、， とおく。 のとき、 の整数解全体は、 の整数解全体と一致する。したがって、特殊解の1つを とすると、一般解は
である。
証明 の両辺を で割ると となり、逆に後者の両辺に を掛けると前者になるので、2つの方程式は同じ整数解をもつ。 と は互いに素なので（第1章 公式6。 と に公約数 があれば が ， の公約数になり、 の最大性に反する）、定理2 を に使えばよい。（証明終）
なのに としてしまうと、 が1つ進むごとに解を 個飛ばしてしまいます。本文で「先に両辺を最大公約数で割る」としたのは、このためです。
中国の剰余定理
本文の実践問題 j09・j20 では、「 で割ると 余り、 で割ると 余る数」を一次不定方程式で求めました。これを一般の形で述べたものが、次の定理です。3〜5世紀ごろの中国の数学書『孫子算経』に「3で割ると2余り、5で割ると3余り、7で割ると2余る数は何か」（答えは ）という問題があることから、中国の剰余定理と呼ばれます（※成立年代は諸説あり）。
定理4：中国の剰余定理
， を互いに素な自然数、， を整数とする。「 が の倍数で、かつ が の倍数」である整数 が存在する。さらに、そのような の1つを とすると、条件を満たす整数全体は
である。とくに、 の範囲に、条件を満たす はちょうど1つある。
証明 （存在）条件は、整数 ， を用いて と書けること、すなわち
が整数解 をもつことである。 と は互いに素なので、定理1 より整数解がある。
（全体の形） と がともに条件を満たすとすると、 は の倍数で、同様に の倍数でもある。 なら の倍数である。 なら、その絶対値は と の公倍数である自然数なので、 と が互いに素であることと第1章 定理5(3) より の倍数であり、 も の倍数である。逆に なら、 は の倍数、 も の倍数なので条件を満たす。
（ちょうど1つ） を で割った余りを とすると、 は条件を満たし である。条件を満たす2つの数の差は の倍数なので、この範囲には しかない。（証明終）
条件が3つ以上でも、どの2つの割る数も互いに素なら、この定理をくり返し使えます。実践問題 j20 は、 と の条件を先に「 で割ると 余る」にまとめ、それと の条件を組み合わせて、 ごとに1つずつ解が現れることを示したものでした。この定理は、第5章の合同式を使うと、より簡潔に書き表せます。
表せない最大の数
小話2の水がめパズルや、実践問題 j17 のように、， を 以上に限ると、 の形に表せない数が出てきます。どこから先はすべて表せるのかを教えてくれるのが、次の定理です。イギリスの数学者シルベスターが1884年に問題として出したことで知られています（※初出には諸説あり）。
定理5：0 以上の整数で表せない最大の数
， を互いに素な自然数とする。
(1) は、 以上の整数 ， を用いて の形に表せない。
(2) より大きい整数は、すべて 以上の整数 ， を用いて の形に表せる。
証明 (1) （，）と表せたとすると
である。 は の倍数で、 と は互いに素なので、第1章 定理5(2) より である。 なので である。同様に である。すると
となって矛盾する。
(2) とする。定理1 より には整数解があり、定理2 より一般解は ， である。 は ずつ変わるので、 をうまく選べば となる解 がとれる。このとき
より 、つまり である。よって は 以上の整数 ， で表せる。（証明終）
， なら で、実践問題 j17 の結果と一致します。， なら で、たとえば「3円切手と5円切手だけでは、7円はちょうど払えないが、8円以上ならいくらでも払える」ということです。表せない自然数の個数は、ちょうど 個であることも知られています（， なら 個）。
こうして、一次不定方程式は「解があるか（定理1）」「すべての解はどう表されるか（定理2・定理3）」がすっかり分かり、その応用として、余りの条件の組み合わせ（定理4）や、 以上の解の有無（定理5）まで導けました。どれも、第2章の互除法から得た「最大公約数は の形に書ける」という1つの性質が土台になっています。
この章の学習が終わったら
学習完了テストを受ける