mersenneforum.org > Math Understanding the LL proof and then more related stuff following it
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2012-05-24, 03:08 #1 Raman Noodles     "Mr. Tuch" Dec 2007 Chennai, India 3·419 Posts Understanding the LL proof and then more related stuff following it 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 2p-1 is being prime if and only if 2p-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.Mp(2+√3)2[SUP]p-2[/SUP]-1 (2+√3)2[SUP]p[/SUP] = (R.Mp(2+√3)2[SUP]p-2[/SUP]-1)2 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.M31(2+√3)2[SUP]29[/SUP]-1 So, the order for the element (2+√3) for modulo M31 = 231? Ridiculous. Please explain. Although on the right hand side, one less than a multiple of M31 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(231) 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 2odd exponent numbers it follows that 3 is being a quadratic non residue (mod Mp) the √3, 2+√3 these elements belong to the finite field GF(Mp2) but still, how can we yet consider the fact that (2+√3)2[SUP]p-1[/SUP] = -1 (mod Mp), whereby the element 2+√3 belongs to the finite field GF(Mp2) Can someone please explain the LL proof in terms of the field theory? 2+√3 is being a root for the polynomial x2-4x+1 So, the proof reduces to proving the following (these) individual parts (portions) 1. x2-4x+1 is being an irreducible polynomial (mod Mp) 2. The order for x being generated with this polynomial inside GF(Mp2) is being exactly equal to Mp+1 (Not 2(Mp+1), etc at all, this is being the order when generated by using the polynomial x2-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 (2p-1) if the order for 2+√3 mod Mp = Mp+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 x2-kx+1 mod Mp = Mp+1 rather. That's it besides the condition that x2-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] Last fiddled with by Raman on 2012-05-24 at 03:52
2012-05-24, 03:23   #2
cheesehead

"Richard B. Woods"
Aug 2002
Wisconsin USA

1E0C16 Posts

Quote:
 Originally Posted by Raman Although on the right hand side, one less than a multiple of M31 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)n will neutralize the corresponding odd powers of +√3 in the expansions of (2+√3)n? 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?

Last fiddled with by cheesehead on 2012-05-24 at 03:42 Reason: various

2012-05-24, 03:36   #3
Raman
Noodles

"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts
A071642, A001122

Quote:
 Originally Posted by Raman 1. x2-4x+1 is being an irreducible polynomial (mod Mp)
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 (x823+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 2q-1, i.e. the order of 2 (mod p) = q.
Prove that the polynomial (xp+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)
(x1613+1)/(x+1) factors out into equal degree irreducible polynomials of order 52
(x1801+1)/(x+1) factors out into equal degree irreducible polynomials of order 25
(x2113+1)/(x+1) factors out into equal degree irreducible polynomials of order 44
(x2143+1)/(x+1) factors out into equal degree irreducible polynomials of order 51
(x2593+1)/(x+1) factors out into equal degree irreducible polynomials of order 81
(x2731+1)/(x+1) factors out into equal degree irreducible polynomials of order 26

(xp+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

x16 + x15 + x14 + x13 + x12 + x11 + x10 + x9 + x8 + x7 + x6 + x5 + x4 + x3 + x2 + x + 1 = (x8 + x5 + x4 + x3 + 1) (x8 + x7 + x6 + x4 + x2 + x + 1)
in Z2

2012-05-24, 04:14   #4
Raman
Noodles

"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts

Quote:
 Originally Posted by cheesehead Have you doublechecked that all the odd powers of -√3 in the expansions of (2-√3)n will neutralize the corresponding odd powers of +√3 in the expansions of (2+√3)n? 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.Mp(2+√3)2[SUP]p-2[/SUP]-1)2
but that the following term (2-√3) does not occur wherever within this equation at all

Last fiddled with by Raman on 2012-05-24 at 04:17

2012-05-24, 05:37   #5
Raman
Noodles

"Mr. Tuch"
Dec 2007
Chennai, India

3·419 Posts

Quote:
 Originally Posted by Raman 2. The order for x being generated with this polynomial inside GF(Mp2) is being exactly equal to Mp+1 (Not 2(Mp+1), etc at all, this is being the order when generated by using the polynomial x2-4x-1)
Consider the case for the Fibonacci numbers, Lucas numbers as well
What is being the shortest way to prove that
Fp (Fibonacci number, prime index p) ≡ ± 1 (mod p), p ≠ 5
Lp (Lucas number, prime index p) ≡ 1 (mod p)

But, both these sequences essentially make use of the same generating polynomial, namely x2-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, x2-x-1 (whose roots are being namely (1+√5)/2, (1-√5)/2) is being reducible over GF(p), thereby Fp = 1 (mod p)
If p = 2, 3 mod 5, then this polynomial x2-x-1 going to be irreducible over GF(p), its roots will be in GF(p2), Fp = -1 (mod p) as follows

Code:
           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 Lp = 1 (mod p) everytime, even works out for p = 5.

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

Code:
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 Lp ≡ 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 Lp ≡ 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 102-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)
x2-x-1 mod 5
= (x+2)2 mod 5

General solution = A.3n + B.n.3n 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 3n mod 5 = 4
Period for Fn = 2.n.3n mod 5 = 20
Period for Ln = 2.3n mod 5 = 4

Code:
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(p2), order = divisor for p2-1

then for example period for x2-x-1, irreducible polynomial (mod 2) = 3
period for x2-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 x2-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 x2-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 x2-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

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post a nicol Math 7 2017-03-28 11:08 Fred PrimeNet 3 2016-05-19 13:40 Fred Hardware 33 2016-04-27 04:42 Demonslay335 YAFU 11 2016-01-08 17:52 zacariaz Homework Help 32 2007-05-16 15:18

All times are UTC. The time now is 04:23.

Mon Oct 25 04:23:54 UTC 2021 up 93 days, 22:52, 0 users, load averages: 0.65, 1.08, 1.24

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.