整数の除法、合同式 | きょうさい対策ブログ

○整数の除法・合同式

\( \displaystyle a,b \)を整数，\( \displaystyle m \)を自然数とする．
(1)\( \displaystyle a=mq+r \ (0 \leqq r < m) \)を満たす整数\( \displaystyle q,r \)をそれぞれ\( \displaystyle a \)を\( \displaystyle m \)で割ったときの商,余りという.
(2)\( \displaystyle a,b \)を\( \displaystyle m \)で割ったときの余りが等しいとき，\( \displaystyle a \)と\( \displaystyle b \)は\( \displaystyle m \)を法として合同であるといい，\( \displaystyle a \equiv b \ (\text{mod} \ m) \)で表す.
\( \displaystyle a \equiv b \ (\text{mod} \ m) \)は，\( \displaystyle a=b+mk \)となる整数\( \displaystyle k \)が存在することを意味する．

○合同式の性質

\( \displaystyle a,b,c,d \)を整数，\( \displaystyle m \)を自然数とする.
\( \displaystyle \begin{cases} a \equiv b \ (\text{mod} \ m) \\ c \equiv d \ (\text{mod} \ m) \end{cases} \implies \begin{cases} a+c \equiv b+d \ (\text{mod} \ m) \\ ac \equiv bd \ (\text{mod} \ m) \end{cases} \)
※上の掛け算を繰り返し使うことで，
\( \displaystyle a \equiv b \ (\text{mod} \ m) \implies a^k \equiv b^k \ (\text{mod} \ m) \)
が言える．

(例1)\( \displaystyle 123 \times 456 \)を\( \displaystyle 7 \)で割った余りを求める．

説明例(クリックして下さい)

\( \displaystyle 123 \equiv 4 \ (\text{mod} \ 7), 456 \equiv 1 \ (\text{mod} \ 7) \)
により，
\( \displaystyle \ \ \ \ \ 123 \times 456 \equiv 4 \cdot 1=1 \ (\text{mod} \ 7) \)
よって余りは\( \displaystyle 1 \) (答)

※\( \displaystyle 123 \times 456=56088 \)と計算する必要はない．

(例2)\( \displaystyle n \)を\( \displaystyle 5 \)で割った余りが\( \displaystyle 4 \)のとき，\( \displaystyle n^3+2n^2+3n+4 \)を\( \displaystyle 5 \)で割ったときの余りを求める．

説明例(クリックして下さい)

\( \displaystyle n \equiv -1 \ (\text{mod} \ 5) \)であるから，
\( \displaystyle \ \ \ \ \ n^3+2n^2+3n+4 \)
\( \displaystyle \ \ \ \ \ \equiv (-1)^3+2 \cdot (-1)^2+3 \cdot (-1)+4 \)
\( \displaystyle \ \ \ \ \ \equiv -1+2-3+4=2 \ (\text{mod} \ 5) \)
よって余りは\( \displaystyle 2 \) (答)

○連続整数積の性質

\( \displaystyle n \)を自然数とする．連続する\( \displaystyle n \)個の整数の積は\( \displaystyle n! \)の倍数である．

説明例(クリックして下さい)

連続する\( \displaystyle n \)個の整数の積は一番小さい整数を\( \displaystyle m+1 \)として，
\( \displaystyle (m+1)(m+2) \cdots (m+n) \)
と表すことができる．

(ア)すべての因数が正のとき，
\( \displaystyle (m+1)(m+2) \cdots (m+n) \)
\( \displaystyle \ \ \ \ \ ={}_{m+n}\mathrm{P}_n=n! \cdot {}_{m+n}\mathrm{C}_n \equiv 0 \ (\text{mod} \ n!) \)

(イ)すべての因数が負のとき，各因数から\( \displaystyle (-1) \)をくくりだして，
\( \displaystyle (m+1)(m+2) \cdots (m+n) \)
\( \displaystyle \ \ \ \ \ =(-1)^n \cdot ( \)連続する\( \displaystyle n \)個の正の整数の積\( \displaystyle ) \)
の形になるから，(ア)によりこれは\( \displaystyle n! \)の倍数である．

(ウ)因数に\( \displaystyle 0 \)を含むとき，連続する\( \displaystyle n \)個の整数の積は\( \displaystyle 0 \)となり，とくに\( \displaystyle n! \)の倍数である．
以上，(ア)，(イ)，(ウ)より，連続する\( \displaystyle n \)個の整数の積は\( \displaystyle n! \)の倍数である．■

※\( \displaystyle 3! \)ぐらいまでなら，上の証明は大袈裟．\( \displaystyle 2 \)の倍数かつ\( \displaystyle 3 \)の倍数であることからすぐ示せる．

○各種あまりの処理

	有効な手法
多項式型\( \displaystyle f(n) \)の余りの処理	余りで分類して代入する
指数型\( \displaystyle a^{f(n)} \)の余りの処理	余りの周期性を利用する or 二項定理を利用する

(例1)\( \displaystyle n \)を整数とする．\( \displaystyle n^2 \)を\( \displaystyle 3 \)で割ったときの余りを求めよ．

説明例(クリックして下さい)

\( \displaystyle 3 \)を法として，
\( \displaystyle n \equiv 0 \)のとき，\( \displaystyle n^2 \equiv 0 \)
\( \displaystyle n \equiv 1 \)のとき，\( \displaystyle n^2 \equiv 1 \)
\( \displaystyle n \equiv 2 \equiv -1 \)のとき，\( \displaystyle n^2 \equiv 1 \)
よって，\( \displaystyle n^2 \)を\( \displaystyle 3 \)で割った余りは，
\( \displaystyle \begin{cases} n \text{が} 3 \text{の倍数のとき} \ \ 0 \\ n \text{が} 3 \text{の倍数でないとき} \ \ 1 \end{cases} \) (答)

※次の計算はよく使われる．
\( \displaystyle \ \ \ \ \ (2n+1)^2 \equiv 1 \ (\text{mod} \ 4) \)
\( \displaystyle \ \ \ \ \ (3n \pm 1)^2 \equiv 1 \ (\text{mod} \ 3) \)(今扱ったことの一部)
\( \displaystyle \ \ \ \ \ (4n \pm 1)^2 \equiv 1, (4n+2)^2 \equiv 4 \ (\text{mod} \ 8) \)

(例2，典型問題)自然数\( \displaystyle a,b,c \)について，\( \displaystyle a^2+b^2=c^2 \)が成り立つとき，\( \displaystyle a,b \)のうち少なくとも\( \displaystyle 1 \)つは\( \displaystyle 3 \)の倍数であることを示せ．

説明例(クリックして下さい)

\( \displaystyle a,b \)がともに\( \displaystyle 3 \)の倍数でないとすると，\( \displaystyle a^2 \equiv 1, b^2 \equiv 1 \ (\text{mod} \ 3) \)が成り立ち，
\( \displaystyle \ \ \ \ \ a^2+b^2 \equiv 2 \ (\text{mod} \ 3) \)
一方，\( \displaystyle c^2 \equiv 0 \)または\( \displaystyle 1 \ (\text{mod} \ 3) \)であるから，\( \displaystyle a^2+b^2=c^2 \)であることに矛盾する(余りの不一致)．
よって，\( \displaystyle a,b \)のうち少なくとも\( \displaystyle 1 \)つは\( \displaystyle 3 \)の倍数である．■

(例3)\( \displaystyle 9^{100} \)を\( \displaystyle 7 \)でわった余りを求める．

説明例(クリックして下さい)

7を法として，
\( \displaystyle 9 \equiv 2, 9^2 \equiv 4, 9^3 \equiv 4 \cdot 2 \equiv 1 \)
よって，\( \displaystyle 9^{100}=(9^3)^{33} \cdot 9 \equiv 1 \cdot 2 \equiv 2 \)であるから，\( \displaystyle 9^{100} \)を\( \displaystyle 7 \)でわった余りは\( \displaystyle 2 \) (答)

※この問題は二項定理を使うのではうまくいかない．実際，\( \displaystyle (7+2)^{100}=(7 \text{の倍数})+2^{100} \)のように変形しても，\( \displaystyle 2^{100} \)の処理が必要になる．

(例4)\( \displaystyle n \)を自然数とするとき，\( \displaystyle 8^n-(5n+3) \cdot 3^{n-1} \)が\( \displaystyle 25 \)の倍数であることを示す．

説明例(クリックして下さい)

\( \displaystyle 8^n-(5n+3) \cdot 3^{n-1}=(5+3)^n-(5n+3) \cdot 3^{n-1} \)
\( \displaystyle \ \ \ \ \ =\sum_{k=0}^n {}_n\mathrm{C}_k \cdot 5^k \cdot 3^{n-k}-5n \cdot 3^{n-1}-3^n \)
\( \displaystyle \ \ \ \ \ \equiv {}_n\mathrm{C}_0 \cdot 3^n+{}_n\mathrm{C}_1 \cdot 5 \cdot 3^{n-1}-5n \cdot 3^{n-1}-3^n \)
\( \displaystyle \ \ \ \ \ \equiv 0 \ (\text{mod} \ 25) \)
であるから，\( \displaystyle 8^n-(5n+3) \cdot 3^{n-1} \)は\( \displaystyle 25 \)の倍数である．■

※この問題では周期性での処理は難しい．

◯合同方程式の処理

	有効な処理
\( \displaystyle ax \equiv b \)の処理	[係数の調整]\( \displaystyle a, m \)が互いに素のとき， \( \displaystyle x \equiv y \ (\text{mod} \ m) \Leftrightarrow ax \equiv ay \ (\text{mod} \ m) \) を利用し，係数を \( \displaystyle 1 \) にする
連立式の処理 \( \displaystyle \begin{cases} ax \equiv b \ (\text{mod} \ M) \\ cx \equiv d \ (\text{mod} \ N) \end{cases} \)	[法の統一]\( \displaystyle l > 0 \)のとき， \( \displaystyle a \equiv b \ (\text{mod} \ m) \Leftrightarrow la \equiv lb \ (\text{mod} \ lm) \) を利用し，法を統一する．
法が大きいとき	[法の分解] 互いに素な法に分解して調べる

(例1)\( \displaystyle 7n \)を\( \displaystyle 11 \)で割った余りが\( \displaystyle 1 \)となるとき，\( \displaystyle n \)を\( \displaystyle 11 \)で割った余りを求める．

説明例(クリックして下さい)

\( \displaystyle 7n \equiv 1 \ (\text{mod} \ 11) \)のとき，\( \displaystyle 7 \cdot 8=56 \equiv 1 \ (\text{mod} \ 11) \)であることに注目して，
\( \displaystyle 7 \cdot 8n \equiv 8 \ (\text{mod} \ 11) \ \therefore n \equiv 8 \ (\text{mod} \ 11) \)
よって，\( \displaystyle n \)を\( \displaystyle 11 \)で割った余りは\( \displaystyle 8 \) (答)

(例2)\( \displaystyle 7 \)で割ると\( \displaystyle 5 \)余り，\( \displaystyle 13 \)で割ると\( \displaystyle 7 \)余る\( \displaystyle 3 \)桁の自然数の個数を求める．

説明例(クリックして下さい)

\( \displaystyle n \equiv 5 \ (\text{mod} \ 7), n \equiv 7 \ (\text{mod} \ 13) \)のとき，
\( \displaystyle 13n \equiv 65 \ (\text{mod} \ 91) \)…①, \( \displaystyle 7n \equiv 49 \ (\text{mod} \ 91) \)…②
②\( \displaystyle \times 2 – 1 \)により，\( \displaystyle n \equiv 49 \cdot 2 – 65 = 33 \ (\text{mod} \ 91) \)
よって，\( \displaystyle n=33+91k \) (\( \displaystyle k \)は整数)と表される．
\( \displaystyle n \)が\( \displaystyle 3 \)桁(\( \displaystyle 100 \leqq n \leqq 999 \))になるのは\( \displaystyle k=1, 2, \cdots, 10 \)のとき．よって，求める個数は，\( \displaystyle 10 \)個 (答)

※「①かつ②(あるいはその前の状態)」が\( \displaystyle n \equiv 33 \ (\text{mod} \ 91) \)と同値なのは，中国剰余定理(後述)からわかる．そのことを使いたくない場合は，定義に戻って
\( \displaystyle \ \ \ \ \ n=5+7a, n=7+13b \) (\( \displaystyle a,b \)は整数)
などとおき，
\( \displaystyle \ \ \ \ \ 5+7a=7+13b \)
\( \displaystyle \ \ \ \ \ \therefore 7a-13b=2 \)
と，\( \displaystyle 2 \)元\( \displaystyle 1 \)次不定方程式に直して解けばよい．

(例3)\( \displaystyle 13^{99} \)を\( \displaystyle 72 \)で割った余りを求める．

説明例(クリックして下さい)

\( \displaystyle N=13^{99} \)とおく．\( \displaystyle 72=2^3 \cdot 3^2 \)により，\( \displaystyle \text{mod} \ 8 \)と\( \displaystyle \text{mod} \ 9 \)に分けて調べる．
\( \displaystyle 8 \)を法として，
\( \displaystyle 13 \equiv 5, 13^2 \equiv 25 \equiv 1, N \equiv (13^2)^{49} \cdot 13 \equiv 5 \ (\text{mod} \ 8) \)
また，\( \displaystyle 9 \)を法として，
\( \displaystyle 13 \equiv 4, 13^2 \equiv 16 \equiv 7, 13^3 \equiv 28 \equiv 1, \)
\( \displaystyle N \equiv (13^3)^{33} \equiv 1 \ (\text{mod} \ 9) \)
となる．
\( \displaystyle \ \ \ \ \ 9N \equiv 45 \ (\text{mod} \ 72) \)…①,
\( \displaystyle \ \ \ \ \ 8N \equiv 8 \ (\text{mod} \ 72) \)…②
①-②から，\( \displaystyle N \equiv 37 \ (\text{mod} \ 72) \)
よって，\( \displaystyle 13^{99} \)を\( \displaystyle 72 \)で割った余りは\( \displaystyle 37 \) (答)

※(別解，二項定理)
\( \displaystyle 13^{99}=(2^2 \cdot 3+1)^{99}=\sum_{k=0}^{99} (2^2 \cdot 3)^k \cdot {}_{99}\mathrm{C}_k \)
\( \displaystyle \ \ \ \ \ =1+2^2 \cdot 3 \cdot 99+((2^2 \cdot 3)^2 \text{の倍数}) \)
\( \displaystyle \ \ \ \ \ \equiv 1+12 \cdot 27=325 \equiv 37 \ (\text{mod} \ 72) \)

※指数型の余りは，周期性の確認か，二項定理をベースにし，それでも難しい場合は法の分解を考えるとよい．ただし，法の分解も万能ではなく，数が大きいときは計算は大変である．

◯中国式剰余定理

\( \displaystyle m,n \)を互いに素な自然数とする．
\( \displaystyle \ \ \ \ \ x \equiv a \ (\text{mod} \ m), x \equiv b \ (\text{mod} \ n) \)
を満たす整数\( \displaystyle x \)が\( \displaystyle mn \)を法として一意に定まる．

説明例(クリックして下さい)

\( \displaystyle m,n \)は互いに素であるから\( \displaystyle pm+qn=1 \)を満たす整数\( \displaystyle p,q \)が存在する．
よって，\( \displaystyle x \equiv a \ (\text{mod} \ m), x \equiv b \ (\text{mod} \ n) \)のとき，
\( \displaystyle nx \equiv an \ (\text{mod} \ mn), mx \equiv bm \ (\text{mod} \ mn) \)であるから，
\( \displaystyle x=(qn+pm)x \equiv qnx+pmx \equiv aqn+bpm \ (\text{mod} \ mn) \)．
逆に，\( \displaystyle x \equiv aqn+bpm \ (\text{mod} \ mn) \)のとき，
\( \displaystyle \begin{cases} x \equiv aqn = a \cdot (1-pm) \equiv a \ (\text{mod} \ m) \\ x \equiv bpm = b \cdot (1-qn) \equiv b \ (\text{mod} \ n) \end{cases} \)
以上により，
\( \displaystyle x \equiv a \ (\text{mod} \ m) \)，\( \displaystyle x \equiv b \ (\text{mod} \ n) \Leftrightarrow x \equiv aqn+bpm \ (\text{mod} \ mn) \)であるから，\( \displaystyle x \)は\( \displaystyle mn \)を法として一意に定まる．■

※\( \displaystyle 1 \)行目の「\( \displaystyle m,n \)は互いに素であるとき\( \displaystyle pm+qn=1 \)を満たす整数\( \displaystyle p,q \)が存在する．」は，ユークリッドの互除法から導くことができる．

◯整数問題の絞り込み手法

	例
積の形から絞る	\( \displaystyle XY=5 \)となる整数は？ \( \displaystyle (X,Y)=(\pm 1, \pm 5), (\pm 5, \pm 1) \) (複号同順)
値の範囲から絞る	\( \displaystyle X^2+Y^2=5 \)となる整数は？ \( \displaystyle \ \ \ \ \ 5=X^2+Y^2 \geqq X^2 \)により\( \displaystyle X^2 \leqq 5 \ \ \ \ \ \therefore X=\pm 2, \pm 1, 0 \) \( \displaystyle \ \ \ \ \ \therefore (X,Y)=(\pm 1, \pm 2), (\pm 2, \pm 1) \)(複号任意)
余りに注目して絞る	\( \displaystyle p^2+2 \)が素数となる\( \displaystyle 3 \)以上の素数\( \displaystyle p \)は？ \( \displaystyle p=3 \)は適する．\( \displaystyle p>3 \)とする． [mod \( \displaystyle 2 \)で考える]\( \displaystyle \rightarrow p \)は奇素数だから\( \displaystyle p \equiv 1 \ (\text{mod} \ 2) \)． \( \displaystyle \ \ \ \ \ p^2+2 \equiv 3 \equiv 1 \ (\text{mod} \ 2) \ \ \ \ \ \therefore p^2+2 \)は奇数(特に何も絞り込めない) [mod \( \displaystyle 3 \)で考える]\( \displaystyle \rightarrow p \)は奇素数だから\( \displaystyle p \equiv \pm 1 \ (\text{mod} \ 3) \)． \( \displaystyle \ \ \ \ \ p^2+2 \equiv 0 \ (\text{mod} \ 3) \) \( \displaystyle \ \ \ \ \ \therefore p^2+2 \)は\( \displaystyle 3 \)の倍数かつ\( \displaystyle p^2+2>11 \)により，素数にはなりえない．以上により，\( \displaystyle p=3 \)．

この記事は役に立ちましたか？

間違い/不具合かな？
と思ったらこちらへ