112359550561797752809×99=11123595505617977528091

$112359550561797752809$ は $99$ 倍すると両端に $1$ をくっつけた数になるという性質を持っています:

$112359550561797752809\times 99=\color{red}{1}112359550561797752809\color{red}{1}$

一般の $b$ 進法でこの性質を考えると、

$b^{k+2}+bx+1=(b^2-1)x, \quad [\log_bx]=k$

が成り立つような $(x, k)$ を求めるという問題が得られます( $x$ は正整数で $k$ は非負整数)。変形すれば、

$\displaystyle \frac{b^{k+2}+1}{b^2-b-1}=x, \quad [\log_bx]=k$

となります。 $b=2$ のときは $[\log_2(2^{k+2}+1)]=k$ という条件になりますが、実際には $[\log_2(2^{k+2}+1)]=k+2$ なので解なしです。一方、 $b \geq 3$ とすると

$\displaystyle b^k < \frac{b^{k+2}+1}{b^2-b-1} < b^{k+1}$

が成り立つので、正整数 $(x, k)$ が存在するための必要十分条件は

$\displaystyle \frac{b^{k+2}+1}{b^2-b-1}$

が整数となることです(そのとき、その整数値が $x$ )。 $e=k+2$ とおけば、これは

$b^e \equiv -1 \pmod{b^2-b-1}$

なる $e$ の存在性と同値です*1。

Fermatの小定理より $10^{88}\equiv 1 \pmod{89}$ ですが、 $10^{22} \equiv -1 \pmod{89}$ がわかるので、十進法で所望の性質を満たす整数は

$\displaystyle \frac{10^{22+44i}+1}{89}$

と表される数となります( $i$ は非負整数)。

そうして、 $i=0$ の場合が $112359550561797752809$ なので、この数が最小とわかりました。

十進法では存在しましたが、このような性質を持つ整数が存在するような $b$ はむしろ少数派であることがわかります:

定理 (Hunsucker-Pomerance) $b^e \equiv -1 \pmod{b^2-b-1}$ なる正整数 $e$ が存在するような $b \geq 3$ のなす集合の正整数全体における密度は $0$ である。

以下、この定理を証明しましょう。定理で考えている集合を $A$ とします。

補題１ $b \in A$ とする。このとき、 $b^2-b-1$ の任意の素因数 $p$ に対して $\mathrm{Ind}_b(p)$ は偶数である。

$\mathrm{Ind}_b(p)$ は $b\bmod{p}$ の $(\mathbb{Z}/p\mathbb{Z})^{\times}$ における位数。cf. カーマイケルのλ関数と絶対擬素数 - INTEGERS

証明. $b \in A$ とすると $b^e \equiv -1 \pmod{b^2-b-1}$ なる正整数 $e$ が存在するため、 $b^2-b-1$ の任意の素因数 $p$ に対して $b^{e} \equiv -1 \pmod{p}$ である。すると、 $b\bmod{p}$ の生成する $(\mathbb{Z}/p\mathbb{Z})^{\times}$ の部分群は $\{\pm1\}$ を部分群として含むので、 $b\bmod{p}$ の位数は偶数である。 Q.E.D.

補題２ $p$ を $p \equiv 3 \pmod{4}$ を満たすような素数とし、或る正整数 $g$ に対して $p \mid g^2-g-1$ とする。このとき、整数 $0 < a_p \leq p$ が存在して、 $b \equiv a_p \pmod{p}$ であれば、 $\mathrm{Ind}_b(p)$ は奇数であり $p \mid b^2-b-1$ が成り立つ。

証明. $p$ の条件から

$\displaystyle \left(\frac{g}{p}\right)\left(\frac{-g+1}{p}\right) = \left(\frac{-g^2+g}{p}\right)=\left(\frac{-1}{p}\right)=-1$

なので(第一補充則)、 $\left(\frac{g}{p}\right)=1$ または $\left(\frac{-g+1}{p}\right)=1$ である。ここで使用している記号はLegendre記号である。 $a_p$ を $\left(\frac{a_p}{p}\right)=1$ が成り立つように $g$ または $-g+1$ を $p$ で割った余りと定める。もし、 $b \equiv a_p \pmod{p}$ であれば、Eulerの規準より

$\displaystyle b^{\frac{p-1}{2}} \equiv a_p^{\frac{p-1}{2}}\equiv \left(\frac{a_p}{p}\right) \equiv 1$

となって、 $\frac{p-1}{2}$ が奇数であることから $\mathrm{Ind}_b(p)$ も奇数であることが従う。また、

$(-g+1)^2-(-g+1)-1=g^2-g-1$

なので

$b^2-b-1 \equiv a_p^2-a_p-1 \equiv 0 \pmod{p}$

である。 Q.E.D.

補題３ $p \equiv 1, 4\pmod{5}$ なる素数 $p$ に対して、或る正整数 $g \geq 3$ が存在して $p \mid g^2-g-1$ が成り立つ。

証明. $h^2 \equiv 5 \mod{p}$ なる正整数 $h$ をとって(平方剰余の相互法則により存在)、

$\displaystyle g:=\frac{1}{2}(1+h)(1+p)$

とおけば、 $g^2-g-1 \equiv 0 \pmod{p}$ が成り立つ。 Q.E.D.

系 $p$ を $p \equiv 11, 19\pmod{20}$ なる素数とする。このとき、或る整数 $0 < a_p \leq p$ が存在して、 $b \equiv a_p \pmod{p}$ であれば、 $\mathrm{Ind}_b(p)$ は奇数であり $p \mid b^2-b-1$ が成り立つ。

証明. 補題２＋補題３ Q.E.D.

$P:=\{p: \text{素数} \mid p \equiv 11, 19 \pmod{20}\}$ とし、 $p \in P$ に対して系で存在する $a_p$ を固定します。

命題 $B:=\{b \geq \mathbb{Z}_{\geq 3} \mid {}^{\exists}p \in P \ \text{s.t.} \ b \equiv a_p \pmod{p}\}$ とする。このとき、 $B \subset \mathbb{Z}_{\geq 3} \setminus A$ である。

証明. 補題１と系より従う。 Q.E.D.

定理の証明. $p \in P$ 毎に $B^{(p)}:=\{b \geq \mathbb{Z}_{>0} \mid b \equiv a_p \pmod{p}\}$ とする。このとき、

$\displaystyle \#B_{\leq N} \geq \#\bigcup_{\substack{p \in P \\ p \leq \log N}}B^{(p)}_{\leq N} -2$

が成り立つ。 $p_1, \dots, p_r$ を $P$ の相異なる元とするとき、中国剰余定理より $0 < a_{p_1\cdots p_r} \leq p_1\cdots p_r$ が存在して、

$\displaystyle \#\{B^{(p_1)}_{\leq N}\cap \cdots \cap B^{(p_r)}_{\leq N}\}=\left[\frac{N-a_{p_1\cdots p_r}}{p_1\cdots p_r}\right]$

が成り立つので、

$\displaystyle \frac{N}{p_1\cdots p_r}-2 < \#\{B^{(p_1)}_{\leq N}\cap \cdots \cap B^{(p_r)}_{\leq N}\} < \frac{N}{p_1\cdots p_r}$

である。従って、命題および包含原理から

$\displaystyle \#A_{\leq N} \leq N-2-\#B_{\leq N} \leq N-\#\bigcup_{\substack{p \in P \\ p \leq \log N}}B^{(p)}_{\leq N} < N\prod_{\substack{p \in P \\ p \leq \log N}}\left(1-\frac{1}{p}\right)+2^{\#P_{\leq \log N}}$

が得られる。 $\#P_{\leq \log N} \leq \log N$ であり、 $\lim_{N \to \infty}\frac{2^{\log N}}{N}=0$ なので、

$\displaystyle \lim_{N \to \infty}\frac{\#A_{\leq N}}{N} \leq \prod_{p \in P}\left(1-\frac{1}{p}\right)$

となる。ディリクレの算術級数定理のL関数を用いない証明 - INTEGERSの定理２より $\sum_{p \in P}\frac{1}{p}=\infty$ なので上記無限積は $0$ であり、結局

$\displaystyle \lim_{N \to \infty}\frac{\#A_{\leq N}}{N}=0$

が示された。 Q.E.D.

$A$ は密度は $0$ ですが、無限集合であると予想されます。

予想 $\#A=\infty$ .

根拠. $b$ を $b\equiv 3 \pmod{4}$ なる素数であり、 $p:=b^2-b-1$ も素数であるようなものとする。Schinzelの仮説Hよりこのような $b$ は無数に存在すると予想されている。 $p \equiv 1 \pmod{4}$ なので、平方剰余の相互法則と第一補充則より

$\displaystyle \left(\frac{b}{p}\right) = \left(\frac{p}{b}\right) = \left(\frac{-1}{b}\right) = -1$

となる。これは、 $\mathrm{Ind}_b(p)$ が偶数であることを意味する。というのも、 $\mathrm{Ind}_b(p)=2e-1$ が奇数であれば、 $b^{2e-1}\equiv 1 \pmod{p}$ から $(b^{e})^2\equiv b \pmod{p}$ となってしまうからである。よって、 $\mathrm{Ind}_b(p)=2e$ と書くことができ、このとき、 $b^e \equiv -1 \pmod{p}$ となって、 $b \in A$ であることがわかる。