京都大学 理学部特色入試 2027年度 第4問 解説
(2026年11月に行われた特色入試の問題です。)
問題編
問題
$p$ と $q$ を互いに素な正の整数とし、
$S=\{mp+nq \mid m$ と $n$ は $0$ 以上の整数 $\}$
とおく。このとき、$S$ に属さない $0$ 以上の整数の個数を求めよ。
考え方
「$0$ 以上」という条件がなければ、 $p$ と $q$ が互いに素の場合は、どんな整数でも $mp+nq$ の形で表すことができます。「$0$ 以上」という条件がつくことで、小さい数の中には表せなくなるものが出てきます。これを数えるために、表せるものをどんどん消して候補を絞っていくと考えやすいでしょう。
下の解答は一般的なケースで書いていますが、わかりにくい場合はさらにその下の解説で具体的にどういうことをやっているかを説明していますので、そちらも読んでみましょう。
具体的な値を使った問題はほかの入試でもよく出ますし、この問題の結果自体は有名なので、特色入試にしてはやさしめの問題です。
解答編
問題
$p$ と $q$ を互いに素な正の整数とし、
$S=\{mp+nq \mid m$ と $n$ は $0$ 以上の整数 $\}$
とおく。このとき、$S$ に属さない $0$ 以上の整数の個数を求めよ。
解答
$0$ 以上の整数を、左上から順番に、1行が $p$ 個になるように並べていく。そうすると、$p$ 個の各列には、 $p$ で割った余りが等しい整数が並び、1つ下に進むごとに $p$ ずつ増える。よって、 $nq$ に対し、 $nq$ とその下にある数はすべて $S$ に属する。
ここで、$p$ と $q$ は互いに素なので、 $0q,1q,\cdots,(p-1)q$ をそれぞれ $p$ で割った余りは互いに異なる(もし同じものがあるとすると、 $p$ より小さな正の整数と $q$ との積が $p$ の倍数になってしまうため)。よって、これらは各列にちょうど1個ずつ現れる。
次に、$S$ に属する数 $mp+nq$ は、$nq$ と同じ列で $nq$ と同じかそれより下の位置にある。また、$n \geqq p$ のとき $nq=qp+(n-p)q$ なので、$nq$ は $(n-p)q$ と同じ列で、それより下にある。これを繰り返すと、$S$ に属する数はすべて、$0q, 1q, \cdots, (p-1)q$ のいずれかと同じ列で、同じ場所かそれより下の位置にあることがわかる。
よって、各列で $0q, 1q, \cdots, (p-1)q$ のそれぞれより上にある数だけが $S$ に属さないことがわかる。
以上から、各 $kq$ ($k=1,2,\cdots,p-1$)より上にある数の個数の和を求めればよい($k=0$ のときは上に数はないため除外)。$kq$ より上にある数の個数は、 $\left[\dfrac{kq}{p}\right]$ と書ける(ここで、 $[x]$ は、 $x$ を超えない最大の整数を表す)。一方、 $(p-k)q$ より上にある数の個数は、 $\left[\dfrac{(p-k)q}{p}\right]$ と書ける。ガウス記号の中を足すと $q$ である。 $kq$ は $p$ で割り切れないので、どちらも整数ではなく、小数部分を切り捨てることになるため和は $1$ 減る。よって、両者の和は $q-1$ である。
これより
\begin{eqnarray}
& & \sum_{k=1}^{p-1} \left[\dfrac{kq}{p}\right] \\[5pt]
&=& \frac{1}{2} \left(\sum_{k=1}^{p-1} \left[\dfrac{kq}{p}\right]+\sum_{k=1}^{p-1} \left[\dfrac{(p-k)q}{p}\right] \right) \\[5pt]
&=& \frac{1}{2} \sum_{k=1}^{p-1} (q-1) \\[5pt]
&=& \frac{(p-1)(q-1)}{2}
\end{eqnarray}となるので、$S$ に属さない $0$ 以上の整数の個数は、$\dfrac{(p-1)(q-1)}{2}$ 個 …(答)
解説
$p=7,\ q=5$ という具体的なケースで考えてみます。まず、数を以下のように並べていきます。7個ごとに次の段に移ります。
\begin{array}{ccccccc} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & \\[5pt] & 7 & 8 & 9 & 10 & 11 & 12 & 13 & \\[5pt] & 14 & 15 & 16 & 17 & 18 & 19 & 20 & \\[5pt] & 21 & 22 & 23 & 24 & 25 & 26 & 27 & \\[5pt] & 28 & 29 & 30 & 31 & 32 & 33 & 34 & \\[5pt] & 35 & 36 & 37 & 38 & 39 & 40 & 41 & \\[5pt] \end{array}こうすると、それぞれの列は、7で割った余りが同じ数が並びます。
次に、$0q=0$ は $S$ に属するので消します。それより下にある数も、 $mp+0q$ の形で書けるから $S$ に属するので消します。
\begin{array}{ccccccc} & \cancel{0} & 1 & 2 & 3 & 4 & 5 & 6 & \\[5pt] & \cancel{7} & 8 & 9 & 10 & 11 & 12 & 13 & \\[5pt] & \cancel{14} & 15 & 16 & 17 & 18 & 19 & 20 & \\[5pt] & \cancel{21} & 22 & 23 & 24 & 25 & 26 & 27 & \\[5pt] & \cancel{28} & 29 & 30 & 31 & 32 & 33 & 34 & \\[5pt] & \cancel{35} & 36 & 37 & 38 & 39 & 40 & 41 & \\[5pt] \end{array}同じ要領で、 $1q=5$ とそれより下を消し、 $10,15,20,25,30$ に対しても同じようにします。そうすると、以下のようになります。
\begin{array}{ccccccc} & \cancel{0} & 1 & 2 & 3 & 4 & \cancel{5} & 6 & \\[5pt] & \cancel{7} & 8 & 9 & \cancel{10} & 11 & \cancel{12} & 13 & \\[5pt] & \cancel{14} & \cancel{15} & 16 & \cancel{17} & 18 & \cancel{19} & \cancel{20} & \\[5pt] & \cancel{21} & \cancel{22} & 23 & \cancel{24} & \cancel{25} & \cancel{26} & \cancel{27} & \\[5pt] & \cancel{28} & \cancel{29} & \cancel{30} & \cancel{31} & \cancel{32} & \cancel{33} & \cancel{34} & \\[5pt] & \cancel{35} & \cancel{36} & \cancel{37} & \cancel{38} & \cancel{39} & \cancel{40} & \cancel{41} & \\[5pt] \end{array}上を見ると、どの列も、あるところからは必ず消えることがわかります。これはたまたまではなく、解答の序盤に書いた「$0q,1q,\cdots,(p-1)q$ をそれぞれ $p$ で割った余りは互いに異なる」ことから、必ず起こります。
また、これ以上、 $35,40, 45,\cdots$ に対して消そうとしても、新たに消えるものはありません。例えば、 $45$ より下は、 $10$ より下を消したときにすでに消しているからです。なので、消える場所のそれぞれ一番上の数は、$0,5,10,15,20,25,30$ であることがわかります(解答の中盤で書いている内容です)。これより上の数は必ず残るので、これらの個数を数えれば答えだ、ということです。
例えば、 $10$ より上と $25$ より上の数を考えると、各段に $7$ 個の数があることから、それぞれ $\left[\dfrac{10}{7}\right]$ 個と $\left[\dfrac{25}{7}\right]$ 個であることがわかります。どちらもガウス記号の中は整数ではなく、ガウス記号の中同士の和は $5$ なので、以下のようになります。

上の画像からもわかる通り、$\left[\dfrac{10}{7}\right] +\left[\dfrac{25}{7}\right]=4$ となります。これは一般的に、 $\left[\dfrac{kq}{p}\right]+\left[\dfrac{(p-k)q}{p}\right]=q-1$ と表せます。これが解答の終盤で書いている内容です。これを用いて、全部の個数を足せば、 $\dfrac{(p-1)(q-1)}{2}$ となります。