aはbの倍数，a+1はb+1の倍数 /「算数にチャレンジ!!」第1045問

問題概略
とりあえず答えを出す
中身を見てみる
中国式剰余定理

問題概略

整数 $a$ , $b$ は次の条件をみたしています。このような $(a,\, b)$ は何組あるでしょうか。

ともに 1 以上 100 以下

$a$ は $b$ よりも大きい

$a$ は $b$ の倍数

$a+1$ は $b+1$ の倍数

http://www.sansu.org/used-html/index1045.html

解説の pdf も作りました。きれいなレイアウトで読みたい方はこちらをどうぞ。

drive.google.com

とりあえず答えを出す

$a$ , $b$ の条件は次のようになります。
\begin{align*}
1\leqq a\leqq 100,\, 1\leqq b\leqq 100,\, a>b,\, b\mid a,\, b+1 \mid a+1
\end{align*}

これをみたす $(a,\, b)$ の個数を mathematica で調べました。答えは「85 組」です。

In[]:= AbsoluteTiming[
   lst = Tuples[Range@100, 2];
   isOK[{a_, b_}] := (a > b) && Divisible[a, b] && 
     Divisible[a + 1, b + 1];
   ans = Length@Select[lst, isOK]]

Out[]= {0.01407, 85}

中身を見てみる

条件をみたす $(a,\, b)$ を見てみましょう。
\begin{align*}
&(3, 1),\, (5, 1),\, (7, 1),\, (8, 2),\, (9, 1),\, (11, 1),\, (13, 1),\, (14, 2),\, (15, 1),\\
&(15, 3),\, (17, 1),\, (19, 1),\, (20, 2),\, (21, 1),\, (23, 1),\, (24, 4),\, (25, 1),\, (26, 2),\\
&(27, 1),\, (27, 3),\, (29, 1),\, (31, 1),\, (32, 2),\, (33, 1),\, (35, 1),\, (35, 5),\, (37, 1),\\
&(38, 2),\, (39, 1),\, (39, 3),\, (41, 1),\, (43, 1),\, (44, 2),\, (44, 4),\, (45, 1),\, (47, 1),\\
&(48, 6),\, (49, 1),\, (50, 2),\, (51, 1),\, (51, 3),\, (53, 1),\, (55, 1),\, (56, 2),\, (57, 1),\\
&(59, 1),\, (61, 1),\, (62, 2),\, (63, 1),\, (63, 3),\, (63, 7),\, (64, 4),\, (65, 1),\, (65, 5),\\
&(67, 1),\, (68, 2),\, (69, 1),\, (71, 1),\, (73, 1),\, (74, 2),\, (75, 1),\, (75, 3),\, (77, 1),\\
&(79, 1),\, (80, 2),\, (80, 8),\, (81, 1),\, (83, 1),\, (84, 4),\, (85, 1),\, (86, 2),\, (87, 1),\\
&(87, 3),\, (89, 1),\, (90, 6),\, (91, 1),\, (92, 2),\, (93, 1),\, (95, 1),\, (95, 5),\, (97, 1),\\
&(98, 2),\, (99, 1),\, (99, 3),\, (99, 9)
\end{align*}

$b$ が非常に小さいのがわかると思います。 $b\leqq 9$ を証明します。

倍数条件から $x$ , $y$ を 2 以上の自然数として $a=xb$ , $a+1=y(b+1)$ とおけます。
$a$ を消去します。
\begin{align*}
xb+1=y(b+1)\quad \therefore (x-y)b=y-1
\end{align*}

右辺は正なので左辺も正です。 $b$ が 10 以上のとき $y-1$ も 10 以上で， $y$ は 11 以上になります。

しかし，このとき $a+1=y(b+1)$ は 101 を超えてしまうので不適。 $b$ は 9 以下です。

中国式剰余定理

倍数条件から $a$ は「 $b$ で割ると余り 0」「 $b+1$ で割ると余り $b$ 」の数です。
これをみたす自然数の最小値は $b$ です。

また， $b$ と $b+1$ は互いに素なので， $a$ を $b$ と $b+1$ で割った余りの組は周期 $b(b+1)$ です。

$a$ の一般形は次のようになります。 $k$ は整数です。
\begin{align*}
a=b+kb(b+1)
\end{align*}

$a>b$ より $k$ の下限は 1。上限は $a\leqq 100$ から求められます。
\begin{align*}
b+kb(b+1) \leqq 100\quad \therefore k\leqq \frac{100-b}{b(b+1)}
\end{align*}

各 $b$ に対する $a$ の個数は $\left\lfloor \frac{100-b}{b(b+1)} \right\rfloor$ 個で，これの和が答えです。
\begin{align*}
\sum_{b=1}^9 \left\lfloor \frac{100-b}{b(b+1)} \right\rfloor &=49+16+8+4+3+2+1+1+1\\
&=85
\end{align*}

variee.hatenablog.com