1A 第8章
8. 整数
整数問題の全体像
Point 1A 8.1.1 整数問題の全体像
重要ポイント
Point 1A 8.2.1 約数と倍数
\(a,\ b,\ k\)は整数とする。
\(a=bk\)が成り立つとき，\(bはaの\)約数，\(aはb\)の倍数
※0は偶数でもあり，3の倍数でもある。
※0は偶数でもあり，3の倍数でもある。
Point 1A 8.2.2 倍数の判定法
- 2の倍数\(\cdots\)下1桁が偶数
- 3の倍数\(\cdots\)各位の和が3の倍数
- 4の倍数\(\cdots\)下2桁が4の倍数
- 5の倍数\(\cdots\)下1桁が0か5
- 6の倍数\(\cdots\)2の倍数かつ3の倍数
- 8の倍数\(\cdots\)下3桁が8の倍数
- 9の倍数\(\cdots\)各位の和が9の倍数
- 10の倍数\(\cdots\)下1桁が0
- 11の倍数\(\cdots\)各位の1つ飛ばしの和同士の差が11の倍数
- 12の倍数\(\cdots\)3の倍数かつ4の倍数
※これは\(1001=7\times 11\times 13\)由来。1001の素因数分解は覚えておいて良いかもしれない。
【気になる人のための簡単な証明】数を3桁ずつのブロックに区切って考える。\(1001=7\times 11\times 13\)より，\(1000\equiv -1\pmod{7,\ 11,\ 13}\)（7・11・13のどれで割っても，\(1000\)は\(-1\)と合同）。よって，\(N=\cdots+a_2\cdot1000^2+a_1\cdot1000+a_0\)（\(a_0,\ a_1,\ a_2,\ \cdots\)は3桁ずつのブロック）とすると， \[N\equiv a_0-a_1+a_2-\cdots \pmod{7,\ 11,\ 13}\] となる。だから，奇数番目のブロックの和と偶数番目のブロックの和の差が7（または11，13）の倍数であれば\(N\equiv 0\)となり，もとの数\(N\)自体もその倍数になる。
【気になる人のための簡単な証明】数を3桁ずつのブロックに区切って考える。\(1001=7\times 11\times 13\)より，\(1000\equiv -1\pmod{7,\ 11,\ 13}\)（7・11・13のどれで割っても，\(1000\)は\(-1\)と合同）。よって，\(N=\cdots+a_2\cdot1000^2+a_1\cdot1000+a_0\)（\(a_0,\ a_1,\ a_2,\ \cdots\)は3桁ずつのブロック）とすると， \[N\equiv a_0-a_1+a_2-\cdots \pmod{7,\ 11,\ 13}\] となる。だから，奇数番目のブロックの和と偶数番目のブロックの和の差が7（または11，13）の倍数であれば\(N\equiv 0\)となり，もとの数\(N\)自体もその倍数になる。
Point 1A 8.2.3 素因数分解の一意性
任意の合成数はただ一通りに素因数分解される。
(このようなとき，数学ではよく「一意的」に素因数分解される，などと言う。)
(このようなとき，数学ではよく「一意的」に素因数分解される，などと言う。)
Point 1A 8.2.4
\(\sqrt{●}\) が自然数となるには・・・\(●\)が平方数となればよい！
Point 1A 8.2.5 正の約数の個数と総和
\(N=a_1^{p_1}\cdot a_2^{p_2}\cdot a_3^{p_3}\cdots\cdots a_n^{p_n}\)と素因数分解されたとき、
\[(正の約数の個数)=\class{mathkuu}{\underline{(p_1+1)(p_2+1)(p_3+1)\cdots\cdots(p_n+1)}}\] \((正の約数の総和)\)
\[=\class{mathkuu}{\underline{(1+a_1^1+a_1^2+\cdots +a_1^{p_1})(1+a_2^1+a_2^2+\cdots +a_2^{p_2})\cdots\cdots (1+a_n^1+a_n^2+\cdots +a_n^{p_n})}}\]
\[(正の約数の個数)=\class{mathkuu}{\underline{(p_1+1)(p_2+1)(p_3+1)\cdots\cdots(p_n+1)}}\] \((正の約数の総和)\)
\[=\class{mathkuu}{\underline{(1+a_1^1+a_1^2+\cdots +a_1^{p_1})(1+a_2^1+a_2^2+\cdots +a_2^{p_2})\cdots\cdots (1+a_n^1+a_n^2+\cdots +a_n^{p_n})}}\]
例：\(2^3\cdot 5^2\)の正の約数の個数を考えよう。
\(2^3\)の正の約数は\(2^0,\ 2^1,\ 2^2,\ 2^3\)の\((3+1)\)個。
\(5^2\)の正の約数は\(5^0,\ 5^1,\ 5^2\)の\((2+1)\)個。
\(2^3\cdot 5^2\)の正の約数は，\(2^3\)の正の約数と\(5^2\)の正の約数の積で表されるから，\(2^3\cdot 5^2\)の正の約数の個数は，\((3+1)(2+1)=4\cdot 3=12\)個。
\(2^3\)の正の約数は\(2^0,\ 2^1,\ 2^2,\ 2^3\)の\((3+1)\)個。
\(5^2\)の正の約数は\(5^0,\ 5^1,\ 5^2\)の\((2+1)\)個。
\(2^3\cdot 5^2\)の正の約数は，\(2^3\)の正の約数と\(5^2\)の正の約数の積で表されるから，\(2^3\cdot 5^2\)の正の約数の個数は，\((3+1)(2+1)=4\cdot 3=12\)個。
Point 1A 8.2.6
「自然数Aが素数でない」ときたら\(\cdots\)
「Aは2つの自然数の積で表される」と言い換える。
※正確にはAや2つの自然数は1でないとき
「Aは2つの自然数の積で表される」と言い換える。
※正確にはAや2つの自然数は1でないとき
Point 1A 8.2.7 【重要】素数条件の扱い方
\(x,\ y,\ kを整数，p を素数とする。\)式を整理したときに，
(1) \(x\cdot y =p\)の形になったら・・・
\[(x,\ y)=\class{mathkuu}{\underline{(p,\ 1)}}, \class{mathkuu}{\underline{(1,\ p)}}, \class{mathkuu}{\underline{(-1,\ -p)}}, \class{mathkuu}{\underline{(-p,\ -1)}}の4通り\]
(2) \(x\cdot y =p\cdot k\)の形になったら・・・
\[\class{mathkuu}{\underline{x}}は\class{mathkuu}{\underline{p}}の倍数 または \class{mathkuu}{\underline{y}}は\class{mathkuu}{\underline{p}}の倍数\]
コツは，\((積の形)=(\boldsymbol{素数}),\ (積の形)=(\boldsymbol{素数})\times (整数)\)のように「素数は右辺に残す！！」
(1) \(x\cdot y =p\)の形になったら・・・
\[(x,\ y)=\class{mathkuu}{\underline{(p,\ 1)}}, \class{mathkuu}{\underline{(1,\ p)}}, \class{mathkuu}{\underline{(-1,\ -p)}}, \class{mathkuu}{\underline{(-p,\ -1)}}の4通り\]
(2) \(x\cdot y =p\cdot k\)の形になったら・・・
\[\class{mathkuu}{\underline{x}}は\class{mathkuu}{\underline{p}}の倍数 または \class{mathkuu}{\underline{y}}は\class{mathkuu}{\underline{p}}の倍数\]
コツは，\((積の形)=(\boldsymbol{素数}),\ (積の形)=(\boldsymbol{素数})\times (整数)\)のように「素数は右辺に残す！！」
Point 1A 8.2.8 最大公約数、最小公倍数の性質
2つの自然数\(a,\ bの最大公約数をg,\ 最小公倍数をlとする。\)
\(a=ga^\prime,\ b=gb^\prime のとき，\)
\(a=ga^\prime,\ b=gb^\prime のとき，\)
- \(a^\prime , b^\prime は\)互いに素である。 (共通する素因数は\(g\)に入れきったイメージ)
- \(l=\class{mathkuu}{\underline{ga^\prime b^\prime}}\)
- \[ab=\class{mathkuu}{\underline{gl}}\quad\quad\quad\quad\quad\quad\quad(2数の積)=(\class{mathkuu}{\underline{最大公約数}})\times(\class{mathkuu}{\underline{最小公倍数}})\]
Point 1A 8.2.9 最大公約数、最小公倍数の求め方
- ① 最大公約数，最小公倍数を求めるには・・・基本，素因数分解をする！
- ② 大きな2数の最大公約数を求めたいときはユークリッドの互除法を用いるとよい。（詳しくはPoint 8.3.2参照）
- ③ 2数\(a,\ b\)について，最大公約数をG，最小公倍数をLとしたとき，ab=GL利用
例：\(252\)と\(180\)の最大公約数・最小公倍数を求めよう。
素因数分解すると，\(252=2^2\cdot 3^2\cdot 7,\quad 180=2^2\cdot 3^2\cdot 5\)
共通する素因数について，指数が小さい方を選んで掛け合わせると，最大公約数は\(G=2^2\cdot 3^2=36\)
最小公倍数は，共通・非共通を問わずすべての素因数について指数が大きい方を選んで掛け合わせて，\(L=2^2\cdot 3^2\cdot 5\cdot 7=1260\)と直接求めることもできるし，
別解として\(ab=GL\)より，\(L=\dfrac{252\times180}{36}=1260\)と求めることもできる。
素因数分解すると，\(252=2^2\cdot 3^2\cdot 7,\quad 180=2^2\cdot 3^2\cdot 5\)
共通する素因数について，指数が小さい方を選んで掛け合わせると，最大公約数は\(G=2^2\cdot 3^2=36\)
最小公倍数は，共通・非共通を問わずすべての素因数について指数が大きい方を選んで掛け合わせて，\(L=2^2\cdot 3^2\cdot 5\cdot 7=1260\)と直接求めることもできるし，
別解として\(ab=GL\)より，\(L=\dfrac{252\times180}{36}=1260\)と求めることもできる。
Point 1A 8.2.10 互いに素
互いに素・・・最大公約数が1である2整数の関係(共通する素因数がない)
ちなみに，1と1は互いに素である。
\(a,\ b,\ cは整数で，a,\ bは互いに素であるとき，\)
\[(1) \ acがbの倍数であるとき，cは\class{mathkuu}{\underline{bの倍数}}である。\] \[(2) \ aの倍数であり，bの倍数でもある整数は\class{mathkuu}{\underline{abの倍数}}である。\] \[(3) 互いに素である2つの自然数a,\ bについて，abはaとbの\class{mathkuu}{\underline{最小公倍数}}である。\]
※(1)は次のような形で利用可能。\(a,\ b\)が互いに素であるとき，
\[ax=byの形になれば・・・\class{mathkuu}{\underline{x}}は\class{mathkuu}{\underline{b}}の倍数，\class{mathkuu}{\underline{y}}は\class{mathkuu}{\underline{a}}の倍数\]
互いに素であることを確認せずこれらの性質を使うと間違えてしまうことがある。
\[例：(2)で，a=4,\ b=2のとき，4や12などは条件を満たすが8(=a\times b)の倍数でない。\]
ちなみに，1と1は互いに素である。
\(a,\ b,\ cは整数で，a,\ bは互いに素であるとき，\)
\[(1) \ acがbの倍数であるとき，cは\class{mathkuu}{\underline{bの倍数}}である。\] \[(2) \ aの倍数であり，bの倍数でもある整数は\class{mathkuu}{\underline{abの倍数}}である。\] \[(3) 互いに素である2つの自然数a,\ bについて，abはaとbの\class{mathkuu}{\underline{最小公倍数}}である。\]
※(1)は次のような形で利用可能。\(a,\ b\)が互いに素であるとき，
\[ax=byの形になれば・・・\class{mathkuu}{\underline{x}}は\class{mathkuu}{\underline{b}}の倍数，\class{mathkuu}{\underline{y}}は\class{mathkuu}{\underline{a}}の倍数\]
互いに素であることを確認せずこれらの性質を使うと間違えてしまうことがある。
\[例：(2)で，a=4,\ b=2のとき，4や12などは条件を満たすが8(=a\times b)の倍数でない。\]
Point 1A 8.2.11 知っておくと良いこと
たまに使えるので下のことは知っておこう。
- ① \[\class{mathkuu}{\underline{ 連続 }}する2整数は互いに素\]
- ② \[\text{gcd}(m,n)=1\iff \text{gcd}(m+n,\class{mathkuu}{\underline{mn}})=1\] \[(互いに素な2つの自然数の\class{mathkuu}{\underline{和}}と\class{mathkuu}{\underline{積}}も互いに素。逆も成り立つ。)\]
Point 1A 8.2.12 連続n整数の性質
\[一般に，連続n整数の積は，\class{mathkuu}{\underline{n！}}の倍数\]
例：
連続2整数：\(n(n+1)は\class{mathkuu}{\underline{2}}の倍数\)
連続3整数：\(n(n+1)(n+2)は\class{mathkuu}{\underline{6}}の倍数\)
連続\(4\)整数：\(n(n+1)(n+2)(n+3)は\class{mathkuu}{\underline{24}}の倍数\)
また，連続する2整数は互いに素であることも知識として知っておこう。
連続3整数：\(n(n+1)(n+2)は\class{mathkuu}{\underline{6}}の倍数\)
連続\(4\)整数：\(n(n+1)(n+2)(n+3)は\class{mathkuu}{\underline{24}}の倍数\)
また，連続する2整数は互いに素であることも知識として知っておこう。
Point 1A 8.2.13
「自然数○○の末尾に0は何個並ぶか」ときたら→2と5の素因数の個数を調べよ！
※例えばその自然数が\(N!\)などの問題では5の素因数の方が少ないので，結局は\(\class{mathkuu}{\underline{5}}\)の素因数の数だけ10で割り切れる。
※例えばその自然数が\(N!\)などの問題では5の素因数の方が少ないので，結局は\(\class{mathkuu}{\underline{5}}\)の素因数の数だけ10で割り切れる。
Point 1A 8.2.14 倍数の個数(標準)
\(a,\ n\)は自然数とする。
\[1からnまでのn個の自然数のうち，aの倍数の個数は，nをaで割ったときの\class{mathkuu}{\underline{商}}として現れる。\]
ex.) 2の倍数または3の倍数の個数は？などといった問題ではベン図を書く癖をつけておこう。
\[1からnまでのn個の自然数のうち，aの倍数の個数は，nをaで割ったときの\class{mathkuu}{\underline{商}}として現れる。\]
ex.) 2の倍数または3の倍数の個数は？などといった問題ではベン図を書く癖をつけておこう。
Point 1A 8.2.15 自然数の積n！に含まれる素因数の個数(標準)
100！\((1\cdot 2\cdot 3\cdots\cdots 100)\)に含まれる素因数2の数は\(\cdots\cdots\)
\[100を「\class{mathkuu}{\underline{2}}で割った\class{mathkuu}{\underline{商}}」+「\class{mathkuu}{\underline{2^2}}で割った商」+「\class{mathkuu}{\underline{2^3}}で割った商」\cdots\cdots\]
で計算。
\[100を「\class{mathkuu}{\underline{2}}で割った\class{mathkuu}{\underline{商}}」+「\class{mathkuu}{\underline{2^2}}で割った商」+「\class{mathkuu}{\underline{2^3}}で割った商」\cdots\cdots\]
で計算。
Point 1A 8.2.16 倍数の個数(応用)
\[1からnまでに含まれるpの倍数の個数は，\class{mathkuu}{\underline{\left[ \dfrac{n}{p} \right]}}個！\]
※ガウス記号\(\left[ ● \right]\)は，「●を超えない最大の整数」を表す。
※ガウス記号\(\left[ ● \right]\)は，「●を超えない最大の整数」を表す。
Point 1A 8.2.17 自然数の積n！に含まれる素因数の個数(応用)
\(n！に含まれる素因数pの個数は，\)
\[\class{mathkuu}{\underline{\left[ \dfrac{n}{p} \right]+\left[ \dfrac{n}{p^2} \right]+\left[ \dfrac{n}{p^3} \right]+\cdots\cdots}}個！\]
※ガウス記号\(\left[ ● \right]\)は，「●を超えない最大の整数」を表す。
※ガウス記号\(\left[ ● \right]\)は，「●を超えない最大の整数」を表す。
Point 1A 8.2.18 除法の性質
\(a\)を整数、\(b\)を正の整数とし、\(a\)を\(b\)で割ったときの商を\(q\),余りを\(r\)とすると、
\[a=\class{mathkuu}{\underline{ b\times q+r }}, \class{mathkuu}{\underline{0}}\leqq r< \class{mathkuu}{\underline{b}}\] を満たす整数\(q\)と\(r\)がただ1通りに定まる。(一意的)
\[a=\class{mathkuu}{\underline{ b\times q+r }}, \class{mathkuu}{\underline{0}}\leqq r< \class{mathkuu}{\underline{b}}\] を満たす整数\(q\)と\(r\)がただ1通りに定まる。(一意的)
Point 1A 8.2.19 ユークリッドの互除法とその活用パターン3つ
\(aはbの倍数でないとし、aをbで割った余りをrとすると、\)
・長方形に正方形を敷き詰めるやり方も便利なので復習しておこう。
また、ユークリッドの互除法はほかにも以下のようなことに活用できる。
\(a=bq+r のとき、gcd(\)\(a\)\(,\)\(b\)\()=gcd(\)\(b\)\(,\)\(r\)\()\)
(1) これを繰り返し用いることで、大きな2数の最大公約数を求めることができる。間違えやすいのが、\(''商q''\)の値はいつも最大公約数に関係しないので注意しておこう。・長方形に正方形を敷き詰めるやり方も便利なので復習しておこう。
また、ユークリッドの互除法はほかにも以下のようなことに活用できる。
(2) 最小公倍数を求める
最大公約数\(G\)が求まると、
\(A=GA^\prime, B=GB^\prime\)
\((A^\prime\), \(B^\prime\)は互いに素な自然数)と表せ、
\(最小公倍数L=GA^\prime B^\prime\left(=\dfrac{AB}{G}\right)\)が求まる
最大公約数\(G\)が求まると、
\(A=GA^\prime, B=GB^\prime\)
\((A^\prime\), \(B^\prime\)は互いに素な自然数)と表せ、
\(最小公倍数L=GA^\prime B^\prime\left(=\dfrac{AB}{G}\right)\)が求まる
Point 1A 8.2.20 2元1次不定方程式について
これは具体的な問題として出題されるという種類のものではないが，事実として知っておいてよい。
\[2つの整数a,bが\class{mathkuu}{\underline{互いに素}}であるとき，整数cについて\] \[ax+by=cを満たす整数x,yが存在する\]
\[2つの整数a,bが\class{mathkuu}{\underline{互いに素}}であるとき，整数cについて\] \[ax+by=cを満たす整数x,yが存在する\]
不定方程式の解法まとめ
Point 1A 8.3.1 2元1次不定方程式\(ax+by\ \color{red}{=0}\)の解法
互いに素のポイント参照。移項して下の形へ。
例： \[3x=-4y\longrightarrow 3と4は互いに素より，xは\class{mathkuu}{\underline{4}}の倍数，yは\class{mathkuu}{\underline{3}}の倍数\]
例： \[3x=-4y\longrightarrow 3と4は互いに素より，xは\class{mathkuu}{\underline{4}}の倍数，yは\class{mathkuu}{\underline{3}}の倍数\]
Point 1A 8.3.2 【重要】2元1次不定方程式\(ax+by\ \color{red}{=1}\)の解法
① 1組の整数解を見つける
② 辺々引いて「積の形」をつくる→「互いに素を利用した式処理」
※①を見つけるのが難しい時は、ユークリッドの互除法利用。
② 辺々引いて「積の形」をつくる→「互いに素を利用した式処理」
\(a,b\)が互いに素のとき、\(ax=by\)であれば、\(xは\class{mathkuu}{\underline{b}}の倍数\) かつ \(yは\class{mathkuu}{\underline{a}}の倍数\)
※最初からうまく積の形をつくれる場合は一気に「互いに素を利用した式処理」から始めてよい。※①を見つけるのが難しい時は、ユークリッドの互除法利用。
ex.) \(47x+29y=1\)のように係数が大きく，1組の整数解がパッと見つからないときは，ユークリッドの互除法を逆にたどればよい。
\[47=1\cdot29+18,\quad 29=1\cdot18+11,\quad 18=1\cdot11+7,\quad 11=1\cdot7+4,\quad 7=1\cdot4+3,\quad 4=1\cdot3+1\]
最後の式(余りが\(1\)になった式)から逆にたどって代入していくと，
\[1=4-1\cdot3=4-(7-4)=2\cdot4-7=2(11-7)-7=2\cdot11-3\cdot7\]
\[=2\cdot11-3(18-11)=5\cdot11-3\cdot18=5(29-18)-3\cdot18=5\cdot29-8\cdot18\]
\[=5\cdot29-8(47-29)=13\cdot29-8\cdot47\]
よって，\(47\times(-8)+29\times13=1\)より，\((x,\ y)=(-8,\ 13)\)が1組の整数解として見つかる。
Point 1A 8.3.3 2元1次不定方程式\(ax+by\ \color{red}{=c}\)の解法
\(ax+by=\class{mathkuu}{\underline{1}}を満たすx,\ y\)を求めて\(c倍\)！
※共通因数でくくって積の形で処理で済む場合もあるので，積の形は常にチェック。
例：\(4x+7y=91 \iff 4x=-7(y-13)\)
※共通因数でくくって積の形で処理で済む場合もあるので，積の形は常にチェック。
例：\(4x+7y=91 \iff 4x=-7(y-13)\)
Point 1A 8.3.4 2次不定方程式\(xy+●x+▲y+c=0\)の解法
セオリー通り，積の形を作り，不等式で範囲を絞れ！
\(xy+●x+▲y+c=\)\((x+▲)(y+●)-●▲\)\(+c\)を用いて積の形へもっていく。
ex.) \(xy+3x-y-8=0 \iff \)\((x-1)(y+3)=5\)
\(\color{red}{3xy}+9x-y-8=0 \iff \)\((3x-1)(y+3)=5\)
不等式での絞り方は，別ポイント参照。自然数条件などから。
※共通因数でくくって積の形で処理したりという場合もある。
\(xy+●x+▲y+c=\)\((x+▲)(y+●)-●▲\)\(+c\)を用いて積の形へもっていく。
ex.) \(xy+3x-y-8=0 \iff \)\((x-1)(y+3)=5\)
\(\color{red}{3xy}+9x-y-8=0 \iff \)\((3x-1)(y+3)=5\)
不等式での絞り方は，別ポイント参照。自然数条件などから。
※共通因数でくくって積の形で処理したりという場合もある。
Point 1A 8.3.5 2次不定方程式\(x^2-y^2=c\)の解法
\(x^2-y^2=\)\((x+y)(x-y)\)で積の形作れ！
Point 1A 8.3.6 「1.積の形をつくる」処理のまとめ
整数問題ときたら\(\cdots\)1.積の形をつくる
・
\[xy=Kの形になれば，xはKの\class{mathkuu}{\underline{約数}}となるので，あてはまる組を絞り込んでいく\] ・
\[\dfrac{K}{x}が整数，ときたら\cdots\cdots xはKの\class{mathkuu}{\underline{約数}}となるので，あてはまる組を絞り込んでいく\]
・
\[xy=Kの形になれば，xはKの\class{mathkuu}{\underline{約数}}となるので，あてはまる組を絞り込んでいく\] ・
\[\dfrac{K}{x}が整数，ときたら\cdots\cdots xはKの\class{mathkuu}{\underline{約数}}となるので，あてはまる組を絞り込んでいく\]
互いに素絡み
\(a,\ b\)が互いに素であるとき，
\[ax=byの形になれば・・・\class{mathkuu}{\underline{x}}は\class{mathkuu}{\underline{b}}の倍数，\class{mathkuu}{\underline{y}}は\class{mathkuu}{\underline{a}}の倍数\]
\[ax=byの形になれば・・・\class{mathkuu}{\underline{x}}は\class{mathkuu}{\underline{b}}の倍数，\class{mathkuu}{\underline{y}}は\class{mathkuu}{\underline{a}}の倍数\]
素数絡み
\(pが素数のとき，\)
(1) \(x\cdot y =p\)の形になったら・・・
\[(x,\ y)=\class{mathkuu}{\underline{(p,\ 1)}}, \class{mathkuu}{\underline{(1,\ p)}}, \class{mathkuu}{\underline{(-1,\ -p)}}, \class{mathkuu}{\underline{(-p,\ -1)}}の4通り\]
(2) \(x\cdot y =p\cdot k\)の形になったら・・・
\[\class{mathkuu}{\underline{x}}は\class{mathkuu}{\underline{p}}の倍数 または \class{mathkuu}{\underline{y}}は\class{mathkuu}{\underline{p}}の倍数\]
(1) \(x\cdot y =p\)の形になったら・・・
\[(x,\ y)=\class{mathkuu}{\underline{(p,\ 1)}}, \class{mathkuu}{\underline{(1,\ p)}}, \class{mathkuu}{\underline{(-1,\ -p)}}, \class{mathkuu}{\underline{(-p,\ -1)}}の4通り\]
(2) \(x\cdot y =p\cdot k\)の形になったら・・・
\[\class{mathkuu}{\underline{x}}は\class{mathkuu}{\underline{p}}の倍数 または \class{mathkuu}{\underline{y}}は\class{mathkuu}{\underline{p}}の倍数\]
Point 1A 8.3.7 「2.不等式で範囲を絞る」
整数問題では，下のように
\[整数nを●\leqq n \leqq ▲などの形に持っていくことで値を絞ることが有効\]
以下，頻出手段
☆\(「nは自然数」より，n>0 またはn \geqq 1\)
☆\(「実数の2乗は\)0以上\(」利用 (n^2\geqq \class{mathkuu}{\underline{0}})\)
☆\(2次方程式の実数解条件\)（判別式）\(\geqq 0\)
☆\(文字の\)対称\(性から，文字の大小関係利用\)
(下の分数式の例題で，\(x,y,z\)の大小関係がなかったとしても自分で設定して解く。)
\[整数nを●\leqq n \leqq ▲などの形に持っていくことで値を絞ることが有効\]
以下，頻出手段
☆\(「nは自然数」より，n>0 またはn \geqq 1\)
☆\(「実数の2乗は\)0以上\(」利用 (n^2\geqq \class{mathkuu}{\underline{0}})\)
☆\(2次方程式の実数解条件\)（判別式）\(\geqq 0\)
☆\(文字の\)対称\(性から，文字の大小関係利用\)
(下の分数式の例題で，\(x,y,z\)の大小関係がなかったとしても自分で設定して解く。)
例題1：積（商）の形を作る，不等式で範囲を絞る
\[xy + 3x - y - 8 = 0\]
を満たす自然数 \(x,\ y\) の組を求めよ。
\[xy + 3x - y - 3 =5\]
\[
(x - 1)(y + 3) = 5 \quad \cdots (1)\quad\color{red}{積の形ができた！}
\]
ここで，\(x,\ y\) は自然数であるから，
\[
x - 1 \geqq 0,\quad y + 3 \geqq 4\quad\color{red}{不等式で範囲を絞った！}
\]
よって，(1) を満たす整数 \(x - 1,\ y + 3\) の組は
\((x - 1,\ y + 3) = (1,\ 5)\)
したがって，
\((x,\ y) = (2,\ 2)\)別解 \(y\) について整理して商の形を作ってもよい！ \[ y = \frac{-3x + 8}{x - 1} = \frac{-3(x - 1) + 5}{x - 1} = -3 + \frac{5}{x - 1} \]
で \(y\) が整数より，\(\frac{5}{x - 1}\) が整数になるには，\(x - 1\) は \(5\) の約数で，\(x \geqq 1\) から，\(x - 1 = 1,\ 5\)
\(y \geqq 1\) となるのを探して，\((x,\ y) =\boxed{ (2,\ 2)}\)
例題2：不等式で値の範囲を絞る
\[
x + 3y + z = 10
\]
を満たす自然数 \(x,y,z\) の解の組の数を求めよ。
自然数から \(x \geqq 1,\ z \geqq 1\) であり，これで \(y\) の値の範囲を絞る！ \[ 3y = 10 - (x + z)\ より，x + z \geqq 2\ から，3y \leqq 8 \] これを満たす正の整数 \(y\) は，\(y = 1,\ 2\)
- \(y = 1\) のとき，\(x + z = 7\) を満たす自然数\((x,\ z)\) の組の数は 6組
- \(y = 2\) のとき，\(x + z = 4\) を満たす自然数\((x,\ z)\) の組の数は 3組
ゆえに，求める解の組は \(\boxed{9}\) 組
例題3：不等式で値の範囲を絞る
\[
x^2 + 4y^2 = 17
\]
を満たす自然数 \(x,\ y\) を求めよ。
自然数から \(x \mathrel{\bcancel{\mkern-8mu=\mkern-8mu}} 0\) で，\(x^2 > 0\) なので，これで \(y\) の値の範囲を絞る！ \[x^2 = 17 - 4y^2>0\] \[\text{これを満たす正の整数 } y \text{ は } y = 1,\ 2\]
- \(y = 1\) のとき \(x^2 = 13\) → これを満たす正の整数\(x\)はない。
- \(y = 2\) のとき \(x^2 = 1\) → これを満たす正の整数\(xは，x = 1\) ゆえに，\((x,\ y) = \boxed{(1,\ 2)}\)
例題4：
\(x,\ y,\ z \text{ は自然数で，} \ x < y < z \text{ とするとき，} \)
\(\dfrac{1}{x} + \dfrac{1}{y} + \dfrac{1}{z} = 1\)を満たす\(x\ ,y\ ,z\)を求めよ。
\(x,\ y,\ z \text{ は自然数で，} \ x < y < z \text{ とするとき，} \)
\(\dfrac{1}{x} + \dfrac{1}{y} + \dfrac{1}{z} = 1\)を満たす\(x\ ,y\ ,z\)を求めよ。
文字の大小関係の不等式で，値の範囲絞る！ \[ \frac{1}{z} < \frac{1}{y} < \frac{1}{x} から， \frac{1}{x} + \frac{1}{y} + \frac{1}{z} < \frac{1}{x}+\frac{1}{x}+\frac{1}{x} \] \[よって 1 < \frac{3}{x} ゆえに x < 3\]
[1] \(x = 1\) のとき
\(\dfrac{1}{y} + \dfrac{1}{z} = 0 \text{ となり，} y,\ z が自然数であることを満たさないから不適。\)
[2] \(x = 2\) のとき
\(\dfrac{1}{y} + \dfrac{1}{z} = \dfrac{1}{2} \quad \text{となる。また } \ \dfrac{1}{y} + \dfrac{1}{z} < \dfrac{1}{y}+\dfrac{1}{y}\) \[よって\dfrac{1}{2} < \dfrac{2}{y} ゆえに y < 4したがってy = 3\] また，
\(\dfrac{1}{z} = \dfrac{1}{2} - \dfrac{1}{y} = \dfrac{1}{2} - \dfrac{1}{3} = \dfrac{1}{6}\)
\(よって z = 6 \quad これは y < z を満たす。\) \[ \therefore\quad \boxed{x = 2,\ y = 3,\ z = 6} \]
Point 1A 8.3.8 \(n\)進法
\[n進法は、1の位, nの位, n^2の位, \cdots と位ごとにわけて考えよう\]
ex). \(3\)進法
※\(n\)進法を用いると、\(n\)種類の記号でいくらでも大きな数を表すことができる。
\((10進法では0から9の10種)\)
また、小数点以下は\(n^{-1}\left( \dfrac{1}{n}\right) の位,\ n^{-2}\left(\dfrac{1}{n^2}\right) の位, \cdots\)と考える。
※\(n\)進法を用いると、\(n\)種類の記号でいくらでも大きな数を表すことができる。
\((10進法では0から9の10種)\)
また、小数点以下は\(n^{-1}\left( \dfrac{1}{n}\right) の位,\ n^{-2}\left(\dfrac{1}{n^2}\right) の位, \cdots\)と考える。
合同式
Point 1A 8.4.1 前提知識
\[m,\ kを正の整数とし，2つの整数a,\ bをmで割ったときの余りをそれぞれr,\ r^\prime とすると，\]
- \[a+bをmで割った余りは，\class{mathkuu}{\underline{r+r^\prime}}をmで割った余りに等しい。\]
- \[a-bをmで割った余りは，\class{mathkuu}{\underline{r-r^\prime}}をmで割った余りに等しい。\]
- \[abをmで割った余りは，\class{mathkuu}{\underline{rr^\prime}}をmで割った余りに等しい。\]
- \[\class{mathkuu}{\underline{a^k}}をmで割った余りは，\class{mathkuu}{\underline{r^k}}をmで割った余りに等しい。\]
Point 1A 8.4.2 合同式の基本性質
\[a,\ b,\ c,\ dは整数，mは正の整数とし，以下法をmとする。\]
- \(a\equiv a\)
- \(a\equiv bのとき，b\equiv a\)
- \(a\equiv bかつb\equiv cのとき，a\equiv c\) (\(a\equiv b\equiv cと書いてもよい。)\)
Point 1A 8.4.3 合同式の総まとめ
\(a,\ b,\ c,\ dは整数，m,kは正の整数とする。\)
\(a\equiv b,\ c\equiv d \pmod m\)のとき，
\(a\equiv b,\ c\equiv d \pmod m\)のとき，
- \(a+c\equiv \class{mathkuu}{\underline{b+d}} \quad\pmod m\) 特に，\(c=d\)のとき\(a+c\equiv \class{mathkuu}{\underline{b+c}} \quad\pmod m\)
- \(a-c\equiv \class{mathkuu}{\underline{b-d}} \quad\pmod m\) 特に，\(c=d\)のとき\(a-c\equiv \class{mathkuu}{\underline{b-c}} \quad\pmod m\)
- \(ac\equiv \class{mathkuu}{\underline{bd}} \quad\pmod m\) 特に，\(c=d\)のとき \(ac\equiv \class{mathkuu}{\underline{bc}} \quad\pmod m\)
- \(a^k\equiv \class{mathkuu}{\underline{b^k}} \quad\pmod m\)
- \[ab\equiv ac\color{red}{かつgcd(\class{mathkuu}{\underline{a}},\ \class{mathkuu}{\underline{m}})=\class{mathkuu}{\underline{1}}}のとき，\quad\ \class{mathkuu}{\underline{b\equiv c}}\quad\pmod m\]
\(●\equiv ▲ \quad\pmod m\)というのは，「\(m\)で割った余りで考える世界では，●と▲はイコールのように扱える(合同)」と認識。上式たちは下のように意味で理解するとよい。
- 等式のように辺々足してもOK！ \[(ex.)\ a\equiv b,\ 4\equiv 7 \iff \class{mathkuu}{\underline{a+4\equiv b+7}} \pmod 3\] 特に「\(dがcのとき\)」なら「辺々同じ数足してもOK！」すなわち， 等式と同様「合同式は移項ができる」ということ。 \[(ex.)\ a-5\equiv b \iff \class{mathkuu}{\underline{a\equiv b+5}}\]
- 等式のように辺々引いてもOK！ \[(ex.)\ a\equiv b,\ 4\equiv 7 \iff \class{mathkuu}{\underline{a-4\equiv b-7}} \pmod 3\] 特に「\(dがcのとき\)」なら「辺々同じ数引いてもOK！」すなわち， 等式と同様「合同式は移項ができる」ということ。 \[(ex.)\ a+5\equiv b \iff \class{mathkuu}{\underline{a\equiv b-5}}\]
- 等式のように辺々かけてもOK！ \[(ex.)\ a\equiv b,\ 4\equiv 7 \iff \class{mathkuu}{\underline{4a\equiv 7b}} \pmod 3\] 特に「\(dがcのとき\)」なら等式と同じように「両辺同じ数かけてもOK！」。 \[(ex.)\ a\equiv b \iff 5a\equiv 5b\]
- よく利用するのは， \[100\equiv 1\pmod 3\ より，\ 100^{20}\equiv \class{mathkuu}{\underline{1^{20}}} = 1 \pmod 3\] のように大きな数の余りが小さな数で考えられる，という問題。これがかなり便利な点。 \[19\equiv -1\pmod 4\ より，\ 19^{100}\equiv \class{mathkuu}{\underline{(-1)^{100}}} = 1 \pmod 4\]
- ※【超重要】割り算が成り立つのは， \[\class{mathkuu}{\underline{a(割る数)}}と，\class{mathkuu}{\underline{m(法)}}が\class{mathkuu}{\underline{互いに素}}であるときのみ！\] 反例： \[6\equiv 2\pmod 4\ の両辺を2で割った\ 3\equiv 1\pmod 4\ は間違い。\]
Point 1A 8.4.4 合同式利用の注意点
「和・差・積・累乗はOKだが，商は注意！」と繰り返し覚えておこう。また，移項はできる！（できる or できない）
Point 1A 8.4.5 フェルマーの小定理
\(p\)が素数で，\(aがp\)と互いに素であるとき
\[\class{mathkuu}{\underline{a^{p-1}}}\equiv \class{mathkuu}{\underline{1}} \pmod{\class{mathkuu}{\underline{p}}}\]