基礎問題集
数学A 整数問題「整数問題」の問題59 解説
数学Aの整数問題「整数問題」にある問題59の基礎問題と解説ページです。問題と保存済み解説を公開し、ログイン後はAI質問と学習履歴も利用できます。
MathGrAIl の基礎問題集にある公開問題ページです。ログイン前でも問題と保存済み解説を確認でき、ログイン後はAI質問と学習履歴の保存を利用できます。
- 基礎問題の問題画像と保存済み解説を公開
- ログイン後にAI質問で復習
- ログイン後に学習履歴を保存
解説
方針・初手
(1) は、同じ余りをもつものが2つあると仮定して合同式を作り、$p$ と $q$ が互いに素であることを用いる。
(2) は、(1) により $x-q,x-2q,\ldots,x-pq$ の中に $p$ で割り切れるものが存在することを使う。そのときの番号を $b$ とおけば、$x=pa+qb$ の形が得られる。
解法1
まず (1) を示す。
$1 \leq i<j \leq p$ とし、$x-iq$ と $x-jq$ を $p$ で割った余りが等しいと仮定する。このとき
$$ x-iq \equiv x-jq \pmod p
$$
であるから、
$$ (j-i)q \equiv 0 \pmod p
$$
すなわち
$$ p \mid (j-i)q
$$
である。
ここで $p$ と $q$ は互いに素なので、ユークリッドの補題より
$$ p \mid (j-i)
$$
が成り立つ。
しかし、$1 \leq i<j \leq p$ であるから
$$ 0<j-i<p
$$
であり、$p$ が $j-i$ を割り切ることはできない。これは矛盾である。
したがって、$x-q,x-2q,\ldots,x-pq$ を $p$ で割った余りはすべて相異なる。
次に (2) を示す。
$p$ で割った余りは $0,1,\ldots,p-1$ の $p$ 種類である。(1) より、$p$ 個の整数
$$ x-q,\ x-2q,\ \ldots,\ x-pq
$$
を $p$ で割った余りはすべて相異なる。よって、これらの余りは $0,1,\ldots,p-1$ のすべてである。
したがって、ある整数 $b$ が
$$ 1 \leq b \leq p
$$
を満たし、
$$ x-bq \equiv 0 \pmod p
$$
となる。
よって、ある整数 $a$ を用いて
$$ x-bq=pa
$$
と表せる。したがって
$$ x=pa+qb
$$
である。
あとは $a,b$ が正の整数であることを確認する。すでに $1 \leq b \leq p$ であるから、$b$ は正の整数である。
また、仮定より $x>pq$ であり、$b \leq p$ だから
$$ x-bq \geq x-pq>0
$$
である。したがって
$$ a=\frac{x-bq}{p}>0
$$
となり、$a$ も正の整数である。
以上より、$pq$ より大きな任意の整数 $x$ は、適当な正の整数 $a,b$ を用いて
$$ x=pa+qb
$$
と表せる。
解説
(1) は「互いに素なら、$q$ をかけることによって $p$ での余りの重複は起こらない」という事実を示している。
(2) では、$x-q,x-2q,\ldots,x-pq$ の中から $p$ の倍数を1つ見つければよい。その番号を $b$ とすると、$x-bq$ が $p$ の倍数になるので、自然に
$$ x-bq=pa
$$
とおける。
ここで重要なのは、$a$ が正になるかどうかである。$b$ は最大でも $p$ なので、$x>pq$ なら
$$ x-bq \geq x-pq>0
$$
となり、$a>0$ が保証される。このため、条件 $x>pq$ が有効に働いている。
答え
**(1)**
任意の整数 $x$ に対して、$x-q,x-2q,\ldots,x-pq$ を $p$ で割った余りはすべて相異なる。
**(2)**
$pq$ より大きな任意の整数 $x$ は、適当な正の整数 $a,b$ を用いて
$$ x=pa+qb
$$
と表せる。