インテジャーズ

INTEGERS

数、特に整数に関する記事。

112359550561797752809×99=11123595505617977528091

11235955056179775280999倍すると両端に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とします。

補題1 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.

補題2 pp \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+1pで割った余りと定める。もし、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.

補題3 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.

pp \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が成り立つ。

証明. 補題2+補題3 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である。

証明. 補題1と系より従う。 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_rPの相異なる元とするとき、中国剰余定理より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の定理2より\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.

根拠. bb\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であることがわかる。

*1:定義からはe \geq 2ですが、b \geq 3のときこの合同式はe=1では不成立のため、「b^e \equiv -1 \pmod{b^2-b-1}を満たす正整数eが存在する」ことと同値になります。