数学A 整数問題 問題 39 解説

方針・初手

$1$ から $p^m q^n$ までの整数のうち、$p$ または $q$ の倍数の個数を包除原理で数える。

その個数を $240$ とおくと、$p,q,m,n$ に関する整数方程式が得られる。特に $m \geqq 3$ より $p^2$ が $240$ を割ることに注目する。

解法1

$N=p^m q^n$ とおく。

$1$ から $N$ までの整数のうち、$p$ の倍数の個数は

$$ \frac{p^m q^n}{p}=p^{m-1}q^n $$

であり、$q$ の倍数の個数は

$$ \frac{p^m q^n}{q}=p^m q^{n-1} $$

である。

また、$p$ と $q$ は異なる素数であるから、$p$ と $q$ の両方の倍数、すなわち $pq$ の倍数の個数は

$$ \frac{p^m q^n}{pq}=p^{m-1}q^{n-1} $$

である。

よって、包除原理より

$$ p^{m-1}q^n+p^m q^{n-1}-p^{m-1}q^{n-1}=240 $$

である。左辺を因数分解すると、

$$ p^{m-1}q^{n-1}(q+p-1)=240 $$

となる。

ここで $m\geqq 3$ より $m-1\geqq 2$ であるから、左辺には $p^2$ が因数として含まれる。したがって $p^2$ は $240$ を割る。

$$ 240=2^4\cdot 3\cdot 5 $$

であるから、平方が $240$ を割る素数は $2$ のみである。よって

$$ p=2 $$

である。

このとき $p<q$ より、$q$ は奇素数である。方程式は

$$ 2^{m-1}q^{n-1}(q+1)=240 $$

となる。

$q$ は奇素数なので、$q+1$ は偶数である。したがって左辺の $2$ の指数は

$$ (m-1)+v_2(q+1) $$

であり、これは $240$ の $2$ の指数である $4$ 以下でなければならない。

また $v_2(q+1)\geqq 1$ であるから、

$$ m-1\leqq 3 $$

である。$m\geqq 3$ より、

$$ m=3,4 $$

に限られる。

(i)

$m=3$ のとき

$$ 2^{2}q^{n-1}(q+1)=240 $$

より

$$ q^{n-1}(q+1)=60 $$

である。

$n=1$ のとき、

$$ q+1=60 $$

より

$$ q=59 $$

であり、これは素数である。したがって

$$ (p,q,m,n)=(2,59,3,1) $$

を得る。

$n\geqq 2$ のとき、$q^{n-1}$ が $60$ を割るので、$q$ は $60$ の素因数である。$q$ は奇素数で $q>2$ だから、

$$ q=3,5 $$

に限られる。

$q=3$ のとき、

$$ 3^{n-1}(3+1)=60 $$

より

$$ 3^{n-1}=15 $$

となり不可能である。

$q=5$ のとき、

$$ 5^{n-1}(5+1)=60 $$

より

$$ 5^{n-1}=10 $$

となり不可能である。

よって $m=3$ では

$$ (p,q,m,n)=(2,59,3,1) $$

のみである。

(ii)

$m=4$ のとき

$$ 2^3q^{n-1}(q+1)=240 $$

より

$$ q^{n-1}(q+1)=30 $$

である。

$n=1$ のとき、

$$ q+1=30 $$

より

$$ q=29 $$

であり、これは素数である。したがって

$$ (p,q,m,n)=(2,29,4,1) $$

を得る。

$n\geqq 2$ のとき、$q^{n-1}$ が $30$ を割るので、$q$ は $30$ の素因数である。$q$ は奇素数で $q>2$ だから、

$$ q=3,5 $$

に限られる。

$q=3$ のとき、

$$ 3^{n-1}(3+1)=30 $$

より

$$ 3^{n-1}=\frac{15}{2} $$

となり不可能である。

$q=5$ のとき、

$$ 5^{n-1}(5+1)=30 $$

より

$$ 5^{n-1}=5 $$

であるから、

$$ n-1=1 $$

すなわち

$$ n=2 $$

である。したがって

$$ (p,q,m,n)=(2,5,4,2) $$

を得る。

以上より、求める組は

$$ (p,q,m,n)=(2,59,3,1),(2,29,4,1),(2,5,4,2) $$

である。

解説

この問題の中心は、倍数の個数を包除原理で数えて

$$ p^{m-1}q^{n-1}(p+q-1)=240 $$

という形にすることである。

その後は、$m\geqq 3$ から $p^2\mid 240$ が分かるため、$p=2$ に絞れる。ここで大きく候補が減る。

さらに、$q$ が奇素数であるため $q+1$ が偶数であることを使うと、$2$ の指数から $m=3,4$ だけを調べればよい。あとは $n=1$ と $n\geqq 2$ に分け、$q^{n-1}$ が右辺を割る条件から有限個に絞る。

答え

$$ (p,q,m,n)=(2,59,3,1),(2,29,4,1),(2,5,4,2) $$