トップ› 大阪大学› 2004年› 理系第2問

大阪大学 2004年理系第2問解説

方針・初手

(1) は $a_1$ と $a_2$ を $p, q$ を用いて表し、最大公約数の性質や合同式を利用して $m$ が満たすべき条件を絞り込む。素数であることと $p > 2q$ という条件から $m$ の素因数や偶奇を特定していく。 (2) は (1) の考察をもとに、すべての自然数 $n$ について $a_n \equiv 0 \pmod 3$ となるための条件を見つける。$a_1 \equiv 0 \pmod 3$ から $p, q$ の条件が定まり、それが十分条件でもあることを確認したうえで、条件を満たす素数の組を具体的に探索する。

解法1

(1) 与えられた定義より、$a_1$ と $a_2$ は以下のようになる。

$$ a_1 = p + 4q $$

$$ a_2 = p^2 - 4q^2 $$

$m$ は $a_1$ と $a_2$ の1より大きい公約数であるから、法 $m$ において以下が成り立つ。

$$ a_1 \equiv 0 \pmod m $$

$$ a_2 \equiv 0 \pmod m $$

$a_1 \equiv 0 \pmod m$ より $p+4q \equiv 0 \pmod m$ であるから、

$$ p \equiv -4q \pmod m $$

これを $a_2 \equiv 0 \pmod m$ に代入すると、

$$ (-4q)^2 - 4q^2 = 16q^2 - 4q^2 = 12q^2 \equiv 0 \pmod m $$

したがって、$m$ は $12q^2$ の約数である。

次に、$m$ と $q$ が互いに素であることを背理法で示す。 $m$ と $q$ が1より大きい公約数 $d$ をもつと仮定する。 $q$ は素数であるため $d=q$ であり、$m$ は $q$ の倍数となる。 $m$ は $a_1$ の約数であるから、$a_1 = p+4q$ は $q$ の倍数となる。 $4q$ は $q$ の倍数であるため、$p = a_1 - 4q$ も $q$ の倍数となる。 $p, q$ はともに素数であるから、これが成り立つのは $p=q$ のときのみであるが、これは条件 $p > 2q$ に矛盾する。したがって、$m$ と $q$ は互いに素である。

$m$ は $12q^2$ の約数であり、かつ $q$ と互いに素であるから、$m$ は12の約数でなければならない。よって $m \in \{1, 2, 3, 4, 6, 12\}$ であるが、$m > 1$ より $m \in \{2, 3, 4, 6, 12\}$ に絞られる。

ここで、$m$ が偶数であると仮定する。 2は $m$ の約数となるため、2は $a_1$ の約数でもある。

$$ a_1 = p + 4q \equiv 0 \pmod 2 \implies p \equiv 0 \pmod 2 $$

$p$ は偶数の素数となるので $p=2$ である。一方、$q$ は素数なので $q \ge 2$ であり、条件 $p > 2q$ より $p > 4$ とならなければならない。これは $p=2$ に矛盾する。よって、$m$ は奇数でなければならない。

12の約数のうち、1より大きい奇数は3のみである。以上より、$m=3$ であることが示された。

(2) $a_n$ がすべて3の倍数であるから、特に $n=1$ のとき $a_1$ は3の倍数である。

$$ a_1 = p + 4q = p + q + 3q \equiv p + q \equiv 0 \pmod 3 $$

したがって、$p \equiv -q \pmod 3$ である。このとき、任意の自然数 $n$ に対して法3で考えると、

$$ a_n = p^n - 4(-q)^n \equiv (-q)^n - (-q)^n = 0 \pmod 3 $$

となり、すべての $a_n$ が3の倍数となる。ゆえに、$a_n$ がすべて3の倍数であるための必要十分条件は $p+q \equiv 0 \pmod 3$ である。

ここで、もし $q=3$ ならば $p \equiv -3 \equiv 0 \pmod 3$ となり、素数 $p$ は $p=3$ となるが、これは $p > 2q$ に矛盾する。したがって、$q$ は3以外の素数である。

求めるものは、$q \neq 3$ かつ $p > 2q$ かつ $p+q \equiv 0 \pmod 3$ を満たす素数の組 $(p, q)$ のうち、積 $pq$ が最小となるものである。 $q$ が小さい順に調べる。

(i)

$q=2$ のとき条件 $p > 4$ を満たす素数 $p$ は $5, 7, 11, \cdots$ である。このうち、$p+2 \equiv 0 \pmod 3$ を満たす最小の素数は $p=7$ である。このとき $pq = 7 \times 2 = 14$ となる。

(ii)

$q \ge 5$ のとき条件 $p > 2q \ge 10$ を満たすため、$p$ は11以上の素数となる。このとき $pq \ge 11 \times 5 = 55 > 14$ となり、積が最小になることはない。

以上より、積 $pq$ が最小となる $p, q$ は $p=7, q=2$ である。

解説

(1) は合同式を用いて $12q^2 \equiv 0 \pmod m$ を導き、$m$ と $q$ が互いに素であることを背理法で示すのが肝である。これにより $m$ が12の約数に限定される。さらに、条件 $p > 2q$ を用いて $m$ が偶数になる可能性を排除することで、結論の $m=3$ を鮮やかに導くことができる。 (2) はすべての自然数 $n$ に対して $a_n \equiv 0 \pmod 3$ となる条件が、$a_1 \equiv 0 \pmod 3$ から得られる $p+q \equiv 0 \pmod 3$ だけで必要十分に定まることに気づくことが重要である。条件を満たす素数の探索は、変数 $q$ を小さい方から固定して絞り込む典型的な処理で容易に解決できる。