[高校入試]「余り」に関する整数問題の解き方を丁寧に解説！

みなさんこんにちは、ゆーきゃんです。

整数問題に関して、いくつか解説してきましたが、今回は「余り」がテーマです。

これで入試で出題される整数問題のパターンはある程度網羅できたかと思います。

それでは早速解説に入っていきます。

また、本記事と合わせて以下の記事もぜひご覧ください。

「余り」に関する等式の概要
「合同式」の定義
例題演習
【1】の解説
【2】の解説
【3】の解説
全9回の動画授業で「整数問題」が無敵に！
まとめ：[高校入試]「余り」に関する整数問題の解き方を丁寧に解説！

「余り」に関する等式の概要

まず、「余り」に関して以下の等式を覚えておきましょう。

$k,m,n,N$を正の整数とし、$0≦n<N$とする。
このとき、$N$を$k$で割ったときの商を$m$, 余りを$n$とすると、
(割られる数)＝(割る数)×(商)＋(余り)
つまり、
$$N=km+n$$
が成立する。

例えば、$47$を$7$で割ると、$5$余るため、
$$47=7×6+5$$
と表されます。

「合同式」の定義

また、数学が得意な方は以下の「合同式」も覚えておくとよいでしょう。

整数$a.b$に関して、$a,b$を正の整数$p$で割ったときの余りが等しいとき、
「$a,b$は$p$を法として合同である」といい、
$$a \equiv b \pmod p$$
と表す。
また、$a \equiv b \pmod p, c \equiv d \pmod p$であるとき、合同式の性質として以下が成り立つ。

$a+c \equiv b+d \pmod p$
$a-c \equiv b-d \pmod p$
$ac \equiv bd \pmod p$

例えば、$13,7$は3で割った余りがともに1になるため、$13 \equiv 7 \pmod 3$であり、

$8,17$は3で割った余りがともに2になるので、$8 \equiv 17 \pmod 3$です。

このとき、$13×8,7×17$を3で割った余りはともに2なので、$13×8 \equiv 7×17 \pmod 3$となります。

以上を踏まえて、「余り」に関する問題演習を行っていきます。

例題演習

以下の問題にチャレンジしてみましょう。

【1】と【2】は「余り」に関する典型問題です。

【3】は出題背景が分かった人にとっては、すぐにできる問題かと思います。

整数問題_余り_例題ダウンロード

【1】の解説

まず、【1】の解説です。

いきなり3つの条件を考えるのは大変なので、まずは「6で割って5余り、7で割って6余る」数を考えます。

このとき、

「それぞれの割る数の最小公倍数」で割ったときの余りに注目する

とよいです。

6と7の最小公倍数は42ですから、42で割ったときの余りに注目します。

ここで、0以上42未満の整数のうち、6で割って5余る数は以下の通りです。

5,11,17,23,29,35,41

この中で、7で割って6余る数は41のみです。

このとき、以下のことを覚えておくとよいでしょう。

$a,b,x,y$を正の整数とする。
「$a$で割って$b$余り、$x$で割って$y$余る」整数が1つ見つかったとする。
それを$N_0$とすれば、$n$を整数として、その条件を満たす整数は以下のように表される。($\mathrm{lcm}(a,x)$:$a,x$の最小公倍数)
$$n×\mathrm{lcm}(a,x)+N_0$$

よって、2つの条件を満たす正の整数は$k$を0以上の整数として、$(42k+41)$と表せます。

つぎに、$(42k+41)$において「8で割ったら7余る」ときの$k$の最小値を求めます。

$(42k+41)$を無理やり8でくくると、以下のようになります。
\begin{eqnarray}
42k+41=8(5k+5)+2k+1
\end{eqnarray}

よって、$(2k+1)$を8で割って7余るときの、$k$の最小値を求めればよいことが分かります。

そうすると、$k=3$のときにはじめてその条件を満たすことが分かります。

ですので、答えは$42×3+41=167$となります。

【2】の解説

この問題では、先ほどご紹介した「合同式」を用いて解いてみましょう。

以下、合同式の法は17とします。

25を17で割ると8余るため、$5^2 \equiv 8$です。

ここで、合同式の性質を利用し、$8^3$を17で割った余りは2なので、
$$(5^2)^3 \equiv 8^3 \equiv 2$$
が成り立ちます。

よって、
$$5^{555}=\{(5^2)^3\}^{92}×5^3 \equiv 2^{92}×5^3$$

また、$256=2^8$を$17$で割った余りが$1$となるので、$2^8\equiv1$です。

これらから、$2^{92}×5^3=(2^8)^{11}×2^4×5^3\equiv 1^{11}×2^4×5^3=2000$となり、問題の答えは$2000$を$17$で割った余りと一致します。

以上より、答えは11となります。

【3】の解説

問1の解説

\begin{eqnarray}
96&=&18×5+6\\
18&=&6×3+0\\
\end{eqnarray}
より、$≪96,18≫=6$です。

\begin{eqnarray}
144&=&15×9+9\\
15&=&9×1+6\\
9&=&6×1+3\\
6&=&3×2+0
\end{eqnarray}
より、$≪144,15≫=3$です。

\begin{eqnarray}
791&=&182×4+63\\
182&=&63×2+56\\
63&=&56×1+7\\
56&=&7×8+0
\end{eqnarray}
より、$≪791,182≫=7$となります。

これら3つを計算して何か気づいたことはありませんか？

これらは実は、2数の最大公約数となっています。

この問題は「ユークリッドの互除法」を背景に作問されており、それは以下のことをいいます。

$k,m,n,N$を正の整数とし、$0≦n<N$とする。
$$N=km+n$$
となるとき、以下が成立する。($\gcd(a,b)$:$a,b$の最大公約数)
$$\gcd(N,k)=\gcd(k,n)$$

この問題で行っている操作は実は、2つの整数の最大公約数を求める手続きに他ならないのです。

それを踏まえ、引き続き解説を行ってゆきます。

問2の解説

$≪42,x≫$を未知数とみて、二次方程式$(≪42,x≫)^2-13≪42,x≫-14=0$を解くと、
$≪42,x≫=14,-1$となります。

$≪42,x≫$は正の値になるので、$≪42,x≫=14$です。

よって、$42,x$の最大公約数が$14$となるような$x$を求めればよいので、

答えは$x=14,28$となります。

問3の解説

まず、$≪(p+1)^2,p-1≫$について考えます。

$p=2$のとき、$≪(p+1)^2,p-1≫=≪9,1≫=1$となり、
$≪p^2+3,≪(p+1)^2,p-1≫≫≠2$は明らかなので不適です。

$p=3$のとき、$≪(p+1)^2,p-1≫=≪16,2≫=2$となり、
$≪p^2+3,≪(p+1)^2,p-1≫≫=≪12,2≫=2$となって、問題の条件に合致します。

$p=5$のとき、$≪(p+1)^2,p-1≫=≪36,4≫=4$であり、
$≪p^2+3,≪(p+1)^2,p-1≫≫=≪28,4≫=4$となり、不適です。

さて、$p＞5$のとき、
\begin{eqnarray}
(p+1)^2&=&p^2+2p+1\\
&=&(p+3)(p-1)+4
\end{eqnarray}
と変形できます。

よって$p>5$ゆえ、$p$は奇数であるから、$(p-1)$が偶数となることを踏まえると、
$≪(p+1)^2,p-1≫=≪p-1,4≫=2$または$4$のいずれかになります。

$k$を$0$以上の整数として、$p$は奇数ですから、$4$で割ったときの余りに注目し、

$≪(p+1)^2,p-1≫=≪p-1,4≫=4$となるとき、$p=4k+1$
$≪(p+1)^2,p-1≫=≪p-1,4≫=2$となるとき、$p=4k+3$

となります。

$p=4k+1$のとき、
\begin{eqnarray}
p^2+3&=&(4k+1)^2+3\\
&=&(4k)^2+2×4k+4\\
&=&4(4k^2+2k+1)
\end{eqnarray}
より、$≪p^2+3,≪(p+1)^2,p-1≫≫=4$となって、
$p=4k+1$の形で表される素数は不適です。

$p=4k+3$のとき、
\begin{eqnarray}
p^2+3&=&(4k+3)^2+3\\
&=&(4k)^2+2×4k×3+12\\
&=&2(8k^2+12k+6)
\end{eqnarray}
より、$≪p^2+3,≪(p+1)^2,p-1≫≫=2$となって、
$p=4k+3$の形で表される素数は問題の条件に合致します。

$4$で割って$3$余り、$3$より大きい素数を列挙すると、$7,11,19,23$となり、
答えは$p=3,7,11,19,23$です。

問3では実は3つの数の最大公約数を求めており、それが2となる条件を考察させる問題でした。

3つの数の最大公約数を求める方法として、