ISL2022N8
今日はIMOshortlistを解いてみます.
$n$を正の整数とするとき$\dfrac{5^n-3^n}{2^n+65}$は整数とならないことを示せ.
一行問題、しかもあんま指数分の指数の形の式を見たことがない...
とりあえず分子が冪乗$-$冪乗の形をしているので, 分子は扱いやすそう. ただ, $n$が素数とかに限定されているわけではないので, 少し面倒. ただ, 分母の素因数を取って矛盾とかはできそう.
まずは自明考察. 明らかに$n$は$3$以上. さらに$\bmod3$でやれば$n\equiv 1\pmod2$がわかります. $n$は奇数. これ普通に使えそう. $n$が奇数なら分子の素因数に制限がかかります. $p|5^n-3^n$とすると, $5^n\equiv3^n\pmod p$がわかるので位数の議論的に何らかの制限がありそうって感じです. 今回はめっちゃ簡単で, 両辺に$3^n$を掛けて平方剰余か否かを考えれば, $15$が$\pmod p$で平方剰余っていうのが条件として出てきます. (平方剰余か否かっていうのは位数に関する情報でしたね)
ということは, $p|2^n+65$なる任意の素数$p$に対して$\left(\dfrac{15}p\right)=1$が成立するということです. 結構厳しい条件.
ただ, このままだと扱うのが面倒です. $p|2^n+65$の部分が非常にめんどくさい. 全ての素因数をいい感じにまとめて議論する方法はないだろうか...
そこで少し頭をよぎるのがヤコビ記号. 雑に言うと平方剰余記号を正整数に拡張したやつです.
$n$を整数, $m$を正の奇数とする. $m=\displaystyle\prod_p p^{e_p}$と素因数分解できるとき, $\left(\dfrac nm\right)=\displaystyle\prod_p\left(\dfrac np\right)^{e_p}$と定義する.
実は平方剰余の相互法則と同様にヤコビ記号には相互法則が成立します.
$m,n$を互いに素な正の奇数とすると, $\left(\dfrac mn\right)\left(\dfrac nm\right)=(-1)^{\frac{(m-1)(n-1)}{4}}$が成立する.
定義から分かるようにヤコビ記号$\left(\dfrac{15}{2^n+65}\right)$の値が$1$であることは$15$が全ての$2^n+65$の素因数$p$で平方剰余であることの必要条件を与えています.
あくまでも必要条件なのであんまりうまくいくことは期待できませんが, とりあえずやってみましょう. ヤコビ記号は基本的に平方剰余記号と同じように扱えます. あと, 明らかに, $2^n+65$は$15$と互いに素です.
$$\left(\dfrac{15}{2^n+65}\right)=\left(\dfrac{2^n+65}{15}\right)(-1)^{\frac{14\cdot(2^n+64)}{4}}=\left(\dfrac{2^n+5}{15}\right)$$
ここで$n\geq3$を用いました. いま, $n$は奇数に限定されていたことを考えると $\left(\dfrac{2^n+5}{15}\right)$はもっと先に進めそうです.
$n\equiv1\pmod4$のときは$\left(\dfrac{2^n+5}{15}\right)=\left(\dfrac{2+5}{15}\right)=\left(\dfrac{7}3\right)\left(\dfrac{7}5\right)=1\cdot(-1)=-1$. なるほど.
$n\equiv3\pmod4$のときは$\left(\dfrac{2^n+5}{15}\right)=\left(\dfrac{8+5}{15}\right)=\left(\dfrac{13}3\right)\left(\dfrac{13}5\right)=1\cdot(-1)=-1$. ま？どっちでも矛盾した？！！！！！
ということで相互法則を使うだけであっけなく解けてしまいました. やはり変数と定数を逆転させれる相互法則の神髄ってとこですね()
ちなみにですが今回出てきたヤコビ記号は普通に平方剰余記号を手計算で求めるときに結構便利なので平方剰余の相互法則に慣れてきたら日々の計算に導入してみるのもよいかもしれません. あと, ヤコビ記号の分母に負の数とかを入れる試みもあります. 少しコーナーケースが面倒になりますが同様に相互法則とか積の分配とかできた記憶. 相互法則は数学的にかなり偉い背景があるので色々調べてみるのも面白いかもしれませんね. 本当にこれがN8じゃなければ良問だったのに...