$5m + 19$ と $4m + 18$ の最大公約数が $7$ となるような $100$ 以下の自然数 $m$ の個数を求める問題です。

1. 問題の内容

$5m + 19$ と $4m + 18$ の最大公約数が $7$ となるような $100$ 以下の自然数 $m$ の個数を求める問題です。

2. 解き方の手順

まず、$5m + 19$ と $4m + 18$ の最大公約数が $7$ であることから、これらの数は $7$ の倍数である必要があります。

したがって、$5m + 19 = 7k$、$4m + 18 = 7l$ と表せます ($k, l$ は自然数)。

$5m + 19$ と $4m + 18$ の最大公約数が $7$ である条件を利用するため、これらの式を組み合わせて $m$ を消去することを考えます。

$5(4m + 18) - 4(5m + 19) = 20m + 90 - 20m - 76 = 14$

$4m + 18 = 7l$より、$4m = 7l - 18$

$5m + 19 = 7k$より、$5m = 7k - 19$

$5(4m+18) - 4(5m+19) = 5(7l) - 5(18) - 4(7k) + 4(19) = 35l - 90 - 28k + 76 = 35l - 28k - 14 = 14$

$35l - 28k = 28$

$5l - 4k = 4$

$5l = 4k + 4 = 4(k+1)$

$l = \frac{4(k+1)}{5}$　ここで、$l$は整数であるので、$k+1$は$5$の倍数である必要がある。

$k+1 = 5n$ ($n$は自然数)とおける。$k = 5n - 1$

$5m + 19 = 7(5n - 1) = 35n - 7$

$5m = 35n - 26$

$m = 7n - \frac{26}{5}$

$m$は整数である必要があるので、先程の$5l - 4k = 4$を用いる

$4m + 18 = 7l$に、$l = \frac{4(k+1)}{5}$を代入すると、

$4m + 18 = 7(\frac{4(k+1)}{5})$

$20m + 90 = 28(k+1)$

$20m = 28k + 28 - 90 = 28k - 62$

$10m = 14k - 31$

$m = \frac{14k-31}{10}$

$m$が整数になるには、$14k-31$が$10$の倍数になればよい。

$14k-31 = 10p$ ($p$は整数)

$14k = 10p + 31$

$k=1,2,3,...$を代入していくと、$k=9$のとき、$14(9) = 126 = 10(9) + 36$より、$10p+31 = 126$より、$10p = 95$、$p=9.5$となり整数ではない。

$14k - 31$の一の位が$0$になればよいので、$4k$の一の位が$1$になる$k$を考える。$k=4, 9, 14, 19,...$

$k = 5q + 4$とおける。(qは0以上の整数)

$m = \frac{14(5q+4)-31}{10} = \frac{70q + 56 - 31}{10} = \frac{70q+25}{10} = 7q + \frac{5}{2}$

この式では$m$が整数にならない。

互除法を用いる。

$5m + 19 = a$

$4m + 18 = b$

$\gcd(a,b) = 7$

$a - b = m + 1$

$\gcd(b,a-b) = \gcd(4m+18, m+1) = 7$

$4(m+1) = 4m+4$

$4m + 18 - (4m+4) = 14$

$\gcd(m+1, 14) = 7$

よって、$m+1$ は $7$ の倍数でなければならない。 また、$m+1$ は $14$ の倍数ではない必要がある。

$m+1 = 7x$ と表せる ($x$ は自然数)。

このとき $m = 7x - 1$

$4m + 18 = 4(7x - 1) + 18 = 28x + 14 = 14(2x + 1)$

$5m + 19 = 5(7x - 1) + 19 = 35x + 14 = 7(5x + 2)$

したがって、$\gcd(4m + 18, 5m + 19) = 7$ となるためには、$2x+1$と$5x+2$の最大公約数が1または7でなければならない。

$x$が偶数のとき、$2x+1$は奇数、$5x+2$は偶数なので最大公約数は1

$x$が奇数のとき、$2x+1$は奇数、$5x+2$は奇数なので最大公約数はあり得る。

$m \le 100$ より、$7x - 1 \le 100$

$7x \le 101$

$x \le \frac{101}{7} \approx 14.4$

$x$ は $1$ から $14$ までの自然数。

$\gcd(m+1, 14) = 7$ より、$m+1$ は $14$ の倍数ではない必要がある。

$m+1 = 7x$ が $14$ の倍数ではないためには、$x$ が偶数であってはならない。したがって、$x$ は奇数である必要がある。

$x = 1, 3, 5, 7, 9, 11, 13$ の $7$ 個の奇数。

$x = 1$ のとき、$m = 6$

$x = 3$ のとき、$m = 20$

$x = 5$ のとき、$m = 34$

$x = 7$ のとき、$m = 48$

$x = 9$ のとき、$m = 62$

$x = 11$ のとき、$m = 76$

$x = 13$ のとき、$m = 90$

$m+1=7x$が$14$の倍数でないことを確認する。

$m+1 = 7, 21, 35, 49, 63, 77, 91$

これらはすべて$14$の倍数ではないので問題ない。

最終的な答えは7個。

3. 最終的な答え

7個