https://spherical-harmonics.hateblo.jp/entry/Kyodai/2026/Bunkei

2026.03.05.00:23:15記

[3] $p$ は $3$ より大きい素数とする．

(1) $2p$ 以上の整数 $N$ は， $0$ 以上の整数 $m$ と $0$ 以上の整数 $k$ を用いて
$N = 3 m + pk$
と表すことができることを示せ．

(2) $0$ 以上の整数 $m$ と $0$ 以上の整数を用いて
$N = 3 m + pk$
と表すことができないような $0$ 以上の整数 $N$ の個数を求めよ．

本問のテーマ

フロベニウスの硬貨問題（シルベスターの(閉形式)定理）

2026.03.15.15:02:52記
$p$ と $3$ が互いに素であることが重要であり， $p$ が素数かどうかは重要ではありません．

[大人の解答]
$3$ と $p$ は互いに素な正の整数であるから，フロベニウスの硬貨問題の一般論により，
「非負整数 $m，k$ を用いて $3m+pk$ の形で表せない最大の整数は $3p-p-3=2p-3$ であり，表すことのできない整数は $\dfrac{(3-1)(p-1)}{2}$ $p-1$ 個（シルベスターの定理）である．

(1) $2p\geqq 2p-3$ により $2p$ 以上の整数 $N$ は， $0$ 以上の整数 $m$ と $0$ 以上の整数 $k$ を用いて $N = 3 m + pk$ と表すことができる．

(2) シルベスターの定理により $\dfrac{(3-1)(p-1)}{2}$ $=p-1$ 個である．

結局，本問はフロベニウスの硬貨問題の一般論とシルベスターの定理の証明に近いものを具体的な $3，p$ について行うことになりますが，(1)の誘導の与え方を考えると，(2)は $k=0，1$ で場合分けをすることを期待していると考えられます．

[解答]
(1) $p$ を $3$ で割った余りを $r$ とし， $p=3a+r$ とおく．このとき $p$ は $3$ より大きな素数であるから $3$ は互いに素となり， $r=1$ または $r=2$ である．

(i) $r=1$ のとき：
$2p$ 以上の整数 $N$ を $3$ で割った余りが $1$ ならば $N-p(\geqq p\geqq 0)$ は $3$ で割り切れるので，その商を $m$ とすれば $m\geqq 0$ で $N=3m+p$ と表すことができる．また $2p$ 以上の整数 $N$ を $3$ で割った余りが $2$ ならば $N-2p(\geqq 0)$ は $3$ で割り切れるので，その商を $m$ とすれば $m\geqq 0$ で $N=3m+2p$ と表すことができる．

(ii) $r=2$ のとき：
$2p$ 以上の整数 $N$ を $3$ で割った余りが $2$ ならば $N-p(\geqq p\geqq 0)$ は $3$ で割り切れるので，その商を $m$ とすれば $m\geqq 0$ で $N=3m+p$ と表すことができる．また $2p$ 以上の整数 $N$ を $3$ で割った余りが $1$ ならば $N-2p(\geqq 0)$ は $3$ で割り切れるので，その商を $m$ とすれば $m\geqq 0$ で $N=3m+2p$ と表すことができる．

よって全ての場合が尽くされたので， $2p$ 以上の整数 $N$ は， $0$ 以上の整数 $m$ と $0$ 以上の整数 $k$ を用いて $N=3m+pk$ と表すことができる．

(2)(i) $r=1$ のとき：
$0\leqq N\leqq p-1$ で表せるものは $3$ の倍数で $0，3，…，p-1=3a$ の $a+1$ 個だから表せないものは $p-a-1$ 個である．また $p\leqq N\leqq 2p-1$ で表せないものは $3$ で割って $2$ 余るもので $p+1=3a+2，3a+5，…，2p-3=6a-1$ の $a$ 個である．よって合計 $p-1$ 個である．

(2)(i) $r=2$ のとき：
$0\leqq N\leqq p-1$ で表せるものは $3$ の倍数で $0，3，…，p-1=3a$ の $a+1$ 個だから表せないものは $p-a-1$ 個である．また $p\leqq N\leqq 2p-1$ で表せないものは $3$ で割って $1$ 余るもので $p+2=3a+4，3a+7，…，2p-3=6a+1$ の $a$ 個である．よって合計 $p-1$ 個である．

以上から求める個数は $p-1$ 個である．

表すことのできない最大の整数は(2)(i)(ii)から $2p-3$ であることがわかります．

一般化すると，正の整数 $p，q$ が互いに素なとき， $p，2p，…，(q-1)p$ を $q$ で割った余りは全て異なり，その集合は $\{1，2，…，q-1\}$ と一致することから， $N\geqq (q-1)p$ であれば $N-ip\geqq 0$ が $q$ の倍数となるような $i$ を選ぶことができることがわかるので， $N=pk+qm$ （ $k，m$ は非負整数）と表せることがわかります．

また， $p$ を $q$ で割った余りが $r$ のとき， $(q-1)p$ を $q$ で割った余りは $q-r$ となるので（ $(q-1)p\equiv -r$ ( $\mbox{mod}\, q$ )）， $(q-2)p\leqq N\leqq (q-1)p-1$ で表せないものは $q$ で割って $q-r$ 余るものとなり，その最大のものは $(q-1)p-q=pq-p-q$ となります．

シルベスターの(閉形式)定理の証明は母関数による証明が楽です．
$f(x)=(1+x^p+x^{2p}+x^{3p}+\cdots)(1+x^q+x^{2q}+x^{3q}+\cdots)$
の $x^{N}$ の係数が $0$ でなければ $N=pk+qm$ （ $k，m$ は非負整数）と表すことができます．

例えば $p=5，q=3$ のとき
$f(x)=(1+x^5+x^{10}+x^{15}+\cdots+)(1+x^3+x^{6}+x^{9}+x^{12}+x^{15}+\cdots)$
$=1+x^3+x^5+x^6+x^8+x^9+x^{10}+x^{11}+x^{12}+x^{13}+x^{14}+2x^{15}+\cdots$
となり，連続する $3$ つの係数が $0$ でなければ帰納的にその続きの係数も $0$ でなくなるので，
$N=5k+3m$ （ $k，m$ は非負整数）と表すことができない最大の整数は $7$ であることがわかります．

（シルベスターの(閉形式)定理の証明）
$0\leqq N\lt pq$ において $N=pk+qm$ （ $k，m$ は非負整数）と表すことができない整数の個数を数えれば十分で，それは
$g(x)=(1+x^p+x^{2p}+\cdots+x^{pq})(1+x^q+x^{2q}+\cdots +x^{pq}）$
に登場しない $x^N$ （ $0\leqq N\lt pq$ ）の個数に等しい．

$2pq$ 次式 $g(x)$ は， $p，q$ が互いに素であるから，展開係数は $2x^{pq}$ を除いて全て $1$ となるので， $(p+1)(q+1)-1$ 個の項の和となる．また， $x^t$ と $x^{2pq-t}$ の係数は等しいので，
$x^N$ （ $N=0，1，…，pq-1$ ）で係数が $0$ でないものは $\dfrac{(p+1)(q+1)-1-1}{2}$ 個となる．

よって求める個数は $pq-\dfrac{(p+1)(q+1)-1-1}{2}=\dfrac{2pq-(p+1)(q+1)+2}{2}=\dfrac{(p-1)(q-1)}{2}$ 個となる．