Understanding the LL proof and then more related stuff following it

[Raman]

From within the LL proof given within the following page
http://primes.utm.edu/notes/proofs/LucasLehmer.html
I've got some gaps in understanding the proof

It says that 2^p-1 is being prime if and only if
2^p-1 divides (2+√3)^2[SUP]p-2[/SUP] + (2-√3)^2[SUP]p-2[/SUP]
OK, but this yields
(2+√3)^2[SUP]p-1[/SUP] = R.M_p(2+√3)^2[SUP]p-2[/SUP]-1
(2+√3)^2[SUP]p[/SUP] = (R.M_p(2+√3)^2[SUP]p-2[/SUP]-1)²
where R should be an integer, as such

For example, when p = 31, R = [S(4) mod 2147483647]/31
R = 1214
does that mean that
(2+√3)^2[SUP]30[/SUP] = 1214.M₃₁(2+√3)^2[SUP]29[/SUP]-1
So, the order for the element (2+√3) for modulo M₃₁ = 2³¹?
Ridiculous. Please explain. Although on the right hand side, one less than a multiple of M₃₁ occurs, but rather 2+√3 is not going to be an integer at all. How will you overcome this situation?

OK, it occurs to me that I have to view that element 2+√3 as such, inside the finite field GF(2³¹)
but that the law of quadratic reciprocity states that
3 is being a quadratic residue (mod p) iff p is being a quadratic residue (mod 3) if p = 1 mod 4
3 is being a quadratic residue (mod p) iff p is being a quadratic non residue (mod 3) if p = 3 mod 4

But, as since 3 is being a quadratic residue (mod p) iff p = 1 (mod 3); if p = 0 (mod 3) then (3/p) = 0
Combining putting these things together
3 is being a quadratic residue (mod p) iff p = 1, 11 mod 12
3 is being a quadratic non residue (mod p) iff p = 5, 7 mod 12

Since the Mersenne Primes are being 7 (mod 12), the 2^{odd exponent} numbers
it follows that 3 is being a quadratic non residue (mod M^p)
the √3, 2+√3 these elements belong to the finite field GF(M_p²)
but still, how can we yet consider the fact that
(2+√3)^2[SUP]p-1[/SUP] = -1 (mod M_p), whereby the element 2+√3 belongs to the finite field GF(M_p²)

Can someone please explain the LL proof in terms of the field theory?
2+√3 is being a root for the polynomial x²-4x+1
So, the proof reduces to proving the following (these) individual parts (portions)
1. x²-4x+1 is being an irreducible polynomial (mod M_p)
2. The order for x being generated with this polynomial inside GF(M_p²) is being exactly equal to M_p+1
(Not 2(M_p+1), etc at all, this is being the order when generated by using the polynomial x²-4x-1)
3. What will be the value for then (2+√3)^2[SUP]p-2[/SUP] + (2-√3)^2[SUP]p-2[/SUP] mod (2^p-1) if the order for 2+√3 mod M_p = M_p+1
It seems to not give the value for the variable (2+√3)^2[SUP]p-2[/SUP] at all; but that the order for 2-√3 should be the same thing, as since that 2-√3 = (2+√3)^-1

Now that a frequently asked question comes thereby: What other values for the LL test could one can start with, instead for S(1) = 4?
I presume that order for x²-kx+1 mod M_p = M_p+1 rather. That's it besides the condition that x²-kx+1 should be an irreducible polynomial?

^{[SUP][SUP][SUP][SUP]Being very similar to that for "Can zero be an intermediate iteration result value for the LL test?" being asked by someone else}[/SUP][/SUP][/SUP][/SUP]

[cheesehead]

Originally Posted by Raman

Although on the right hand side, one less than a multiple of M₃₁ occurs, but rather 2+√3 is not going to be an integer at all. How will you overcome this situation?

Have you doublechecked that all the odd powers of -√3 in the expansions of (2-√3)ⁿ will neutralize the corresponding odd powers of +√3 in the expansions of (2+√3)ⁿ? There shouldn't be any nonintegral parts left over after the two expansions are added.

I know this is elementary, but why would "2+√3 is not going to be an integer" be any problem to be overcome after the two complementary expansions are added?

[Raman]

Originally Posted by Raman

1. x²-4x+1 is being an irreducible polynomial (mod M_p)

What is being the best known algorithm to test out whether a polynomial is being irreducible in a finite field GF(p)? What is being the best known algorithm to factor the polynomial in the finite field GF(p)?

For the polynomial (x⁸²³+1)/(x+1), in GF(2)
PARI/GP makes use of the Berlekamp algorithm, but rather how does it work out? Any significance of using it for the integer factorization, such as the Cunningham numbers? Why/Why not?

Question. Let p be a prime factor for the least Mersenne number 2^q-1, i.e. the order of 2 (mod p) = q.
Prove that the polynomial (x^p+1)/(x+1) in GF(2) splits out into (p-1)/q equal degree irreducible polynomials of order q.

For example, for the following polynomials in GF(2)
(x¹⁶¹³+1)/(x+1) factors out into equal degree irreducible polynomials of order 52
(x¹⁸⁰¹+1)/(x+1) factors out into equal degree irreducible polynomials of order 25
(x²¹¹³+1)/(x+1) factors out into equal degree irreducible polynomials of order 44
(x²¹⁴³+1)/(x+1) factors out into equal degree irreducible polynomials of order 51
(x²⁵⁹³+1)/(x+1) factors out into equal degree irreducible polynomials of order 81
(x²⁷³¹+1)/(x+1) factors out into equal degree irreducible polynomials of order 26

(x^p+1)/(x+1) is being an irreducible polynomial in GF(2) if and only if, then 2 is being a primitive root (mod p), then 2 quadratic non residue mod p, p = 3, 5 mod 8

x¹⁶ + x¹⁵ + x¹⁴ + x¹³ + x¹² + x¹¹ + x¹⁰ + x⁹ + x⁸ + x⁷ + x⁶ + x⁵ + x⁴ + x³ + x² + x + 1 = (x⁸ + x⁵ + x⁴ + x³ + 1) (x⁸ + x⁷ + x⁶ + x⁴ + x² + x + 1)
in Z₂

[Raman]

Originally Posted by cheesehead

Have you doublechecked that all the odd powers of -√3 in the expansions of (2-√3)ⁿ will neutralize the corresponding odd powers of +√3 in the expansions of (2+√3)ⁿ? There shouldn't be any nonintegral parts left over after the two expansions are added.

I know this is elementary, but why would "2+√3 is not going to be an integer" be any problem to be overcome after the two complementary expansions are added?

No, it's not. To be better, I was rather being talking referring to the following equation,
(2+√3)^2[SUP]p[/SUP] = (R.M_p(2+√3)^2[SUP]p-2[/SUP]-1)²
but that the following term (2-√3) does not occur wherever within this equation at all

[Raman]

Originally Posted by Raman

2. The order for x being generated with this polynomial inside GF(M_p²) is being exactly equal to M_p+1
(Not 2(M_p+1), etc at all, this is being the order when generated by using the polynomial x²-4x-1)

Consider the case for the Fibonacci numbers, Lucas numbers as well
What is being the shortest way to prove that
F_p (Fibonacci number, prime index p) ≡ ± 1 (mod p), p ≠ 5
L_p (Lucas number, prime index p) ≡ 1 (mod p)

But, both these sequences essentially make use of the same generating polynomial, namely x²-x-1, for the Fibonacci numbers
According to the law of quadratic reciprocity
5 is being a quadratic residue mod p if and only if p is being a quadratic residue mod 5
p is being a quadratic residue mod 5 if and only if p = 1, 4 mod 5

If p = 1, 4 mod 5, x²-x-1 (whose roots are being namely (1+√5)/2, (1-√5)/2) is being reducible over GF(p), thereby F_p = 1 (mod p)
If p = 2, 3 mod 5, then this polynomial x²-x-1 going to be irreducible over GF(p), its roots will be in GF(p²), F_p = -1 (mod p) as follows

           0 mod p   if p = 5
  F_p = {  1 mod p   if p = 1 or 4 mod 5
          -1 mod p   if p = 2 or 3 mod 5

This I would prove using some knowledge of finite fields.  You see, if
p is 1 or 4 mod 5, then 5 is a quadratic residue mod p (see Quadratic
Reciprocity), which means that there is a square root x of 5 mod p, so
x^2 = 5 mod p.  It turns out that if you set

  a = (1+x)/2, b = (1-x)/2

then you have

  F_p = (a^p - b^p)/x mod p,

which you can prove in the same way that you prove the formula over
the real numbers.  In this case, Fermat's Little Theorem says that

  a^p = a (mod p)

which means that

  F_p = (a - b)/x = (x)/x = 1 mod p.

On the other hand, if p is 2 or 3 mod 5, then 5 is a quadratic
nonresidue mod p, which means that the square root of 5 mod p belongs
to a quadratic extension of the finite field of p elements.  In fact,
it is in the finite field of p^2 elements.  Then if r and s are in the
base field (with p elements), then you have (in this field of p^2
elements)

  (r + s*sqrt(5))^p = r^p + s^p*5^((p-1)/2)*sqrt(5)
                    = r + s*(5/p)*sqrt(5)

where the first equality follows from the Binomial Theorem, and the
second from Fermat's Little Theorem and from the fact that the
Legendre symbol, written (m/p) above, equals m^((p-1)/2) mod p.  Since
5 is a nonresidue, that means that

  (r + s*sqrt(5))^p = r - s*sqrt(5).

In the case where r = 1/2 and s = 1/2 or -1/2, we find that

  (r + s*sqrt(5))(r - s*sqrt(5)) = (r^2 - 5s^2) = -1

and therefore

  a^p = -1/a
  b^p = -1/b

so

  F_p = (a^p - b^p)/x
      = (-1/a + 1/b)/x mod p
      = (a - b)/(abx) mod p
      = 1/ab mod p
      = -1 mod p.

You can do a similar analysis for the Lucas numbers, but the formula
should be

  L_p = a^p + b^p.

I don't know how for the Lucas numbers, eventhough it uses the same generating polynomial, as such, but L_p = 1 (mod p) everytime, even works out for p = 5.

In fact every prime factor for F_p, L_p as well satisfies these conditions each
EVERY prime FACTOR for F_p ≡ ± 1 (mod p), p ≥ 7
EVERY prime FACTOR for L_p ≡ 1 (mod p)

suppose that p is a prime, and suppose that q is a prime factor
of F_p.  Let's also assume that p is not 5, as I've already pointed
out that F_5 = 5 breaks your rule.  You can step out the Fibonacci
numbers mod 5 to show that if p is not divisible by 5, then F_p will
not be divisible by 5, so we can also assume that q is not 5.

Similarly, you can check that F_p is even if and only if p is
divisible by 3, so after checking F_3 = 2, we can assume that q is not 2.

Now, recall what I said before about the algebraic numbers a and b,

  a = (1+x)/2, b = (1-x)/2


where x is a square root of 5.  If 5 is quadratic residue mod q, then
x is an element of the finite field with q elements, so a and b have
order dividing q-1.  So too their ratio a/b will have order dividing
q-1.  If 5 is not a quadratic residue mod q, then x is quadratic over
that field, so it belongs to the finite field with q^2 elements, and
in fact a and b have order dividing q+1, as I demonstrated before, and
therefore so too their ratio a/b will have order dividing q+1.

Now, since q is a factor of F_p, that means that

  F_p = (a^p - b^p)/x = 0 (mod q).

Multiplying both sides of the equation by x, we conclude that

  a^p - b^p = 0 (mod q)

or

  a^p = b^p (mod q).

Since q is not 2 or 5, b is nonzero mod q, so we can divide both sides
of the equation by b^p and get

  (a/b)^p = 1 (mod q),

which means that a/b has order (mod q) dividing p.  Since p is a prime
number, that order can only be either 1 or p.  Order 1 would mean that
a = b, which implies x = 0 (mod q), which is impossible since q is not
5.  So a/b has order p.  But we already established that a/b has order
dividing q-1 or q+1 (according to whether 5 is a quadratic residue mod
q).  Therefore, p divides either q-1 or q+1, which is exactly what you
wanted to prove.

Besides that for the Lucas numbers, all the prime factors for L_p ≡ 1 (mod p), it happens that they are being congruent to 1, 9 (mod 10). I am struggling to prove with this fact. Please help out. It is quite immediate to visualize for the (mod 2) case, but to observe for the (mod 5) case?

How to Prove that any prime factor for L_p ≡ 1, 4 (mod 5).
Is 5 being a quadratic residue, or otherwise quadratic non-residue for the Lucas number case?

For the period for the Fibonacci numbers, Lucas numbers (mod 10), once more that the Fibonacci numbers are being strange, exotic in comparison to the Lucas numbers. According to the pairs of numbers that come together to repeat the last digit (mod 10), there should be 10²-1 = 99 such pairs, excluding the (0, 0) element, so the period should be a divisor for 99? For the Fibonacci numbers it is being 60, for the Lucas numbers it is being 12.

This is due to the existence for the repeated root for the Fibonacci numbers case (mod 5)
x²-x-1 mod 5
= (x+2)² mod 5

General solution = A.3ⁿ + B.n.3ⁿ mod 5
A = 0, B = 2 for the Fibonacci numbers
A = 2, B = 0 for the Lucas numbers

period for n mod 5 = 5
period for 3ⁿ mod 5 = 4
Period for F_n = 2.n.3ⁿ mod 5 = 20
Period for L_n = 2.3ⁿ mod 5 = 4

It appears that within the pair of numbers from inside the finite field GF(52), with the exception for (0, 0), the polynomial x2-x-1, for the Lucas number case seems to generate x+2, 3x+1, 4x+3, 2x+4 these four elements, for the Fibonacci number case everything else those twenty elements

Mod 5 the Lucas Sequence follows as into
(2,1), (1,3), (3,4), (4,2) consecutive elements

GF(52) supports 24 elements, such that the terms follow the case for the series (the constant term, the coefficient for x)

Period (mod p)
Whenever that p = 1, 4 mod 5, then 5 is being quadratic residue mod p
√5 belongs to GF(p), order = p-1.
Whenever that p = 2, 3 mod 5, then 5 is being quadratic non residue mod p
√5 belongs to GF(p²), order = divisor for p²-1

then for example period for x²-x-1, irreducible polynomial (mod 2) = 3
period for x²-x-1, irreducible polynomial (mod 3) = 8

Merging these two results, we will get that
period for Fibonacci numbers = 60 (mod 10)
period for Lucas numbers = 12 (mod 10)

For many of the numbers, period for x²-x-1, irreducible polynomial (mod p), p ≡ 2, 3 mod 5 = 2(p+1)
but this is not being the case at all everytime
for this condition consideration, take away p = 47, period for x²-x-1, irreducible polynomial (mod 47) = 32, not 96 at all

If whenever that p = 1, 4 mod 5, then this implies that the polynomial x²-x-1 is being reducible inside GF(p), two roots whose difference is being 1, whose product is being -1, exist in (from within) GF(p)
Consequence.
Corollary. There exist two adjacent numbers < p whose product is being 1 (mod p), they exist if and only if, p = 1, 4 mod 5
i.e. (5/p) = 1