入試整数入門

120

はじめに

この記事は整数分野をまだ勉強していない人向けの入門記事です。
入試に出る整数にはいくつかパターンがあるのですが、今回はそのうちの重要と思われる二つ「合同式」と「不定方程式」について解説します。

合同式とは

合同式って、学校では習ったり習わなかったりすると思うんですけど、かなり重要な概念ですよね、というか必須です。ここでは合同式を初めて学ぶ人向けに様々な計算規則から応用例まで紹介します。
例えば一週間は7日、一周は360度を1つの周期としてループします。つまり土曜日の次は日曜日に戻ってきて、361度は1度と同じであるとみなします。これを数学的に言えば
「1と361は360で割った余りが等しい」
ということです。このことを数式で次のように表現します。
$$1\equiv 361\pmod{360}$$
このような式を合同式といいます。上式において360にあたる部分を法といいます。$\equiv$ は「合同」とか、「イクイバレント」とか読みます。どうでもいいです。360で割った余りが同じ数はすべて"合同"であるから、
$$-359\equiv1 \equiv 361\equiv 721 \cdots \equiv360k+1\pmod{360}$$
ということです。

いろいろな合同式

$1 \equiv 361\pmod{360}$
$7 \equiv 40\pmod{3}$
$-1000 \equiv 10000\pmod{100}$

で、合同式の何がうれしいの？って話ですよね。でも読み進めれば徐々にそのおいしさに気づくはずです。

合同式の四則演算

単刀直入に言うと、次のことが成り立ちます。

合同式の演算

$a,b$を整数,$c$を正の整数として$a \equiv a',b \equiv b'\pmod{c}$のとき、次のことが成り立つ

$a + b \equiv a'+ b'\pmod{c}$
$a - b \equiv a'- b'\pmod{c}$
$ab \equiv a'b'\pmod{c}$

合同式の計算

$1 \equiv 361,2\equiv362\pmod{360}$であり、実際$361+362=723\equiv3=1+2$である。つまり$1+2\equiv 361+362.$
$5 \equiv 11,3\equiv15\pmod{6}$であり、実際$11\cross15=165\equiv3\equiv15=3\cross5$である。つまり$3\cross5\equiv11\cross15.$
任意の整数$c,n$に対し$c\equiv c$は自明であるから$n\equiv m$の時$cn\equiv cm.$→同じ数を両辺にかけてもよい

これは合同式がおおむね普通の文字式の計算と同様に扱えることを示しています。これは非常にうれしい性質です。例えば、移項のような操作も自由に行うことができます。
上の例のように、法が明らかな場合は$\pmod{〇〇}$を省略してもよいですが、みだりに省略するのはやめましょう。特に慣れていないうちは。
いくつか注意すべき点があります。

$a$が$b$で割り切れて$a \equiv a',b \equiv b'\pmod{c}$が成り立ったからといって$\dfrac{a}{b} \equiv \dfrac{a'}{b'}\pmod{c}$は一般に成り立ちません
例えば、$10\equiv28\pmod{6}$という合同式の両辺を調子に乗って$2$で割ると(上式において$a=10,a'=28,b=b'=2$とした)$5\equiv14\pmod{6}$という嘘が出来上がります。詳しく言えば、割る数と法$c$が互いに素な時は両辺割っても安全です。互いに素とは最大公約数が$1$であることを言います。

要するに、割り算は安易にするな！！

さらに次も陥りやすい罠です。

$a \equiv a'\pmod{c}$が成り立ったからといって$ n^a\equiv n^{a'}\pmod{c}$が成り立つとは限りません。例えば$1\equiv4\pmod3$ですが$2^1\not\equiv2^4\pmod3$です。つまり、合同だからと言って何でもかんでも同じとして扱うと痛い目見るよってこと。

でも$a\equiv b\pmod{c}$のとき$a^n\equiv b^n\pmod{c}$は成り立ちます。確かに、$a\equiv b$の左辺に$a$,右辺に$b$をかけるという操作を$n-1$回続けていけば成り立つな~ということがわかります。これはかなり重要で、次のような例を見てみましょう。

累乗の合同式

$1001\equiv1\pmod{1000}$である。よって$1001^{9999}\equiv1^{9999}=1\pmod{1000}$
$999\equiv -1 \pmod{1000}$である。よって$999^{9999}\equiv(-1)^{9999}\equiv-1\equiv999\pmod{1000}$である。

問.$n\equiv4\pmod7$の時、$n^{50}$を$7$で割った余りを求めよ.

解.$n^{50}\equiv 4^{50}=2^{100}=2\cross2^{99}=2\cross8^{33}\equiv2\pmod7$

このように超でかい数の余りも合同式を用いて華麗に求めることができてしまいます。ポイントは$1$や$-1$のように累乗しても値が大きくならずに扱いやすい形を見つける、もしくは作るということです。

練習問題

$2000^{2000}$を$12$で割った余りを求めよ(Focus Goldからの引用)
$\displaystyle\sum_{k=1}^{10000}{(2^k+3^k)}$を$8$で割った余りを求めよ

答え(1):4 (2):6

合同式の応用

これまでで、合同式のいい点をいくつか見てきました。最後に有名問題を通してさらなる合同式の秘めたすばらしさを紹介します。

$a^2+b^2=c^2$のとき、$a$または$b$は$3$の倍数であることを示せ.(有名問題)

解答.
合同式の法は$3$とする。
$a,b$がいずれも$3$の倍数ではないと仮定しよう.この時$a\equiv\pm1,b\equiv\pm1$であるから$a^2\equiv b^2 \equiv1$である。よって$c^2\equiv2$となるが$c$が$3$の倍数でなければ$c^2\equiv1$であり,$c$が$3$の倍数であれば$c^2\equiv0$となるため,$c^2\equiv2$となることはなく矛盾である。したがって$a$または$b$は$3$の倍数である。

このように,$2$乗をある数で割った余りに着目する平方剰余の考え方は入試に頻出です。東大でも出ました。例えば,$a^2$を$3$で割った余りは$0$か$1$だから,$n\equiv2$のとき$n$は平方数ではないな。というようなことがわかります。(もし$n$が平方数で$n=m^2$と表せるなら$m^2\equiv2$となり矛盾である。)平方数ときたら$3,8$あたりで割った余りを一度考えてみましょう。それぞれ次のようになります。
$a^2\equiv0,1\pmod3$
$a^2\equiv0,1,4\pmod5$
$a^2\equiv0,1,4\pmod8$

練習問題

$x^4-5y^4=2$を満たす整数の組$(x,y)$は存在しないことを示せ.(岩手大)

一次不定方程式

不定方程式とは何でしょうか。今まで扱ってきた方程式は例えば$2x+1=3$のように,解が一つに定まっていました。
それに比べて不定方程式は$2x+3y=5$のように解(の組)が一つに定まらないような方程式のことを言います。
この方程式の実数解は明らかに無限にあり、そんなものを求めよと言われても何の面白みもありません。(答えるとしたら$t$を任意定数として$(t,\dfrac{5-2t}{3})$といったところでしょうか。)
よって、この一次不定方程式の整数解を求める問題を考えます。
上の式は一次の不定方程式なので特に一次不定方程式と呼びます。ここでは整数解を単に解ということにします。
さて、この一次不定方程式はどのように解けばよいのでしょうか。まず見た瞬間に$(1,1)$が条件を満たすことがわかるでしょう。
このような解を特殊解といいます。しかし解は$(1,1)$に限るのでしょうか?
全くそんなことはありません。実は、整数解に限定したとしても探せばいくらでも解は見つかります。
結論から言うと$k$を整数として$(-3k+1,2k+1)$の形で表せる数の組はすべて解になります。ここで$k=0$としたのが$(1,1)$です。
このようにすべての解を網羅する解を一般解と呼びます。そもそも一次不定方程式を"解く"とはこの一般解を求めることを指します。
ではこの一般解はどのように求めるのでしょうか?

一次不定方程式の解き方

引き続き先ほどの一次不定方程式$2x+3y=5$について考えます。一次不定方程式の解き方にはいくつかのプロセスがあります。下の通りです。

特殊解を見つける
元の方程式と辺々引く
任意定数$k$を用いて解を表す

このプロセスに従って実際に一般解を求めてみましょう。

i.特殊解を見つける
先ほど見た通り、$(1,1)$が特殊解(の一つ)でした。別に、$(-2,3)$などでもよいですが、$(1,1)$がもっとも単純でしょう。

ii.元の方程式と辺々引く
$2\cdot x+3\cdot y=5$
$2\cdot1+3\cdot1=5$
$2(x-1)+3(y-1)=0$
これを移項します
$2(x-1)=-3(y-1)\cdots$①

iii.任意定数$k$を用いて解を表す
①において左辺は$2$の倍数であり、右辺において$-3$は$2$と互いに素であるので、$y-1$が$2$の倍数である必要があります。つまり$y-1=2k$と表せます。よって$y=2k+1$となります。この時右辺は$-6k$となり,$x-1=-3k$から$x=-3k+1$となります。よって一般解$(-3k+1,2k+1)$を得る。

※解の表し方は一通りではない。例えば、$(-3k-2,2k+3)$と書いても$(-3k+4,2k-1)$と書いても正解になります。

これで一般解を導出することができました。赤文字になっている部分が重要です。左辺が偶数なので右辺も偶数である必要があるけれども$-3$は偶奇に関与しないので$y-1$が偶数でなければならないということです。

とにかく解を求めるプロセスさえ暗記してしまえば難しいことはないでしょう。

$3$で割ると$2$あまり,$5$で割ると$4$あまるような数を求めよ($k$を用いて表せ)

解答.
条件を満たす整数を$n$とおくと、$n$は$3$で割ると$2$余ることから$n=3x+2$とおける。($x$は整数)また、$n$は$5$で割ると$4$余ることから$n=5y+4$($y$は整数)とおける。よって$3x+2=5y+4\Leftrightarrow3x-5y=2$となり、一次不定方程式に帰着しました。

i.特殊解を見つける
すぐに$(x,y)=(-1,-1)$が解であるとわかります。

ii.元の方程式と辺々引く
$3\cdot x-5\cdot y=2$
$3\cdot(-1)-5\cdot(-1)=2$
$3(x+1)-5(y+1)=0$
$3(x+1)=5(y+1)$

iii.任意定数$k$を用いて解を表す
左辺は$3$の倍数で,$3,5$は互いに素であるから$y+1$が$3$の倍数である必要があります。よって$y+1=3k$となり$y=3k-1$が従う。よって$n=5y+4$であったからこれを代入して$n=5(3k-1)+4=\mathbf{15k-1}$が求める答えである.