View Single Post
Old 2018-12-21, 15:12   #1
science_man_88's Avatar
"Forget I exist"
Jul 2009

26·131 Posts
Default Modified Form of LL Test?

Iterated function on Wikipedia has two examples that are relevant:

\[f(x)=ax+b\to f^n(x)=a^nx+ \frac{a^n-1}{a-1}b\]


\[f(x)=ax^2+bx+\frac{b^2-2b-8}{4a}\to f^n(x)=\frac{2\alpha^{2^n}+2\alpha^{-2^n}-b}{2a}\]



The first is the way Mersenne numbers iterate with a=2,b=1 . The second is how the the Lucas-Lehmer test variants iterate. The normal Lucas-Lehmer test sequence (prior to mod) is a=1,b=0. The reduced version using \(2x^2-1\) is a=2,b=0. I chose to look at the latter as it shares a possible x value with the Mersenne numbers.
Now getting the b values to equate was a priority for me ( because it simplifies the expressions if they both equal 0, as then b can be taken out of the variables). Allowing b to go to b-1 without changing the value of the first n-th iterate gives the following:


Now we can eliminate all the b values and any direct multiplies by b from both n-th iterates giving:






Next thing to note is that a is equal in both cases (namely a=2). Plugging that fact, plus \(a=\frac{x-1}{3}\) for our common x value into the first case, and the whole set of equations in the second reduces to :

\[f^n(x)=\left ( \frac{x-1}{3}\right )^nx+\left ( \frac{x-1}{3}\right )^n-1\]





My main question is:

What's the simplified version of their modular remainder ( second mod first)?

that can allow us to solve for a relation n+3 must have to get 0 out and therefore all odd Mersenne prime exponents.

(Idea for this thread, was from: ewmayer and CRGreathouse)

Last fiddled with by science_man_88 on 2018-12-21 at 15:21
science_man_88 is offline