冪乗が出てくる整数問題

958

最近読んでいる『数論の精選104問』という本で解いていて面白かった問題を3つ紹介しようと思います。

1つ目です。

3

以上の奇数

n

について、

3^{n} + 1

は

n

では割りきれないことを示せ．

マスターデーモン(1990年のIMOの問3)を彷彿とさせる問題ですが、本家(?)よりは簡単に解くことができます。

証明には無限降下法を使います。

(証明)

3^{n} + 1

が

n

の倍数となるような

3

以上の奇数

n

が存在したと仮定し、そのような

n

の中で最小のものを取ってくる。

k

を、

3^{k} + 1

が

n

の倍数となるような正の整数のうち最小のものとする。
このとき、

k

が

n

の約数であることを示す。

n = m k + r (0 \leq r < k)

とすると、

3^{r} \equiv 3^{n - m k} \equiv (- 1)^{m + 1} (\mod n)

である。
ここで、

r \neq 0

と仮定すると、

r

と

k - r

のどちらかは

k

の最小に矛盾するので

r = 0

であり、

k

は

n

の約数であると結論できる。また、これから

k

が奇数であることもわかる。
次に、

k < n

であることを示す。

n

は

3

の倍数ではないので、Eulerの定理より

3^{φ (n)} \equiv 1 (\mod n)

であり、

φ (n) < n

なので

3^{n - φ (n)} \equiv - 1 (\mod n)

となり、

k \leq n - φ (n) < n

が得られる。
また、

k = 1

なら

n

は

4

の約数となるので

k = 1

とはなり得ない。
以上より

3^{k} + 1

は

n

の倍数なので

k

の倍数でもあり、

1 < k < n

であり、

k

は奇数なので

n

が最小であることに矛盾している。
よって題意は示された。

もちろんマスターデーモンと同じ解き方でもできます。(書くのが面倒だったのでここでは書きません)

2つ目です。

どの

2

つも互いに素であるような

3

整数

a, b, c > 1

であって

b | 2^{a} + 1, c | 2^{b} + 1, a | 2^{c} + 1

をみたすようなものが存在するかどうかを決定せよ．

これも無限降下法が使えます。

(解答)

a, b, c

がどれも奇数であるときのみを考えればよい。
条件をみたす

(a, b, c)

が存在したと仮定し、その中で

a + b + c

の値が最も小さくなるものを取る。
一般性を失わず

a

が

a, b, c

の中で最大であると仮定できる。

a^{'}

を

2^{a^{'}} + 1

が

b

の倍数となるような正の整数の中で最小のものとする。
先ほどの議論を適用すると、

a^{'}

は

a

の約数であり、

a

より小さい。
ここで、

a^{'} = 1

とすると

b | 2^{a^{'}} + 1

より、

b = 3

であり、

c | 2^{b} + 1

から

c = 3, 9

で

b

と

c

が互いに素であるという条件に反する。
よって

a

を

a^{'}

に入れ換えることができ、

(a, b, c)

の最小性に矛盾する。
よって題意をみたす

(a, b, c)

は存在しない。

3つ目です。

素数の組

(p, q, r)

であって

p | q^{r} + 1, q | r^{p} + 1, r | p^{q} + 1

をみたすものをすべて求めよ．

この3つの中だと一番時間がかかりました。

(解答)
条件より、

p, q, r

は相異なる。
まず、

p, q, r

がどれも奇素数である場合を考える。

q^{k} + 1

が

p

の倍数であるような

k

のうち最小のものを取る。このとき、

k

は

r

の約数である。ここで、

r | p^{q} + 1

より、

k

は

p^{q} + 1

の約数である。また、Fermatの小定理より

q^{p - 1} - 1

は

p

の倍数なので

k

が

p - 1

の約数であることもわかる。
ここで、

p^{q} + 1 - (p - 1) (p^{q - 1} + p^{q - 2} + \dots + 1) = 2

より

k

は

2

の約数である。

k

が

r

の約数であることも踏まえると

k = 1

となり、

p | q + 1

である。

p, q, r

は奇素数なので

p = q + 1

とはならず、

q + 1 \geq 2 p

すなわち、

q \geq 2 p - 1

となる。
同様に、

r \geq 2 q - 1, p \geq 2 r - 1

もわかるので、

p \geq 2 r - 1 \geq 2 (2 q - 1) - 1 \geq 2 (2 (2 p - 1) - 1) - 1 = 8 p - 7

となり、

p > 2

に矛盾する。

次に、

p, q, r

の中に

2

が含まれている場合を考える。
一般性を失わず

p = 2

としてよい。

2 | q^{r} + 1, r | 2^{q} + 1

からそれぞれ

q, r

が奇素数であることがわかる。

2^{k} + 1

が

r

の倍数であるような

k

のうち最小のものを取る。
すると、先ほどと同様に

k = 1

であることがわかり、

r | 2^{k} + 1

から

r = 3

である。
また、

q | r^{2} + 1

から

q = 5

がわかり、

(p, q, r) = (2, 5, 3)

は解となっている。
よって、この方程式の解は

(p, q, r) = (2, 5, 3), (5, 3, 2), (3, 2, 5)

である。

投稿日：2022年1月22日

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

tria_math

531

44475

大学2年生

他の人のコメント

コメントはありません。

読み込み中

tria_math

冪乗が出てくる整数問題