x^x^xを1987で割った余りが1977になる正の整数xの存在証明｜合同式を使った考え方

指数が何重にも重なった数の余りを求める問題は、一見すると巨大な数を計算しなければならないように感じます。しかし、合同式やフェルマーの小定理を利用すると、実際には小さな計算だけで処理できます。

この記事では、x^x^x（ここでは指数法則の慣習に従いx^(x^x)と解釈します）が1987で割った余りとして1977になる正の整数xが存在することを、具体的な数値を使って説明します。

問題を合同式の形に整理する

求めたい条件は、x^(x^x)を1987で割った余りが1977になることです。つまり、合同式では次のように表せます。

x^(x^x) ≡ 1977 (mod 1987)

まず1987について確認すると、1987は素数です。そのため、xが1987の倍数でない場合、フェルマーの小定理より

x^1986 ≡ 1 (mod 1987)

が成り立ちます。したがって、指数部分は1986を法として考えればよいことになります。

1977は1987との差が10なので、

1977 ≡ -10 (mod 1987)

と書けます。つまり、最終的にはx^(x^x)が1987を法として-10になるようなxを探せばよいことになります。

このような問題では、xそのものをうまく選び、底と指数の両方を制御する考え方が重要です。巨大な指数を直接計算するのではなく、余りだけを追跡します。

実際に、x=3187という正の整数を考えます。

まず底については、

3187 ≡ 1200 (mod 1987)

となります。

次に指数部分を1986を法として計算します。

3187^3187 ≡ 373 (mod 1986)

したがって、フェルマーの小定理を使うと、

3187^(3187^3187) ≡ 1200^373 (mod 1987)

として計算できます。

上で求めた合同式を計算すると、

1200^373 ≡ 1977 (mod 1987)

となります。

よって、

3187^(3187^3187) ≡ 1977 (mod 1987)

が成立します。

つまり、x=3187は条件を満たす正の整数であり、「そのようなxが存在する」ことが示されました。

このタイプの問題で大切なのは、巨大な指数を実際に展開しようとしないことです。指数関数的に大きくなる数でも、余りだけを考えれば計算量を大きく減らせます。

特に、法となる数が素数の場合はフェルマーの小定理が強力な道具になります。指数を1986で考えることで、何兆、何京という大きさの数を扱わずに済みます。

また、x^x^xのような問題では、どの部分をどの法で考えるべきかを判断する力が重要です。底を見る法と指数を見る法が異なる点を意識すると、複雑な指数問題にも対応できます。

x^x^xを1987で割った余りが1977になる正の整数xが存在することは、実際にx=3187を示すことで証明できます。

計算のポイントは、1987が素数であることを利用し、指数部分を1986を法として処理することです。巨大な数を直接計算するのではなく、合同式によって必要な情報だけを取り出すことが、この問題を解く基本的な考え方になります。