数学A 整数問題 問題 59 解説

方針・初手

(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 $$

と表せる。