\begin{align*}
&2x^2+3xy-2y^2-3x+4y-5=0 \land x,y\in\mathbb{Z}\\
\Longleftrightarrow~&x=\frac{-3(y-1)\pm \sqrt{25y^2-50y+49}}{4} \land x,y\in\mathbb{Z}\\
\Longleftrightarrow~&x=\frac{-3(y-1)\pm \sqrt{25y^2-50y+49}}{4} \land x,y\in\mathbb{Z} \\
&\land \exists k \in \{0,1,2,\cdots\}[25y^2-50y+49=k^2]\\
\Longleftrightarrow~&x=\frac{-3(y-1)\pm \sqrt{25y^2-50y+49}}{4} \land x,y\in\mathbb{Z} \\
&\land \exists k \in \{0,1,2,\cdots\}[(5y-k-5)(5y+k-5)=-24]\\
\Longleftrightarrow~&x=\frac{-3(y-1)\pm \sqrt{25y^2-50y+49}}{4} \land x,y\in\mathbb{Z} \\
&\land \exists k \in \{0,1,2,\cdots\}\left[\begin{cases}5y-k-5=-2\\5y+k-5=12 \end{cases} \lor \begin{cases}5y-k-5=-4\\5y+k-5=6\end{cases}\right.\\
&\lor \left. \begin{cases}5y-k-5=-6\\5y+k-5=4\end{cases} \lor \begin{cases}5y-k-5=-12\\5y+k-5=2\end{cases} \right]\\
\Longleftrightarrow~&x=\frac{-3(y-1)\pm \sqrt{25y^2-50y+49}}{4} \land x,y\in\mathbb{Z} \\
&\land \exists k \left[\begin{cases}5y-k-5=-2\\5y+k-5=12\\ k\in \{0,1,2,\cdots\}\end{cases} \lor \begin{cases}5y-k-5=-4\\5y+k-5=6 \\ k\in \{0,1,2,\cdots\}\end{cases}\right.\\
&\lor \left. \begin{cases}5y-k-5=-6\\5y+k-5=4 \\ k\in \{0,1,2,\cdots\}\end{cases} \lor \begin{cases}5y-k-5=-12\\5y+k-5=2 \\ k\in \{0,1,2,\cdots\}\end{cases} \right]\\
\Longleftrightarrow~&x=\frac{-3(y-1)\pm \sqrt{25y^2-50y+49}}{4} \land x,y\in\mathbb{Z} \\
&\land \exists k \left[\begin{cases}y=2\\k=7\\ k\in \{0,1,2,\cdots\}\end{cases} \lor \begin{cases}y=\frac{6}{5}\\k=5 \\ k\in \{0,1,2,\cdots\}\end{cases}\right.\\
&\lor \left. \begin{cases}y=\frac{4}{5}\\k=5 \\ k\in \{0,1,2,\cdots\}\end{cases} \lor \begin{cases}y=0\\k=7 \\ k\in \{0,1,2,\cdots\}\end{cases} \right]\\
\Longleftrightarrow~&x=\frac{-3(y-1)\pm \sqrt{25y^2-50y+49}}{4} \land x\in\mathbb{Z} \\
&\land \exists k \left[\begin{cases}y=2\\k=7\\ k\in \{0,1,2,\cdots\}\\y\in\mathbb{Z}\end{cases} \lor \begin{cases}y=\frac{6}{5}\\k=5 \\ k\in \{0,1,2,\cdots\}\\y\in\mathbb{Z}\end{cases}\right.\\
&\lor \left. \begin{cases}y=\frac{4}{5}\\k=5 \\ k\in \{0,1,2,\cdots\}\\y\in\mathbb{Z}\end{cases} \lor \begin{cases}y=0\\k=7 \\ k\in \{0,1,2,\cdots\}\\y\in\mathbb{Z}\end{cases} \right]\\
\Longleftrightarrow~&x=\frac{-3(y-1)\pm \sqrt{25y^2-50y+49}}{4} \land x\in\mathbb{Z} \\
&\land \exists k \left[\begin{cases}y=2\\k=7\\ k\in \{0,1,2,\cdots\}\\y\in\mathbb{Z}\end{cases} \lor \begin{cases}y=0\\k=7 \\ k\in \{0,1,2,\cdots\}\\y\in\mathbb{Z}\end{cases} \right]\\
\Longleftrightarrow~&x=\frac{-3(y-1)\pm \sqrt{25y^2-50y+49}}{4} \land x\in\mathbb{Z} \\
&\land \left( \exists k \begin{cases}y=2\\k=7\\ k\in \{0,1,2,\cdots\}\\y\in\mathbb{Z}\end{cases} \lor \exists k\begin{cases}y=0\\k=7 \\ k\in \{0,1,2,\cdots\}\\y\in\mathbb{Z}\end{cases} \right)\\
\Longleftrightarrow~&\left( x=\frac{-3(y-1)\pm \sqrt{25y^2-50y+49}}{4} \land x\in\mathbb{Z} \land \exists k \begin{cases}y=2\\k=7\\ k\in \{0,1,2,\cdots\}\\y\in\mathbb{Z}\end{cases}\right)\\
&\lor \left( x=\frac{-3(y-1)\pm \sqrt{25y^2-50y+49}}{4} \land x\in\mathbb{Z} \land \exists k\begin{cases}y=0\\k=7 \\ k\in \{0,1,2,\cdots\}\\y\in\mathbb{Z}\end{cases} \right)\\
\Longleftrightarrow~&\exists k \begin{cases}y=2\\k=7\\ k\in \{0,1,2,\cdots\}\\x,y\in\mathbb{Z}\\x=\frac{-3(y-1)\pm \sqrt{25y^2-50y+49}}{4}\end{cases} \lor \exists k\begin{cases}y=0\\k=7 \\ k\in \{0,1,2,\cdots\}\\x,y\in\mathbb{Z}\\x=\frac{-3(y-1)\pm \sqrt{25y^2-50y+49}}{4}\end{cases}\\
\Longleftrightarrow~&\exists k \begin{cases}y=2\\k=7\\ k\in \{0,1,2,\cdots\}\\x,y\in\mathbb{Z}\\x=\frac{-3\pm 7}{4}\end{cases} \lor \exists k\begin{cases}y=0\\k=7 \\ k\in \{0,1,2,\cdots\}\\x,y\in\mathbb{Z}\\x=\frac{3 \pm 7}{4}\end{cases}\\
\Longleftrightarrow~&\exists k \begin{cases}y=2\\k=7\\ k\in \{0,1,2,\cdots\}\\x,y\in\mathbb{Z}\\x=1\end{cases} \lor \exists k\begin{cases}y=0\\k=7 \\ k\in \{0,1,2,\cdots\}\\x,y\in\mathbb{Z}\\x=-1\end{cases}\\
\Longleftrightarrow~&\left(\begin{cases}(x,y)=(1,2)\\x,y\in \mathbb{Z}\end{cases} \land \exists k \begin{cases}k=7\\ k\in \{0,1,2,\cdots\}\end{cases}\right) \\
&\lor \left(\begin{cases} (x,y)=(-1,0)\\\\x,y\in \mathbb{Z}\end{cases} \land \exists k\begin{cases}k=7 \\ k\in \{0,1,2,\cdots\}\end{cases}\right)\\
\Longleftrightarrow~&\begin{cases}(x,y)=(1,2)\\x,y\in \mathbb{Z}\end{cases} \lor \begin{cases} (x,y)=(-1,0)\\x,y\in \mathbb{Z}\end{cases}\\
\Longleftrightarrow~&(x,y)=(1,2) \lor (x,y)=(-1,0)
\end{align*}
2次の不定方程式(つづき1)
次の方程式を満たす整数\(x,y\)の値を求めよ.
- \(2x^2+3xy-2y^2-3x+4y-5=0\)
- \(x^2-4xy+5y^2+2x-5y-1=0\)
前回記事(上の問題)の1. \[2x^2+3xy-2y^2-3x+4y-5=0\]を因数分解せずに解くとどうなるかを見てみます。前と同様,
\begin{align*}
&2x^2+3xy-2y^2-3x+4y-5=0\\
\Longleftrightarrow~&x=\frac{-3(y-1)\pm \sqrt{25y^2-50y+49}}{4}
\end{align*}と変形し,ここから必要条件として\[25y^2-50y+49\geq 0\]が得られますが,しかしこれは何の旨味もないものです。なぜならこの式を満たす\(y\in \mathbb{Z}\)は無数にあり,\(y\)が絞れないからです。そこで必要条件として別のものをとり出してみます。
別解
\begin{align*}
&2x^2+3xy-2y^2-3x+4y-5=0\\
\Longleftrightarrow~&x=\frac{-3(y-1)\pm \sqrt{25y^2-50y+49}}{4}
\end{align*}\(x\)は整数であるから\[25y^2-50y+49=k^2\quad(k=0,1,2,\cdots)\]と表せることが必要.ここで
\begin{align*}
&25y^2-50y+49=k^2\\
\Longleftrightarrow~&25(y^2-2y+1-1)-k^2+49=0\\
\Longleftrightarrow~&25(y-1)^2-k^2=-24\\
\Longleftrightarrow~&(5(y-1)-k)(5(y-1)+k)=-24\\
\Longleftrightarrow~&(5y-k-5)(5y+k-5)=-24(=-2^3\times 3)
\end{align*}
また,\((5y-k-5)+(5y+k-5)=2(5y-3)(=\text{偶数})\)であることから\(5y-k-5\)と\(5y+k-5\)の偶奇は一致すること,そして\(5y-k-5<5y+k-5\)であることから,\((5y-k-5,5y+k-5)\)の組み合わせは\[(-2^1,2^2\cdot 3),(-2^2,2^1\cdot 3),(-2^1\cdot 3,2^2),(-2^2\cdot 3,2^1)\]の\(4\)通りであることが分かる.これより\(y=2,\frac{6}{5},\frac{4}{5},0\)が得られ,\(y\)は整数だから\(y=0,2\)で\(x=-1,1\).したがって求める答えは\((x,y)=(-1,0),(1,2)\)である.
別解終
途中,必要条件なのに逆の考察をしていないのはやはり同値だからです。論理式で記述すると(つづく)
2次の不定方程式
次の方程式を満たす整数\(x,y\)の値を求めよ.
- \(2x^2+3xy-2y^2-3x+4y-5=0\)
- \(x^2-4xy+5y^2+2x-5y-1=0\)
1.
整数問題の大まかなタイプとしては,
因数分解,範囲を絞ってしらみつぶし,合同式の利用(余りで分類)
というのは有名ですが,このうち一つ目の因数分解を狙うというのは自然な発想かと思います。
(因数分解の方針その1)
\begin{align*}
&2x^2+3xy-2y^2-3x+4y-5=0\\
\Longleftrightarrow~&2x^2+3(y-1)x-2y^2+4y-5=0\\
\Longleftrightarrow~&2x^2+3(y-1)x-2(y^2-2y+1-1)-5=0\\
\Longleftrightarrow~&2x^2+3(y-1)x-2(y-1)^2-3=0\\
\Longleftrightarrow~&(2x-y+1)(x+2y-2)=3
\end{align*}
3行目の変形がちょっと苦しい…?^^;
(因数分解の方針その2)
\begin{align*}
&2x^2+3xy-2y^2-3x+4y-5=0\\
\Longleftrightarrow~&2x^2+3(y-1)x-2y^2+4y-5=0\\
\Longleftrightarrow~&2\left(x^2+\frac{3(y-1)}{2}x+\frac{9(y-1)^2}{16}-\frac{9(y-1)^2}{16}\right)-2y^2+4y-5=0\\
\Longleftrightarrow~&2\left(x+\frac{3(y-1)}{4}\right)^2-\frac{9(y-1)^2}{8}-2y^2+4y-5=0\\
\Longleftrightarrow~&(4x+3(y-1))^2-9(y-1)^2-16y^2+32y-40=0\\
\Longleftrightarrow~&(4x+3(y-1))^2-25y^2+50y-49=0\\
\Longleftrightarrow~&(4x+3(y-1))^2-25(y^2-2y+1-1)-49=0\\
\Longleftrightarrow~&(4x+3(y-1))^2-25(y-1)^2=24\\
\Longleftrightarrow~&(4x-2y+2)(4x+8y-8)=24\\
\Longleftrightarrow~&(2x-y+1)(x+2y-2)=3
\end{align*}平方完成で強引に。
(因数分解の方針その3)
\(2x^2+3xy-2y^2=(2x-y)(x+2y)\)に着目し,\((2x-y+a)(x+2y+b)\)という式の展開式を考えます。すると\[(2x-y+a)(x+2y+b)=2x^2+3xy-2y^2+Ax+By+C\]という与式の形が現れますから,\(A=-3,B=4\)を解いて,\(a,b\)を求めます(これを\(a_0,b_0\)とします。これにより\(C=C_0\)も求まる):\[(2x-y+a_0)(x+2y+b_0)=2x^2+3xy-2y^2-3x+4y+C_0\]与式より\(2x^2+3xy-2y^2-3x+4y=5\)でしたから
\begin{align*}
&(2x-y+a_0)(x+2y+b_0)=2x^2+3xy-2y^2-3x+4y+C_0\\
\Longleftrightarrow&~(2x-y+a_0)(x+2y+b_0)=5+C_0
\end{align*}を得ます。以上を実際行うと,
\[(2x-y+1)(x+2y-2)=2x^2+3xy-2y^2-3x+4y-2=5-2=3\]となります。
…ともあれ因数分解できました。あとは右辺の因数の組み合わせが\((1,3),(-1,-3),(3,1),(-3,-1)\)のみであることから\((x,y)=(1,2),(-1,0)\)を得ます。
2.
これも因数分解…と思いきや,1.のようにうまく因数分解できない。お手上げか…?
そこで姿勢を変えて論理で攻めてみます。
解答
\begin{align*}
&x^2-4xy+5y^2+2x-5y-1=0\\
\Longleftrightarrow~&x^2-2(2y-1)x+5y^2-5y-1=0\\
\Longleftrightarrow~&x=(2y-1)\pm\sqrt{-y^2+y+2}
\end{align*}これが整数解をもつならば,\(-y^2+y+2\geq 0\)であることが必要.
\begin{align*}
&-y^2+y+2\geq 0\\
\Longleftrightarrow~&y^2-y-2\leq 0\\
\Longleftrightarrow~&(y-2)(y+1)\leq 0\\
\Longleftrightarrow~&-1 \leq y\leq 2
\end{align*}
\(y\)は整数であるから,\(y=-1,0,1,2\)
\(y=-1\)のとき\(x=-3\),
\(y=0\)のとき\(x=-1\pm \sqrt{2}\),
\(y=1\)のとき\(x=1\pm \sqrt{2}\),
\(y=2\)のとき\(x=3\),
ゆえに\((x,y)=(-1,-3),(2,3)\)が求めるものである.
解答終
必要条件なのに逆の考察をしていないのは同値だからです。論理式で記述すると
\begin{align*}
&x,y\in \mathbb{Z},x^2-4xy+5y^2+2x-5y-1=0\\
\Longleftrightarrow~&x,y\in \mathbb{Z} \land x=(2y-1)\pm\sqrt{-y^2+y+2}\\
\Longleftrightarrow~& x,y\in \mathbb{Z} \land x=(2y-1)\pm\sqrt{-y^2+y+2} \land -y^2+y+2\geq 0\\
\Longleftrightarrow~& x,y\in \mathbb{Z} \land x=(2y-1)\pm\sqrt{-y^2+y+2} \land -1\leq y \leq 2\\
\Longleftrightarrow~& x,y\in \mathbb{Z} \land x=(2y-1)\pm\sqrt{-y^2+y+2}\\
&\land (y=-1 \lor y=0 \lor y=1 \lor y=2)\\
\Longleftrightarrow~& \left(x,y\in \mathbb{Z} \land x=(2y-1)\pm\sqrt{-y^2+y+2} \land y=-1\right)\\
\lor & \left(x,y\in \mathbb{Z} \land x=(2y-1)\pm\sqrt{-y^2+y+2} \land y=0\right)\\
\lor & \left(x,y\in \mathbb{Z} \land x=(2y-1)\pm\sqrt{-y^2+y+2} \land y=1\right)\\
\lor & \left(x,y\in \mathbb{Z} \land x=(2y-1)\pm\sqrt{-y^2+y+2} \land y=2\right)\\
\Longleftrightarrow~& (x,y\in \mathbb{Z} \land x=-3 \land y=-1)\\
\lor & (x,y\in \mathbb{Z} \land x=-1\pm \sqrt{2} \land y=0)\\
\lor & (x,y\in \mathbb{Z} \land x=1\pm\sqrt{2} \land y=1)\\
\lor & (x,y\in \mathbb{Z} \land x=3 \land y=2)\\
\Longleftrightarrow~&(x,y\in \mathbb{Z} \land x=-3 \land y=-1)\lor (x,y\in \mathbb{Z} \land x=3 \land y=2)\\
\Longleftrightarrow~&x,y\in \mathbb{Z} \land (( x=-3 \land y=-1)\lor (x=3 \land y=2))\\
\Longleftrightarrow~&( x=-3 \land y=-1)\lor (x=3 \land y=2)
\end{align*}ということをしています。ちなみに,\(1.,2.\)それぞれを図示すると\(1.\)は双曲線,\(2.\)は楕円になります。
実験する
次の\(2\)つの条件\(\mathrm{(i),(ii)}\)をみたす自然数\(n\)について考える.
\(\mathrm{(i)}~\)\(n\)は素数ではない.
\(\mathrm{(ii)}~\)\(l,m\)を\(1\)でも\(n\)でもない\(n\)の正の約数とすると,必ず\[|l-m|\leq 2\]である.このとき,次の問いに答えよ.
-
- \(n\)が偶数のとき,\(\mathrm{(i),(ii)}\)をみたす\(n\)をすべて求めよ.
- \(n\)が\(7\)の倍数のとき,\(\mathrm{(i),(ii)}\)をみたす\(n\)をすべて求めよ.
- \(2\leq n \leq 1000\)の範囲で,\(\mathrm{(i),(ii)}\)をみたす\(n\)をすべて求めよ.
(大阪大)
うーんわからない/(^o^)\
なんかよくわからないので,実験してみます。
(考え方)
\(\textbf{1.}\)
偶数\(2,4,6,8,\cdots\)を順に調べてみます。
するとどうやら,\(n\)が\(10\)以降だと適するものが現れないのでは?と予想できます。そこで,「\(n\geq 10\)ならば\(n\)は\(\mathrm{(i),(ii)}\)を満たさない」という命題の証明を試みます。実際,\(n=2k~(k\geq 5)\)とおくと,\(2\)と\(k\)は\(n(=2k)\)の\(1\)でも\(n\)でもない正の約数ですが,\[|k-2|=k-2\geq 5-2 =3\]となり\((\mathrm{ii})\)を満たしません。
これで\(1.\)の答えは\(4,6,8\)のみであることが分かりました。
\(\textbf{2.}\)
これも\(1.\)と同様に考えてみます。ただし\(n\)が偶数の場合は\(1.\)ですでに調べているので,これを除いて調べていきます:
すると\(n\)が\(63\)以降だと適するものが現れないのでは?と予想できます。そこで「\(n\geq 63\)ならば\(n\)は\(\mathrm{(i),(ii)}\)を満たさない」という命題の証明を試みると:
\(n=7k~(k\geq 9)\)とおく.\(k=9\)とき,\(n=63\)より正の約数は\(1,3,7,9,21,63\)だから\((\mathrm{ii})\)を満たさない.\(k \geq 11\)のとき,\(7\)と\(k\)は\(n(=7k)\)の\(1\)でも\(n\)でもない正の約数だが,\[|k-2|=k-2\geq 11-2 =9\]となり\((\mathrm{ii})\)を満たさない.
これで\(2.\)の答えは\(35\)と\(49\)のみであることが分かりました。
\(\textbf{3}.\)
上と同じように考えれば,\(n\)が\(3\)の倍数のとき,\(5\)の倍数のときも同じように\(\mathrm{(i),(ii)}\)を満たす\(n\)が簡単に見つかる気がします。もしそうであれば,結局\(2,3,5,7\)の倍数についてはすべて調べ上げたことになるので,調べるべき残りの\(n\)は(\(\mathrm{(i)}\)より\(n\)は素数でないことに注意すれば)\(11\)以上の素因数からなる合成数のみ調べればよいことが分かります(エラトステネスのふるい)。また,その合成数の因数の個数に着目すれば,因数の個数が\(1\)個のとき素数になるから\(\mathrm{(i)}\)を満たさず,因数の個数が\(3\)個以上のときは最小でも\(11^{3}=1331\)となり\(1000\)を超えてしまうことから,(素)因数の個数は\(2\)個であることが分かります。さらに,\(37 \times 37 =1369>1000\)より,\(37\)以降の素数については考える必要はありません。以上の考察から以下のように結論できます:
\(n\)が\(3\)の倍数の場合
\(2,7\)の倍数のときはすでに調べてあり,また\(5\)の倍数の場合はこのあと調べるのでこれらを除いて調べると
求める\(n\)は\(9\)のみであることが分かる(証明は上と同様なので割愛).
\(n\)が\(5\)の倍数の場合
求める\(n\)は\(15\)と\(25\)のみであることが分かる(証明割愛).
あとは素因数が\(11\)以上で\(31\)以下であり,かつその個数が\(2\)個である合成数のみを調べればよい.
するとそれは(\(\mathrm{(ii)}\)に注意して)\[11^2,13^2,17^2,19^2,23^2,29^2,31^2,11\times13,17\times19,29\times 31\]すなわち\[121,169,289,361,529,841,961,143,323,899\]のみであることがわかる.以上により求める\(n\)は\[4,6,8,9,15,25,35,49,121,143,169,289,323,361,529,841,899,961\]となる.
(考え方終わり)
既知の解法にはまらないとき,あるいは既知の解法に帰着しないとき(=何をすればいいのか見通しが立たないとき),「とりあえず実験してみて,予想し,それを証明する」という姿勢はしばしば有効な気がします。(少なくとも泥臭く手を動かすだけで\(2.\)までは答えを導ける!)
合同式の応用
- \(10^{10}\)を\(2020\)で割った余りを求めよ。
- \(100\)桁の正の整数で各位の数の和が\(2\)となるもののうち,\(2020\)で割り切れるものの個数を求めよ。
(一橋大)
解答
\(2020\)を法として考える.以下,\(\mod 2020\)を省略して記述する.
\(10000\equiv10000+2020\cdot(-5)\equiv-100\)であるから,
\begin{align*}
10^{10}\equiv&10^2\cdot(10^4)^2\\
\equiv &10^2\cdot(-100)^2\\
\equiv &10^2\cdot10000\\
\equiv &10^2\cdot(-100)\\
\equiv &-10000\\
\equiv &-(-100)\\
\equiv &100
\end{align*}
ゆえに\(10^{10}\equiv100\)(\(1.\)の答え)
\(100\)桁の正の整数で各位の数の和が\(2\)であるような数は
\begin{align*}
\mathrm{(i)}\quad &2\underbrace{0\cdots0}_{99\text{個}}=2\times10^{99}\\
\mathrm{(ii)}\quad &1\underbrace{0\cdots01\overbrace{0\cdots0}^{k\text{個}}}_{99\text{個}}=10^{99}+10^k\quad(0\leq k \leq 98)
\end{align*}のいずれかである.
\(\mathrm{(i)}\)のとき
\(1.\)により\(10^{10}\equiv10^2\)であることに注意して,
\begin{align*}
2\times10^{99}\equiv&2\cdot10^{9}\cdot(10^{10})^9\\
\equiv&2\cdot10^{9}\cdot(10^{2})^9\\
\equiv&2\cdot 10^{27}\\
\equiv&2\cdot(10^{10})^2\cdot10^7\\
\equiv&2\cdot(10^{2})^2\cdot10^7\\
\equiv&2\cdot10^{11}\\
\equiv&2\cdot10^{10}\cdot10\\
\equiv&2\cdot10^{2}\cdot10\\
\equiv&2000\\
\end{align*}ゆえにこの数は\(2020\)で割り切れない.
\(\mathrm{(ii)}\)のとき
\(10^{99}+10^{k}\equiv 1000 + 10^{k}\)より(なぜならば\(\mathrm{(i)}\)の途中過程により\(10^{99}\equiv1000\)),\(1000+10^k\equiv 0(\Leftrightarrow 10^{k}\equiv -1000)\)を満たす\(k~(0\leq k \leq 98)\)の個数を調べればよい.\(k\)の値は高々\(99\)個なので,実際に調べてみると(やる気),
\(1,10\)から始まり,\(100,1000,-100,-1000\)と繰り返すことがわかる.したがって,\(99=2+4\times 24+1\)により求める個数は\(24\)個とわかる.(\(2.\)の答え)
解答終
必要条件を追う
(中央大)
示すべきは必要条件であること,つまり十分性(逆が言えるか?)を考える必要がないことに注意します。これは細かいことを考えず手元にある道具(仮定)を好き勝手にいじり倒して結論が言えればその時点で証明終わりということなので気楽です:\[f(n),f(n+1),f(n+2)\in\mathbb{Z}\overset{\text{ひつよう!}}{\Longrightarrow} a_0,a_1,a_2 \in\mathbb{Z}\]
とりあえず,\(f(n)\)と\(f(n+1)\)の\(n\)と\(n+1\)は連番なので,差をとってみたらどうか?と思いつきます。(邪魔者がもろもろ消えそうだから)\begin{align*}
&~f(n+1)-f(n)\in \mathbb{Z}\\
\Longleftrightarrow&~\left(a_0+a_1(n+1)+\frac{a_2}{2}(n+1)n\right)\\
&~-\left(a_0+a_1n+\frac{a_2}{2}n(n-1)\right)\in \mathbb{Z}\\
\Longleftrightarrow&~a_1+a_2n \in \mathbb{Z}\tag{1}
\end{align*}なんかうまくいきそうなので,\(f(n+2)-f(n+1)\)も同様に計算すると,\[f(n+2)-f(n+1)\in \mathbb{Z}\Longleftrightarrow a_1+a_2n+a_2 \in \mathbb{Z}\tag{2}\]が得られます。\((1)\)と\((2)\)において\(a_1+a_2n\)が共通していることに着目して\(a_2\)が整数であることがわかり,またこれと\((1)\)により芋づるで\(a_1\)が整数であることが言えます。残りは\(a_0\)ですが,これは\(f(n)=a_0+a_1+\frac{a_2}{2}n(n-1)\in\mathbb{Z}\)であること,すでに示したように\(a_1,a_2\in \mathbb{Z}\)であること,そして\(n(n-1)\)は連続数だから偶数したがって\(\frac{a_2}{2}n(n-1)\in\mathbb{Z}\)であることからいうことができます。(証明終)
とりあえず必要性を追うという方針で証明してみましたが,こうしてみると次のように同値変形できることに気づきます:
証明
\begin{align*}
&~f(n),f(n+1),f(n+2)\in \mathbb{Z}\\
\overset{(\ast)}{\Longleftrightarrow}&~f(n+1)-f(n)\in\mathbb{Z} ,f(n+2)-f(n+1)\in\mathbb{Z},f(n)\in\mathbb{Z}\\
\Longleftrightarrow&~a_1+a_2n \in \mathbb{Z},a_1+a_2n+a_2\in\mathbb{Z},a_0+a_1+\frac{a_2}{2}n(n-1)\in\mathbb{Z}\\
\Longleftrightarrow&~a_1+a_2n \in \mathbb{Z},a_2\in\mathbb{Z},a_0+a_1+\frac{a_2}{2}n(n-1)\in\mathbb{Z}\\
\Longleftrightarrow&~a_1\in \mathbb{Z},a_2\in\mathbb{Z},a_0+a_1+\frac{a_2}{2}n(n-1)\in\mathbb{Z}\\
\Longleftrightarrow&~a_1\in \mathbb{Z},a_2\in\mathbb{Z},a_0\in\mathbb{Z}
\end{align*}
証明終
\((\ast)\)において,\begin{align*}
&~f(n),f(n+1),f(n+2)\in \mathbb{Z}\\
\Longrightarrow&~f(n+1)-f(n)\in\mathbb{Z} ,f(n+2)-f(n+1)\in\mathbb{Z}
\end{align*}ですが,\(f(n)\in\mathbb{Z}\)を加えることで\(\Leftarrow\)も言え,上のように同値になるというカンジです。
三角形の成立条件
\begin{align*}
&|b-c| < a < b+c\\
\Longleftrightarrow~& |b-c| < a \land a < b+c\\
\Longleftrightarrow~& -a < b-c < a \land a < b+c\\
\Longleftrightarrow~& -a < b-c \land b-c < a \land a < b+c\\
\Longleftrightarrow~& c < a+b \land b < a+c \land a < b+c
\end{align*}
なのでどっち使ってもOKです。
フェルマーの小定理
証明
\[1a,~2a,~3a,~\cdots,(p-1)a\]を考える.これらを\(p\)で割った余りはすべて異なることを以下に示す.\(p\)で割って余りが等しくなるような\(2\)数が存在すると仮定し,それらを\(ia,ja~(1 \leq i,j \leq p-1,~i\neq j )\)とおけば\[ia\equiv ja \pmod p \Longleftrightarrow (i-j)a\equiv 0 \pmod p\]が得られるが,\(a \not\equiv 0 \pmod p\)により\(i-j \equiv 0 \pmod p\)でなくてはならない.しかし,\(1 \leq i,j \leq p-1\)であったから,\(i-j\)は\(p-1\)以下であり,矛盾する.
したがって\(1a,~2a,~3a,~\cdots,(p-1)a\)を\(p\)で割った余りはすべて異なる.また\(a\not \equiv 0 \pmod p\)よりこれらは\(p\)では割り切れない(\(p\)で割っても余りが\(0\)にはならない)から,\(1a,~2a,~3a,~\cdots,(p-1)a\)を\(p\)で割ると余りとして\(1,2,\cdots,p-1\)がそれぞれ\(1\)回ずつ現れることになる.これを\[1a\equiv n_{1}~,2a\equiv n_{2}~,~\cdots~,(p-1)a\equiv n_{p-1}\]と表すことにする(ただし\((n_{1},~n_{2},~\cdots~,n_{p-1})\)は\(1,2,~\cdots~,p-1\)の適当な順列).辺々掛けることで
\begin{align*}
&1\cdot 2 \cdot \cdots \cdot (p-1) a^{p-1}\equiv n_{1}n_{2}\cdots n_{p-1} \pmod p \\
\Longleftrightarrow ~&(p-1)! a^{p-1}\equiv (p-1)! \pmod p
\end{align*}ここで,\(\gcd(p,(p-1)!)=1\)であるから(実際,\(p\)と\((p-1)!\)に共通な素因数が存在すると仮定すると,\(p\)が素数であることからその共通の素因数は\(p\)であるが,\(1,2,\cdots,p-1\)はいずれも\(p\)では割り切れず,矛盾する),両辺を\((p-1)!\)で割ることができて\[a^{p-1} \equiv 1 \pmod p\]が得られる.
証明終
「分からない」の大切さ
合同式の問題でよく見る問題です。
解答
\begin{align*}
11^{10}&\equiv 2^{10}\\
&\equiv 2\cdot 2^9\\
&\equiv 2\cdot 8^3\\
&\equiv 2\cdot (-1)^3\\
&\equiv -2\\
&\equiv 7 \pmod 9
\end{align*}よって\[11^{10}\equiv 7 \pmod 9\]したがって求める余りは\(7\)
解答終
授業でこの解説をしたところ「\(\equiv\)を\(=\)の同じような使い方をしてよいのかどうかがいまいちしっくりこない」という感想が。そう言われてみれば確かにこの解説はちょっと乱暴過ぎます(理解に必要な準備が足らない)。以下,この解答の理解のために知識を追加します。
まず一つ目。\[a_1 \equiv a_2 \equiv a_3 \equiv \cdots \equiv a_n \pmod p\]を\[a_1 \equiv a_2 \pmod p,~a_2 \equiv a_3\pmod p,~\cdots~,a_{n-1} \equiv a_n \pmod p\]を意味するものと規約します。これはただの記法なので問題なし。
二つ目。\[a_1 \equiv a_2 \equiv a_3 \equiv \cdots \equiv a_n \pmod p~\text{ならば}~a_1 \equiv a_n \pmod p\]であることを確認します。これは結局,次の性質(推移律)があるのか?という問題に帰着します。
証明
仮定により\(a-b=pk,b-c=pk^{\prime}\Longleftrightarrow a=b+pk,~b=c+pk^{\prime}\).このとき,
\begin{align*}
a-c&=b+pk-c\\
&=c+pk^{\prime}+pk-c\\
&=p(k^{\prime}+k)
\end{align*}よって\[a\equiv c\pmod p\]
証明終
以上により,上の解答の式は
\begin{align*}
&11^{10}\equiv 2^{11}\pmod 9\\
&2^{11}\equiv 2\cdot 2^9\pmod 9\\
&2\cdot2^9\equiv 2\cdot 8^3\pmod 9\\
&2\cdot 8^3\equiv 2\cdot (-1)^3\pmod 9\\
&2\cdot (-1)^3\equiv -2\pmod 9\\
&-2\equiv 7 \pmod 9
\end{align*}を意味し,上で示した性質(推移律)を繰り返し適用することにより\(11^{10}\equiv 7 \pmod 9\)という結論が得られることになります(つまりこの解答の略記が上の解答)。
「わからない」「しっくりこない」という素直な感覚は,理解を深めるひとつの起点であると改めて思ます。
不定方程式
次の不定方程式の整数解を求めよ.\[(1)~7x-17y=1 \qquad (2)~52x+539y=19 \]
教科書と同じ解法はつまらないので,合同式を用いて解いてみます。
解答
\((1)\)
\[7x-17y\equiv1\pmod{7}\]
左辺に\(7(-x)\)を加えて(ア)
\[-17y\equiv1\pmod{7}\]
左辺に\(14y\)を加えて
\[-3y\equiv1\pmod{7}\]
両辺を\(2\)倍して(イ)
\[-6y\equiv2\pmod{7}\]
左辺に\(7y\)を加えて
\[y\equiv2\pmod{7}\]
よって\[y=7k+2~(k\in\mathbb{Z})\]
もとの式にこれを代入して
\[x=17k+5~(k\in\mathbb{Z})\]
\((2)\)
\[52x+539y\equiv19\pmod{52}\]
左辺に\(52(-x)\)を加えて
\[539y\equiv19\pmod{52}\]
左辺に\(52(-10y)\)を加えて
\[19y\equiv19\pmod{52}\]
\(19\)と\(52\)は互いに素であるから,両辺を\(19\)で割ることができて(ウ)
\[y\equiv1\pmod{52}\]
よって\[y=52k+1~(k\in\mathbb{Z})\]
もとの式にこれを代入して
\[x=-539k-10~(k\in\mathbb{Z})\]
解答終
このように合同式を利用すればゴチャゴチャ計算しなくとも簡潔に記述できます。
ただし(ア)(イ)(ウ)の操作は証明が必要です。