整数の性質の問題

1. 特殊解を見つける

$13=8\cdot 1+5,8=5\cdot 1+3,5=3\cdot 1+2,3=2\cdot 1+1$ より、$13$ と $8$ は互いに素です。

$y$ が整数になるような $x$ を探すため、$8$ を法として考えます。

• $13\equiv 5(\mathrm{mod}8)$
• $1001=8\cdot 125+1$ より $1001\equiv 1(\mathrm{mod}8)$

したがって $5x\equiv 1(\mathrm{mod}8)$ です。$5\cdot 5=25\equiv 1(\mathrm{mod}8)$ なので $x\equiv 5(\mathrm{mod}8)$ となります。

$x=5$ のとき $8y=1001-65=936$ より $y=117$ です。よって $(x,y)=(5,117)$ は 1 つの解です。実際、$13\cdot 5+8\cdot 117=65+936=1001$ が成り立ちます。

2. 一般解を求める

$$13x+8y=1001,13\cdot 5+8\cdot 117=1001$$

の辺々を引くと

$$13(x-5)=-8(y-117)$$

となります。$13$ と $8$ は互いに素なので、$x-5$ は $8$ の倍数です。$x-5=8k$（$k$ は整数）とおくと、$13\cdot 8k=-8(y-117)$ より $y-117=-13k$ です。よって

$$x=8k+5,y=117-13k(k\text{ は整数})$$

3. 正の整数となる条件

• $x>0$: $8k+5>0$ より $k>-\frac{5}{8}$。$k$ は整数なので $k\geqq 0$。
• $y>0$: $117-13k>0$ より $k<9$。$k$ は整数なので $k\leqq 8$。

したがって $k=0,1,2,\dots ,8$ の $9$ 個です。

(確認) $k=0$ のとき $(5,117)$、$k=8$ のとき $(69,13)$ で、$13\cdot 69+8\cdot 13=897+104=1001$ となり正しく成り立ちます。

よって、求める組の数は $9$ 組です。

$13x+8y=1001$ を mod 8 で考える。$1001=8\cdot 125+1$ なので $13x\equiv 5x\equiv 1(\mathrm{mod}8)$。$5\cdot 5=25\equiv 1$ より $x\equiv 5(\mathrm{mod}8)$。

そこで $x=8k+5$ とおくと、$y=(1001-13(8k+5))/8=(936-104k)/8=117-13k$。

$x>0$ より $k\ge 0$。$y>0$ より $117-13k>0$ なので $k<9$、つまり $k\le 8$。

よって $k=0,1,\dots ,8$ の 9 組。

検算: $k=8$ のとき $(x,y)=(69,13)$ で $13\cdot 69+8\cdot 13=897+104=1001$ で成立。$k=9$ のとき $(77,0)$ となり $y$ が正でないので不適。

答え: 9 組