整数の性質の問題

1. 特殊解を 1 つ見つける

$13x+8y=300$ の両辺を $8$ で割った余りを考える。$13\equiv 5(\mathrm{mod}8)$、$300=8\cdot 37+4$ より
$$5x\equiv 4(\mathrm{mod}8)$$
となる。$5\cdot 5=25\equiv 1(\mathrm{mod}8)$ なので、両辺に $5$ を掛けると $x\equiv 20\equiv 4(\mathrm{mod}8)$ である。

$x=4$ のとき $8y=300-52=248$ より $y=31$ となる。よって $(x,y)=(4,31)$ は解である。実際、$13\cdot 4+8\cdot 31=52+248=300$ が成り立つ。

2. 一般解を求める

$13x+8y=300$ から $13\cdot 4+8\cdot 31=300$ を辺々引くと
$$13(x-4)=-8(y-31)$$
となる。$13$ と $8$ は互いに素なので、$x-4$ は $8$ の倍数である。$x-4=8k$（$k$ は整数）とおくと、$13\cdot 8k=-8(y-31)$ より $y-31=-13k$ となる。よって整数解は
$$x=8k+4,y=31-13k(k\text{ は整数})$$
である。

3. 正の整数解を絞る

• $x>0$ より $8k+4>0$、すなわち $k>-\frac{1}{2}$ なので $k\ge 0$
• $y>0$ より $31-13k>0$、すなわち $k<\frac{31}{13}=2.38\cdots$ なので $k\le 2$

したがって $k=0,1,2$ であり、正の整数解は次の 3 組である。

• $k=0$：$(4,31)$、$xy=124$
• $k=1$：$(12,18)$、$xy=216$
• $k=2$：$(20,5)$、$xy=100$

4. 結論

$xy$ の最大値は $216$ である（$(x,y)=(12,18)$ のとき）。

$13x+8y=300$ を $8$ で割った余りを考える。$13x\equiv 5x$、$300\equiv 4(\mathrm{mod}8)$ より $5x\equiv 4(\mathrm{mod}8)$。両辺に $5$ を掛けると $25x\equiv 20$、すなわち $x\equiv 4(\mathrm{mod}8)$。

$y>0$ より $13x<300$ なので $x\le 23$。よって $x=4,12,20$。

• $x=4$ のとき $y=(300-52)/8=31$、$xy=124$
• $x=12$ のとき $y=(300-156)/8=18$、$xy=216$
• $x=20$ のとき $y=(300-260)/8=5$、$xy=100$

最大は $(x,y)=(12,18)$ のときで、$xy=216$。

検算: $13\cdot 12+8\cdot 18=156+144=300$ で条件を満たす。