7
競技数学解説
冪乗が出てくる整数問題
677
0
$$$$
最近読んでいる『数論の精選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=mk+r\ (0\leq r< k)$ とすると、$3^r\equiv3^{n-mk}\equiv(-1)^{m+1}\pmod n$である。
ここで、$r\neq0$と仮定すると、$r$と$k-r$のどちらかは$k$の最小に矛盾するので$r=0$であり、$k$は$n$の約数であると結論できる。また、これから$k$が奇数であることもわかる。
次に、$k< n$であることを示す。
$n$は$3$の倍数ではないので、Eulerの定理より$3^{\varphi(n)}\equiv1\pmod n$であり、$\varphi(n)< n$なので$3^{n-\varphi(n)}\equiv-1\pmod n$となり、$k\leq n-\varphi(n)< n$が得られる。
また、$k=1$なら$n$は$4$の約数となるので$k=1$とはなり得ない。
以上より$3^k+1$は$n$の倍数なので$k$の倍数でもあり、$1< k< n$であり、$k$は奇数なので$n$が最小であることに矛盾している。
よって題意は示された。
$3^n+1$が$n$の倍数となるような$3$以上の奇数$n$が存在したと仮定し、そのような$n$の中で最小のものを取ってくる。
$k$を、$3^k+1$が$n$の倍数となるような正の整数のうち最小のものとする。
このとき、$k$が$n$の約数であることを示す。
$n=mk+r\ (0\leq r< k)$ とすると、$3^r\equiv3^{n-mk}\equiv(-1)^{m+1}\pmod n$である。
ここで、$r\neq0$と仮定すると、$r$と$k-r$のどちらかは$k$の最小に矛盾するので$r=0$であり、$k$は$n$の約数であると結論できる。また、これから$k$が奇数であることもわかる。
次に、$k< n$であることを示す。
$n$は$3$の倍数ではないので、Eulerの定理より$3^{\varphi(n)}\equiv1\pmod n$であり、$\varphi(n)< n$なので$3^{n-\varphi(n)}\equiv-1\pmod n$となり、$k\leq n-\varphi(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$
をみたすようなものが存在するかどうかを決定せよ．
$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)$は存在しない。
$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$
をみたすものをすべて求めよ．
$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}+\cdots+1)=2$より$k$は$2$の約数である。
$k$が$r$の約数であることも踏まえると$k=1$となり、$p|q+1$である。
$p,q,r$は奇素数なので$p=q+1$とはならず、$q+1\geq2p$すなわち、$q\geq2p-1$となる。
同様に、$r\geq2q-1,\ p\geq2r-1$もわかるので、$p\geq2r-1\geq2(2q-1)-1\geq2(2(2p-1)-1)-1=8p-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)$である。
条件より、$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}+\cdots+1)=2$より$k$は$2$の約数である。
$k$が$r$の約数であることも踏まえると$k=1$となり、$p|q+1$である。
$p,q,r$は奇素数なので$p=q+1$とはならず、$q+1\geq2p$すなわち、$q\geq2p-1$となる。
同様に、$r\geq2q-1,\ p\geq2r-1$もわかるので、$p\geq2r-1\geq2(2q-1)-1\geq2(2(2p-1)-1)-1=8p-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日
この記事を高評価した人
この記事を高評価した人
高評価したユーザはいません
この記事に送られたバッジ
この記事に送られたバッジ
バッジはありません。
投稿者
投稿者
コメント
コメント
他の人のコメント
コメントはありません。
読み込み中...
読み込み中