京大文系数学2026 第3問～フロベニウスの硬貨交換問題

更新 2026/03/02

京大文系数学2026 第3問

$p$ は $3$ より大きい素数とする。

$2p$ 以上の整数 $N$ は， $0$ 以上の整数 $m$ と $0$ 以上の整数 $n$ を用いて $N = 3 m + pk$ と表すことができることを示せ。
$0$ 以上の整数 $m$ と $0$ 以上の整数 $n$ を用いて $N = 3 m + pk$ と表すことができないような0以上の整数 Nの個数を求めよ。

この記事では京大文系数学2026 第3問およびその背景について解説します。

解答

(1)NNN が 333 の倍数なら考えることはありません。それ以外の場合，どうなっているのか調べてみましょう。
p=5p = 5p=5 の場合，2p+12p+12p+1 は
11=6+5=3⋅2+5⋅1
11 = 6+5 = 3 \cdot 2 + 5 \cdot 1 
11=6+5=3⋅2+5⋅1
と表されますね。今回は (2p+1)−p(2p+1) - p(2p+1)−p が3の倍数になったことがポイントです。
N≡p (mod 3)N \equiv p \ (\mathrm{mod} \ 3)N≡p (mod 3) であれば N−p=3⋅(正の整数)N - p = 3 \cdot (\text{正の整数})N−p=3⋅(正の整数) と表されるのでOKというワケです。
今，NNN も ppp も 333 の倍数ではないときを考えています。そのため，N≡p (mod 3)N \equiv p \ (\mathrm{mod} \ 3)N≡p (mod 3)  ではない場合，代わりに N≡2p (mod 3)N \equiv 2p \ (\mathrm{mod} \ 3)N≡2p (mod 3) になります。特に今回 N≧2pN \geqq 2pN≧2p であるため N−2p>0N - 2p > 0N−2p>0 となり，確実に N−2p=3⋅(正の整数)N - 2p = 3 \cdot (\text{正の整数})N−2p=3⋅(正の整数) と表されます。
333 で割った余りは 000，111，222 という3択です。今回，余りが 000 の場合は自明であるため考える必要がなく，本質的に議論は2択に絞られ，シンプルな論証が可能になります。
(1)
以下，p≡1 (mod 3)p \equiv 1 \ (\mathrm{mod}\ 3)p≡1 (mod 3) の場合を考える。このとき，ある正整数 qqq が存在して p=3q+1p = 3q + 1p=3q+1 と表される。
N≡0 (mod 3)N \equiv 0 \ (\mathrm{mod}\ 3)N≡0 (mod 3) の場合

ある正整数 mmm があって N=3m+p⋅0N = 3m + p \cdot 0N=3m+p⋅0 と表されるため，この場合，命題は従う。
N≡1 (mod 3)N \equiv 1 \ (\mathrm{mod}\ 3)N≡1 (mod 3) の場合

ある正整数 MMM が存在して N=3M+1N = 3M + 1N=3M+1 と表される。このとき N−p=3(M−q)N - p = 3(M-q)N−p=3(M−q) である。今，N≧2pN \geqq 2pN≧2p であるため，M−q>0M-q > 0M−q>0 である。

以上の議論より NNN は
N=3(M−q)+p⋅1
N = 3(M-q) + p \cdot 1
N=3(M−q)+p⋅1
と表され，この場合，命題は従う。
N≡2 (mod 3)N \equiv 2 \ (\mathrm{mod}\ 3)N≡2 (mod 3) の場合

ある正整数 MMM が存在して N=3M+2N = 3M + 2N=3M+2 と表される。このとき N−2p=3(M−2q)N - 2p = 3(M-2q)N−2p=3(M−2q) である。今，N≧2pN \geqq 2pN≧2p であるため，M−2q>0M-2q > 0M−2q>0 である。

以上の議論より NNN は
N=3(M−2q)+p⋅2
N = 3(M-2q) + p \cdot 2
N=3(M−2q)+p⋅2
と表され，この場合，命題は従う。
p≡2 (mod 3)p \equiv 2 \ (\mathrm{mod}\ 3)p≡2 (mod 3) の場合，2と3の議論をそれぞれ入れ替えることで，同様に示される。
もし 333 ではなく 555 の場合は，4通りのパターン分けが必要になっていました。
(2)2p2p2p 未満の数のなかには，どれくらい「書けない」数が出てくるのでしょうか？
p=11p = 11p=11 で考えてみると
1,2,4,5,7,8,10,13,16,19
1,2,4,5,7,8,10,13,16,19
1,2,4,5,7,8,10,13,16,19
の 101010 個となります。
p=13p = 13p=13 で考えてみると
1,2,4,5,7,8,10,11,14,17,20,23
1,2,4,5,7,8,10,11,14,17,20,23
1,2,4,5,7,8,10,11,14,17,20,23
の 121212 個となります。
他にも実験してみると p−1p-1p−1 個であることが予想されます。これをどのように論証するのが良いでしょうか？
見比べてみましょう。ppp を越えるまでは同じように 1,2,4,5,⋯1,2,4,5, \cdots1,2,4,5,⋯ と続きます。他方，ppp を越えると様子が変わってきますが，よく見るとどちらも 333 個おきに登場します。この観察から ppp を区切りに場合分けしてみるのがよさそうです。
(2)
(1) より 2p−12p-12p−1 以下の整数のみ考えればよい。
1≦N≦p−11 \leqq N \leqq p -11≦N≦p−1 の場合

  333 の倍数ではない整数の個数を求めればよい。
p≡1 (mod 3)p \equiv 1 \ (\mathrm{mod} \ 3)p≡1 (mod 3) の場合

p−1≡0 (mod 3)p-1 \equiv 0 \ (\mathrm{mod} \ 3)p−1≡0 (mod 3) であるため，333 の倍数ではない整数は
p−13×2
\dfrac{p-1}{3} \times 2
3p−1​×2
個存在する。
p≡2 (mod 3)p \equiv 2 \ (\mathrm{mod} \ 3)p≡2 (mod 3) の場合

p−2≡0 (mod 3)p-2 \equiv 0 \ (\mathrm{mod} \ 3)p−2≡0 (mod 3) であるため，333 の倍数ではない整数は
p−23×2+1
\dfrac{p-2}{3} \times 2 + 1
3p−2​×2+1
個存在する。
p+1≦N≦2p−1p+1 \leqq N \leqq 2p-1p+1≦N≦2p−1 の場合
p≡1 (mod 3)p \equiv 1 \ (\mathrm{mod} \ 3)p≡1 (mod 3) の場合

NNN が 333 の倍数である場合は 3m3m3m，N≡1 (mod 3)N \equiv 1 \ (\mathrm{mod} \ 3)N≡1 (mod 3) の場合は 3m+p⋅13m + p \cdot 13m+p⋅1 と表される。よって N≡2 (mod 3)N \equiv 2 \ (\mathrm{mod} \ 3)N≡2 (mod 3) となる NNN の個数を数えればよい。

p+1≡2 (mod 3)p+1 \equiv 2 \ (\mathrm{mod} \ 3)p+1≡2 (mod 3)，2p−1≡1 (mod 3)2p-1 \equiv 1 \ (\mathrm{mod} \ 3)2p−1≡1 (mod 3) であるため，N≡2 (mod 3)N \equiv 2 \ (\mathrm{mod} \ 3)N≡2 (mod 3) となる NNN は 
2p−(p+1)3=p−13
\dfrac{2p- (p+1)}{3} = \dfrac{p-1}{3}
32p−(p+1)​=3p−1​
個存在する。
p+1≦N≦2p−1p+1 \leqq N \leqq 2p-1p+1≦N≦2p−1 の場合

NNN が 333 の倍数である場合は 3m3m3m，N≡2 (mod 3)N \equiv 2 \ (\mathrm{mod} \ 3)N≡2 (mod 3) の場合は 3m+p⋅13m + p \cdot 13m+p⋅1 と表される。よって N≡1 (mod 3)N \equiv 1 \ (\mathrm{mod} \ 3)N≡1 (mod 3) となる NNN の個数を数えればよい。

p+1≡0 (mod 3)p+1 \equiv 0 \ (\mathrm{mod} \ 3)p+1≡0 (mod 3)，2p−1≡0 (mod 3)2p-1 \equiv 0 \ (\mathrm{mod} \ 3)2p−1≡0 (mod 3) であるため，N≡2 (mod 3)N \equiv 2 \ (\mathrm{mod} \ 3)N≡2 (mod 3) となる NNN は 
2p−1−(p+1)3=p−23
\dfrac{2p-1 - (p+1)}{3} = \dfrac{p-2}{3}
32p−1−(p+1)​=3p−2​
個存在する。
p≡1 (mod 3)p \equiv 1 \ (\mathrm{mod} \ 3)p≡1 (mod 3) の場合，求める個数は 
p−13×2+p−13=p−1
\dfrac{p-1}{3} \times 2 + \dfrac{p-1}{3} = p-1
3p−1​×2+3p−1​=p−1
p≡2 (mod 3)p \equiv 2 \ (\mathrm{mod} \ 3)p≡2 (mod 3) の場合，求める個数は
p−23×2+1+p−23=p−1
\dfrac{p-2}{3} \times 2 + 1 + \dfrac{p-2}{3} = p-1
3p−2​×2+1+3p−2​=p−1
以上より p−1p-1p−1 個である。

背景：フロベニウスの硬貨交換問題

一般に次の事実が知られています。

正の整数 $A$ と $B$ は互いに素であるとする。

0以上の整数 $m,\ n$ を用いて $Am + Bn$ と表すことができない最大の整数は $AB- A -B$ であり，表すことができない正の整数の個数は $\dfrac{(A-1)(B-1)}{2}$ 個である。

このように2整数 $A,\ B$ により $Am+Bn$ と表される数を調べる問題のことをフロベニウスの硬貨交換問題（シルベスターの切手問題）といいます。また，最後の定理（表すことができない正の整数の個数を与える公式）をシルベスターの定理ということがあります。

詳しくはフロベニウスの硬貨交換問題を読んでみてください。

知る人ぞ知る有名問題です。今回は $3$ を固定していることで，受験問題としても見通しのよい良問になっていると思いました。