1
$\begingroup$

Can you provide proofs or counterexamples for the following claims?

Claim 1

Let $P_m(x)=2^{-m}\cdot((x-\sqrt{x^2-4})^m+(x+\sqrt{x^2-4})^m)$ . Let $M= k \cdot b^{n}-c $ where $k,b,n,c$ are natural numbers such that $ k>0$ , $ b>1$ , $ n>1$ and $ c>0$. Let $a$ be a natural number greater than two such that $\left(\frac{a-2}{M}\right)=-1$ and $ \left(\frac{a+2}{M}\right)=1$ where $ \left(\frac{}{}\right)$ denotes Jacobi symbol. Let $ S_i=P_b(S_{i-1})$ with $ S_0$ equal to the modular $P_{kb}(a)\phantom{5} \text{mod} \phantom{5} M$. Then, if $ M$ is prime then $ S_{n-1} \equiv P_{c-1}(a) \pmod{M}$ .

You can run this test here .

Claim 2

Let $P_m(x)=2^{-m}\cdot((x-\sqrt{x^2-4})^m+(x+\sqrt{x^2-4})^m)$ . Let $N= k \cdot b^{n}+c $ where $k,b,n,c$ are natural numbers such that $k>0$ , $ b>1$ , $ n>1$ and $ c>0$ . Let $ a$ be a natural number greater than two such that $ \left(\frac{a-2}{N}\right)=1$ and $ \left(\frac{a+2}{N}\right)=1$ where $ \left(\frac{}{}\right)$ denotes Jacobi symbol. Let $ S_i=P_b(S_{i-1})$ with $ S_0$ equal to the modular $ P_{kb}(a)\phantom{5} \text{mod} \phantom{5} N$. Then, if $ N$ is prime then $ S_{n-1} \equiv P_{c-1}(a) \pmod{N}$ .

You can run this test here .

I have tested these claims for many random values of $k$ , $b$ , $n$ and $c$ and there were no counterexamples .

$\endgroup$
  • $\begingroup$ Again, after DavidSpeyer's answer 3 years ago, did you work on the order of $6-2\sqrt{3}\in \mathbb{Z}/P\mathbb{Z}[\sqrt{3}]^\times$ with $P = 2^p-1$ which is the core of the proof of the LLT for the Mersenne numbers ? If so then what finite ring and which elements are you looking at ? $\endgroup$ – reuns Oct 18 '18 at 4:20
3
+100
$\begingroup$

The two claims are true.

Proof for Claim 1 :

Let us prove by induction that $$S_i\equiv 2^{-kb^{i+1}}(s^{kb^{i+1}}+t^{kb^{i+1}})\pmod M\tag1$$ where $s:=a-\sqrt{a^2-4},t=a+\sqrt{a^2-4}$.

$(1)$ holds for $i=0$ since $$S_0\equiv P_{kb}(a)=2^{-kb}(s^{kb}+t^{kb})\pmod M$$

Supposing that $(1)$ holds for $i$ gives $$\begin{align}S_{i+1}&=P_b(S_i) \\\\&\equiv P_b(2^{-kb^{i+1}}(s^{kb^{i+1}}+t^{kb^{i+1}}))\pmod M \\\\&=2^{-b}\cdot\bigg(\bigg(2^{-kb^{i+1}}(s^{kb^{i+1}}+t^{kb^{i+1}})-\sqrt{(2^{-kb^{i+1}}(s^{kb^{i+1}}+t^{kb^{i+1}}))^2-4}\bigg)^b \\&\qquad\qquad+\bigg(2^{-kb^{i+1}}(s^{kb^{i+1}}+t^{kb^{i+1}})+\sqrt{(2^{-kb^{i+1}}(s^{kb^{i+1}}+t^{kb^{i+1}}))^2-4}\bigg)^b\bigg) \\\\&=2^{-b}\cdot\bigg(\bigg(2^{-kb^{i+1}}(s^{kb^{i+1}}+t^{kb^{i+1}})-\sqrt{(2^{-kb^{i+1}}(t^{kb^{i+1}}-s^{kb^{i+1}}))^2}\bigg)^b \\&\qquad\qquad +\bigg(2^{-kb^{i+1}}(s^{kb^{i+1}}+t^{kb^{i+1}})+\sqrt{(2^{-kb^{i+1}}(t^{kb^{i+1}}-s^{kb^{i+1}}))^2}\bigg)^b\bigg) \\\\&=2^{-b}\cdot\bigg(\bigg(2^{-kb^{i+1}}(s^{kb^{i+1}}+t^{kb^{i+1}})-2^{-kb^{i+1}}(t^{kb^{i+1}}-s^{kb^{i+1}})\bigg)^b \\&\qquad\qquad+\bigg(2^{-kb^{i+1}}(s^{kb^{i+1}}+t^{kb^{i+1}})+2^{-kb^{i+1}}(t^{kb^{i+1}}-s^{kb^{i+1}})\bigg)^b\bigg) \\\\&=2^{-kb^{i+2}}(s^{kb^{i+2}}+t^{kb^{i+2}})\qquad\square\end{align}$$

From $(1)$, we get, using $2(a\pm\sqrt{a^2-4})=(\sqrt{a+2}\pm\sqrt{a-2})^2$, $$\begin{align}S_{n-1}&\equiv 2^{-(M+c)}(s^{M+c}+t^{M+c})\pmod M \\\\&=2^{-2M-2c}\bigg((\sqrt{a+2}-\sqrt{a-2})^{2M+2c} \\&\qquad\qquad\qquad +(\sqrt{a+2}+\sqrt{a-2})^{2M+2c}\bigg)\tag2\end{align}$$

Here, we have, by the binomial theorem, $$\begin{align}&(\sqrt{a+2}\pm\sqrt{a-2})^{M} \\\\&=\sum_{k=0}^{M}\binom Mk(\sqrt{a+2})^{M-k}(\pm\sqrt{a-2})^k \\\\&=\sqrt{a+2}\sum_{j=0}^{(M-1)/2}\binom{M}{2j}(a+2)^{(M-2j-1)/2}(a-2)^{j} \\&\qquad\qquad \pm\sqrt{a-2}\sum_{j=1}^{(M+1)/2}\binom{M}{2j-1}(a+2)^{(M-2j+1)/2}(a-2)^{j-1}\end{align}$$

So, there are integers $C,D$ such that $$(\sqrt{a+2}\pm\sqrt{a-2})^{M}=C\sqrt{a+2}\pm D\sqrt{a-2}$$ where $$C=\sum_{j=0}^{(M-1)/2}\binom{M}{2j}(a+2)^{(M-2j-1)/2}(a-2)^{j}\equiv \left(\frac{a+2}{M}\right)\equiv 1\pmod M$$ and $$D=\sum_{j=1}^{(M+1)/2}\binom{M}{2j-1}(a+2)^{(M-2j+1)/2}(a-2)^{j-1}\equiv \left(\frac{a-2}{M}\right)\equiv -1\pmod M$$

From $(2)$, we get $$\begin{align}2^{2(M-1)}\cdot S_{n-1}&\equiv 2^{-2c-2}\left((\sqrt{a+2}-\sqrt{a-2})^{2M+2c}+(\sqrt{a+2}+\sqrt{a-2})^{2M+2c}\right)\pmod M \\\\&=2^{-2c-2}\bigg((\sqrt{a+2}-\sqrt{a-2})^{2c}(C\sqrt{a+2}- D\sqrt{a-2})^2 \\&\qquad +(\sqrt{a+2}+\sqrt{a-2})^{2c}(C\sqrt{a+2}+ D\sqrt{a-2})^2\bigg) \\\\&\equiv 2^{-2c-2}\bigg((\sqrt{a+2}-\sqrt{a-2})^{2c}(\sqrt{a+2}+\sqrt{a-2})^2 \\&\qquad +(\sqrt{a+2}+\sqrt{a-2})^{2c}(\sqrt{a+2}-\sqrt{a-2})^2\bigg)\pmod M \\\\&=2^{-2c+2}\bigg((\sqrt{a+2}-\sqrt{a-2})^{2c-2}+(\sqrt{a+2}+\sqrt{a-2})^{2c-2}\bigg) \\\\&=2^{-(c-1)}(s^{c-1}+t^{c-1}) \\\\&=P_{c-1}(a)\end{align}$$ It follows from $2^{2(M-1)}\equiv 1\pmod M$ that $$S_{n-1}\equiv P_{c-1}(a)\pmod M$$


Proof for Claim 2 :

From $(1)$, we get, similarly as above, $$\begin{align}2^{2(N-1)}\cdot S_{n-1}&\equiv 2^{N+c-2}(s^{N-c}+t^{N-c})\pmod N \\\\&=2^{2c-2}((\sqrt{s+2}-\sqrt{s-2})^{2N-2c}+(\sqrt{s+2}+\sqrt{s-2})^{2N-2c}) \\\\&=2^{2c-2}\bigg((\sqrt{s+2}-\sqrt{s-2})^{2N}\bigg(\frac{\sqrt{s+2}+\sqrt{s-2}}{4}\bigg)^{2c} \\&\qquad\qquad +(\sqrt{s+2}+\sqrt{s-2})^{2N}\bigg(\frac{\sqrt{s+2}-\sqrt{s-2}}{4}\bigg)^{2c}\bigg) \\\\&\equiv 2^{-2c-2}((\sqrt{s+2}-\sqrt{s-2})^2(\sqrt{s+2}+\sqrt{s-2})^{2c} \\&\qquad\qquad +(\sqrt{s+2}+\sqrt{s-2})^2(\sqrt{s+2}-\sqrt{s-2})^{2c})\pmod N \\\\&=2^{-2c+2}((\sqrt{s+2}+\sqrt{s-2})^{2c-2}+(\sqrt{s+2}-\sqrt{s-2})^{2c-2}) \\\\&=2^{-(c-1)}(s^{c-1}+t^{c-1}) \\\\&=P_{c-1}(a)\end{align}$$ It follows from $2^{2(N-1)}\equiv 1\pmod N$ that $$S_{n-1}\equiv P_{c-1}(a)\pmod N$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.