1から1000までの自然数全体の集合を$M$とする。$15!$の素因数分解を $15! = p_1^{m_1} p_2^{m_2} p_3^{m_3} p_4^{m_4} p_5^{m_5} p_6^{m_6}$と表す。ただし、$p_1, p_2, \dots, p_6$は小さい順に並べた素数、$m_1, m_2, \dots, m_6$は自然数とする。 (1) $p_4$と$p_6$を求める。 (2) $m_1$, $m_2$, $m_3$を求める。 (3) $p_5 x - p_6 y = 1$が成り立つような$M$の要素の組$(x,y)$の個数、および$x$が最小と最大のものを求める。 (4) $M$の要素のうち、$p_4 p_5$と互いに素なものの個数、$p_4 p_5 p_6$と互いに素なものの個数を求める。

1. 問題の内容

1から1000までの自然数全体の集合を$M$とする。$15!$の素因数分解を $15! = p_1^{m_1} p_2^{m_2} p_3^{m_3} p_4^{m_4} p_5^{m_5} p_6^{m_6}$と表す。ただし、$p_1, p_2, \dots, p_6$は小さい順に並べた素数、$m_1, m_2, \dots, m_6$は自然数とする。

(1) $p_4$と$p_6$を求める。

(2) $m_1$, $m_2$, $m_3$を求める。

(3) $p_5 x - p_6 y = 1$が成り立つような$M$の要素の組$(x,y)$の個数、および$x$が最小と最大のものを求める。

(4) $M$の要素のうち、$p_4 p_5$と互いに素なものの個数、$p_4 p_5 p_6$と互いに素なものの個数を求める。

2. 解き方の手順

(1)

$p_1, p_2, \dots, p_6$は小さい順に並べた素数なので、$p_1 = 2, p_2 = 3, p_3 = 5, p_4 = 7, p_5 = 11, p_6 = 13$。

よって、$p_4 = 7$、$p_6 = 13$。

(2)

$m_1$: 15!に含まれる2の個数

$m_1 = \lfloor\frac{15}{2}\rfloor + \lfloor\frac{15}{4}\rfloor + \lfloor\frac{15}{8}\rfloor = 7 + 3 + 1 = 11$

$m_2$: 15!に含まれる3の個数

$m_2 = \lfloor\frac{15}{3}\rfloor + \lfloor\frac{15}{9}\rfloor = 5 + 1 = 6$

$m_3$: 15!に含まれる5の個数

$m_3 = \lfloor\frac{15}{5}\rfloor + \lfloor\frac{15}{25}\rfloor = 3 + 0 = 3$

よって、$m_1 = 11$、$m_2 = 6$、$m_3 = 3$。

(3)

$11x - 13y = 1$の整数解を求める。

$11x - 13y = 1$

$11(6) - 13(5) = 66 - 65 = 1$

よって、$x = 6$, $y = 5$は特殊解の一つ。

一般解は$x = 6 + 13k, y = 5 + 11k$ ($k$は整数)。

$x$と$y$は1から1000までの自然数なので、$1 \leq 6 + 13k \leq 1000$、$1 \leq 5 + 11k \leq 1000$。

$-5 \leq 13k \leq 994$、$k$は整数なので、$-\frac{5}{13} \leq k \leq \frac{994}{13} \approx 76.46$

$-5 \leq 11k \leq 995$、$k$は整数なので、$-\frac{5}{11} \leq k \leq \frac{995}{11} \approx 90.45$

したがって、$0 \leq k \leq 76$。

$k$は77個あるので、解$(x,y)$は77個ある。

$x$が最小となるのは$k = 0$のときで、$x = 6$, $y = 5$。

$x$が最大となるのは$k = 76$のときで、$x = 6 + 13(76) = 6 + 988 = 994$, $y = 5 + 11(76) = 5 + 836 = 841$。

(4)

$p_4 p_5 = 7 \times 11 = 77$と互いに素な$M$の要素の個数は、1から1000までの自然数の中で、7の倍数でも11の倍数でもないものの個数。

7の倍数の個数は$\lfloor\frac{1000}{7}\rfloor = 142$。

11の倍数の個数は$\lfloor\frac{1000}{11}\rfloor = 90$。

77の倍数の個数は$\lfloor\frac{1000}{77}\rfloor = 12$。

$1000 - (142 + 90 - 12) = 1000 - 220 = 780$個。

$p_4 p_5 p_6 = 7 \times 11 \times 13 = 1001$と互いに素な$M$の要素の個数は、1から1000までの自然数の中で、7の倍数でも11の倍数でも13の倍数でもないものの個数。

13の倍数の個数は$\lfloor\frac{1000}{13}\rfloor = 76$。

7と11の倍数の個数は12（上記より）。

7と13の倍数の個数は$\lfloor\frac{1000}{91}\rfloor = 10$。

11と13の倍数の個数は$\lfloor\frac{1000}{143}\rfloor = 6$。

7と11と13の倍数の個数は$\lfloor\frac{1000}{1001}\rfloor = 0$。

$1000 - (142 + 90 + 76 - 12 - 10 - 6 + 0) = 1000 - (308 - 28) = 1000 - 280 = 720$個。

3. 最終的な答え

(1) $p_4 = 7$, $p_6 = 13$

(2) $m_1 = 11$, $m_2 = 6$, $m_3 = 3$

(3) $77$個。最小のものは$(x,y) = (6, 5)$。最大のものは$(x,y) = (994, 841)$。

(4) $780$個、$720$個。