トップ› 基礎問題› 数学A› 整数問題› 整数問題› 問題 77

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

方針・初手

(1) は $2^2=4\equiv 1 \pmod{3}$ を使う。

(2) は $2^n+1$ と $2^n-1$ の差が $2$ であることに注目する。共通約数は $2$ を割り切るが、両方とも奇数である。

(3) はまず偶奇から $p,q$ がともに奇素数であることを確認し、(1) により $3$ が右辺 $pq^2$ を割り切ることを利用する。

解法1

(1)

$n$ は正の偶数なので、ある正の整数 $k$ を用いて

$$ n=2k $$

と表せる。

このとき

$$ 2^n=2^{2k}=4^k $$

である。ここで

$$ 4\equiv 1 \pmod{3} $$

だから、

$$ 4^k\equiv 1^k\equiv 1 \pmod{3} $$

となる。したがって

$$ 2^n-1\equiv 0 \pmod{3} $$

である。

よって、$2^n-1$ は $3$ の倍数である。

(2)

ここでは自然数を正の整数とする。

$2^n+1$ と $2^n-1$ の正の公約数を $d$ とする。このとき

$$ d\mid 2^n+1,\qquad d\mid 2^n-1 $$

であるから、その差も $d$ で割り切れる。よって

$$ d\mid {(2^n+1)-(2^n-1)} $$

すなわち

$$ d\mid 2 $$

である。

一方、$2^n$ は偶数であるから、$2^n+1$ と $2^n-1$ はともに奇数である。したがって、両者の公約数 $d$ も奇数である。

$d\mid 2$ かつ $d$ は奇数なので、

$$ d=1 $$

でなければならない。

よって、$2^n+1$ と $2^n-1$ は互いに素である。

(3)

まず $p=2$ のとき、

$$ 2^{p-1}-1=2^1-1=1 $$

であるが、右辺は

$$ pq^2=2q^2 $$

となり $1$ にはならない。よって $p\neq 2$ である。

また、$q=2$ のとき、右辺 $pq^2=4p$ は偶数であるが、左辺 $2^{p-1}-1$ は奇数である。よって矛盾する。したがって $q\neq 2$ である。

よって、$p,q$ はともに奇素数である。

$p$ は奇素数なので、$p-1$ は正の偶数である。したがって (1) より

$$ 3\mid 2^{p-1}-1 $$

である。

条件

$$ 2^{p-1}-1=pq^2 $$

より、

$$ 3\mid pq^2 $$

である。$p,q$ は素数だから、

$$ p=3 \quad \text{または} \quad q=3 $$

である。

(i) $p=3$ の場合

このとき

$$ 2^{p-1}-1=2^2-1=3 $$

である。一方、右辺は

$$ pq^2=3q^2 $$

だから、

$$ 3=3q^2 $$

となる。よって

$$ q^2=1 $$

となるが、$q$ は素数なので不可能である。

したがって、$p=3$ は成り立たない。

(ii) $q=3$ の場合

条件式は

$$ 2^{p-1}-1=9p $$

となる。すなわち

$$ 2^{p-1}=9p+1 $$

である。

$p$ は $3$ ではない奇素数なので、

$$ p=5,\ 7,\ \text{または }p\geq 11 $$

である。

$p=5$ のとき、

$$ 2^{p-1}=2^4=16,\qquad 9p+1=46 $$

であり、成り立たない。

$p=7$ のとき、

$$ 2^{p-1}=2^6=64,\qquad 9p+1=64 $$

であり、成り立つ。

次に $p\geq 11$ の場合を考える。$p=11$ のとき

$$ 2^{p-1}=2^{10}=1024>100=9\cdot 11+1 $$

である。また、$m\geq 11$ のとき

$$ 2^m-9>0 $$

だから、

$$ {2^m-(9(m+1)+1)}-{2^{m-1}-(9m+1)}=2^{m-1}-9>0 $$

である。したがって、$2^{p-1}-(9p+1)$ は $p\geq 11$ で正であり、

$$ 2^{p-1}>9p+1 $$

となる。よって $p\geq 11$ では等式

$$ 2^{p-1}=9p+1 $$

は成り立たない。

以上より、

$$ p=7,\qquad q=3 $$

だけが条件を満たす。

実際に

$$ 2^{7-1}-1=2^6-1=63=7\cdot 3^2 $$

であるから、確かに成り立つ。

解説

(1) は偶数乗を $2^{2k}=4^k$ と見て、$4\equiv 1\pmod{3}$ を使う典型問題である。

(2) は「互いに素」を示すときの基本で、共通約数を $d$ と置き、差を取る。差が $2$ であり、かつ両方が奇数であることから、共通約数は $1$ に限られる。

(3) では、まず偶奇で $p,q$ が奇素数であることを確定する。その後、$p-1$ が偶数になるため (1) が使える。これにより $3$ が $pq^2$ を割り切るので、$p=3$ または $q=3$ に絞れる。最後は $p=3$ を排除し、$q=3$ として $2^{p-1}=9p+1$ を調べればよい。