競技数学問題

7^1013+1の四桁の素因数を全て求めよ。

初等整数論,競技数学,整数問題

はじめに

整数問題を作ってみました！
問題文がコンパクトで綺麗に仕上がったのでここで解説をしていきたいと思います！

問題

$7^{1013}+1$の四桁の素因数を全て求めよ。
　ただし、素数表を用いてもよい。

解きたい人用
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:

指針

整数問題の醍醐味といえば解の絞り込みです。解の絞り込みには因数分解、不等式評価、余りの一意性など主にこの三つですが、今回はどれも見通しがあまりよくありません。そこで、$7^{1013}\equiv{-1} \Longrightarrow{7^{2026}\equiv{1}} $
であることから今回の問題は位数との相性が良さそうなので$7$の位数に着目して解を絞っていこうと思います。

解答に行く前に

今回の問題を解くにあたって位数や平方剰余における基本的な定理が必要になるので知らない方のために下に載せておきます。知ってるよという方はとばしてもらって構いません。<(_ _)>

位数

整数$a$に対して$p$を素数としたとき、$a^n\equiv{1\pmod{p}}$となるような最小の正整数$n$を法$p$における$a$の位数という。

正整数$n$を法$p$における$a$の位数とする。正整数$m$に対して$a^m\equiv{1\pmod{p}}$ならば$m$は$n$の倍数である。

定理１の

$a^m\equiv{a^n}\equiv{1}\pmod{p}$ならば法$p$における$a$の位数は$\gcd{(m,n)}$である。

ルジャンドル記号

$p$を奇素数とし、$a$を$p$と互いに素である整数とする。法$p$において
$\begin{eqnarray} \displaystyle\bigg(\frac{a}{p}\bigg{)}= \left\{ \begin{array}{l} 1\,\,\,\,\cdots\;\;{a\text{が平方剰余のとき}} \\ -1\cdots\;\;{a\text{が平方非剰余のとき}} \end{array} \right. \end{eqnarray}$

ルジャンドル記号の性質

$p$を奇素数、$a,b$はどちらも$p$互いに素とする。このとき、
$1.\;\; \displaystyle\bigg(\frac{a}{p}\bigg{)}\equiv{a^{\frac{p-1}{2}}}\pmod{p}$ (オイラーの規準)

$2.\;\;\displaystyle\bigg(\frac{ab}{p}\bigg{)}=\bigg(\frac{a}{p}\bigg{)}\bigg(\frac{b}{p}\bigg{)}$

補充法則

$p$を奇素数とする。
$1.\;\; \displaystyle\bigg(\frac{-1}{p}\bigg{)}=(-1)^{\frac{p-1}{2}}$ (第一補充法則)

$2.\;\;\displaystyle\bigg(\frac{2}{p}\bigg{)}=(-1)^{\frac{p^{2}-1}{8}}$ (第二補充法則)

平方剰余の相互法則

$p,q$を奇素数とする。
$\displaystyle\bigg(\frac{q}{p}\bigg{)}\bigg(\frac{p}{q}\bigg{)}=(-1)^{\frac{(p-1)(q-1)}{4}}$

:
:
:
:
:
:

解答

$7^{1013}+1$を割り切るような四桁の素数を$p$とおく。
以下法を$p$とする。
$7^{1013}\equiv{-1} \Longrightarrow{7^{2026}\equiv{1}} $
フェルマーの小定理より、
${7^{2026}\equiv{1}}\equiv{7^{p-1}} $
したがって、法$p$における$7$の位数は$\gcd{(2026,p-1)}$であることがわかる。
$2026=2\cdot{1013}$なので位数の候補としてありうるのは$p-1$が偶数であることを考慮して$2$または$2026$であることがわかるが$2$は明らかに不適なので位数は$2026$である。
よって、$p$の候補は$2027,4053,6079,8105$のいずれかであるが素数表より$2027,6079$の$2$つに絞られる。
(i) $p=2027$のとき
平方剰余の相互法則より、

$\displaystyle\bigg(\frac{7}{2027}\bigg{)}\bigg(\frac{2027}{7}\bigg{)}=\bigg(\frac{7}{2027}\bigg{)}\bigg(\frac{4}{7}\bigg{)}=\bigg(\frac{7}{2027}\bigg{)}=(-1)^{\frac{(2027-1)(7-1)}{4}}=-1$

$\therefore\displaystyle\bigg(\frac{7}{2027}\bigg{)}=-1$

オイラー規準から
$\displaystyle7^{\frac{2027-1}{2}}\equiv7^{1013}\equiv{-1}$
$\therefore7^{1013}+1\equiv{0}\pmod{2027}$
よって、$7^{1013}+1$は$2027$を素因数にもつ。
(ii) $p=6079$のとき
平方剰余の相互法則より、
$\displaystyle\bigg(\frac{7}{6079}\bigg{)}\bigg(\frac{6079}{7}\bigg{)}=\bigg(\frac{7}{6079}\bigg{)}\bigg(\frac{3}{7}\bigg{)}=\bigg(\frac{7}{6079}\bigg{)}(-1)=(-1)^{\frac{(6079-1)(7-1)}{4}}=-1$
$\therefore\displaystyle\bigg(\frac{7}{6079}\bigg{)}=1$
オイラー規準から
$\displaystyle7^{\frac{6079-1}{2}}\equiv7^{3039}\equiv{1}$
ここで、$7^{1013}+1\equiv{0}\pmod{6079}$と仮定すると
$7^{3039}\equiv(7^{1013})^{3}\equiv{(-1)^{3}}\equiv{1}$
$\therefore-1\equiv{1}\pmod{6079}$
より矛盾が生じる。
したがって、求める素因数は$2027$のみである。