Special Form of Mersenne and Fermat Number Factors

[michael]

errata case a⁴ + 1

Same reasoning gives
(1) a^{[B]8[/B]k+[B]4[/B]} - 1 ≡ 0 mod p;
(2) ....=a^8k+[B]4[/B] + 1 ≡ 0 mop p

-michael

[ewmayer]

Originally Posted by ewmayer

If q is a proper factor of F(n), then the group defined by arithmetic modulo q has order q-1, and thus 2*p must divide q-1. Since 2*p = 2*2^n = 2^(n+1), Fermat number factors must have the form q = j*2^(n+1) + 1.

In this case, because the term multiplied by j is even rather than odd, we cannot conclude that j is a multiple of 2 based on a simple parity argument. The great Edouard Lucas (yep, that Lucas) was the first to show j is in fact itself even, i.e. Fermat factors have form k*2^(n+2) + 1; when I get a chance to look up his proof of that fact I'll add it to this post if it's sufficiently simple to follow.

I was looking over several of these long-dormant threads on the Math forum today, and see that Bob Silverman gives a nice proof of the latter fact (using the theory of quadratic residues and Euler's criterion) on this thread:

http://www.mersenneforum.org/showthread.php?t=2811

[Dougy]

Theorem 1: Let q be an odd prime divisor of 2^p-1 where p is an odd prime. Then q = 2pk + 1 for some natural number k.

Proof:
Since q divides 2^p-1 we know that 2^p = 1 mod q
By Fermat's Little Theorem 2^q-1 = 1 mod q

Hence 2^GCD(p,q-1) = 1 mod q.

GCD(p,q-1) = 1 is nonsense. So GCD(p,q-1) > 1. Since p is a prime p must divide q-1. Hence q-1 = cp for some natural number c. c is even since q and p were assumed to be odd.

Theorem 2: Let q be an odd prime divisor of 2^p-1 where p is an odd prime. Then q = 8n +/- 1 for some natural number n.

Proof:
Consider 2(2^p-1) = 2^p+1 - 2 = x^2 - 2 where x = 2^((p+1)/2).
Since q divides 2^p-1 then q divides x^2 - 2. So x^2 = 2 mod q.

As q is odd, q is of the form 8n +/- 1 or 8n +/- 3. We will contradict the latter case.

Since the equation x^2 = 2 mod q has an integer solution, we know that 2 is a quadratic residue modulo q. However if q = 8n +/- 3, then 2 is not a quadratic residue modulo q.

Why from these:
2^p = 1 mod q
2^(q-1) = 1 mod q
You conclude this:
2^GCD(p,q-1) = 1 mod q
?
proof?

[R.D. Silverman]

Originally Posted by marnes

Why from these:
2^p = 1 mod q
2^(q-1) = 1 mod q
You conclude this:
2^GCD(p,q-1) = 1 mod q
?
proof?

Hint1: Look up Lagrange's Theorem
Hint2: Given the results of performing Hint1, what can you conclude
about GCD(p,q-1)????

[WsF]

Originally Posted by Dougy

Theorem 2: Let q be an odd prime divisor of 2^p-1 where p is an odd prime. Then q = 8n +/- 1 for some natural number n.
Proof:Consider 2(2^p-1) = 2^p+1 - 2 = x^2 - 2 where x = 2^((p+1)/2).
Since q divides 2^p-1 then q divides x^2 - 2. So x^2 = 2 mod q.
As q is odd, q is of the form 8n +/- 1 or 8n +/- 3. We will contradict the latter case.
Since the equation x^2 = 2 mod q has an integer solution, we know that 2 is a quadratic residue modulo q. However if q = 8n +/- 3, then 2 is not a quadratic residue modulo q.

I'm not good in dealing with quadratic residues. But I've found that q=2k+1 is a divisor of Mp if there exists a solution of equation x^2=k+1 mod q.
Example: 23 can be a divisor of 2^11-1 (and it is) since 9^2=81=12 mod 23.
I've checked some q's and in all cases q=+/-1 mod 8. The reciprocal theorem is false, i.e. not all q=+/-1 (mod 8) have solution of the equation provided (e.g. q=111, 121). Some results:

   x^2      k+1         q
 19^2 =   52 mod  103 (=7 mod 8), for k=  51
  31^2 =   57 mod  113 (=1 mod 8), for k=  56
  37^2 =   60 mod  119 (=7 mod 8), for k=  59   two solutions
  54^2 =   60 mod  119 (=7 mod 8), for k=  59
   8^2 =   64 mod  127 (=7 mod 8), for k=  63
  53^2 =   69 mod  137 (=1 mod 8), for k=  68
  23^2 =   76 mod  151 (=7 mod 8), for k=  75
   9^2 =   81 mod  161 (=1 mod 8), for k=  80 two solutions
  37^2 =   81 mod  161 (=1 mod 8), for k=  80
  77^2 =   84 mod  167 (=7 mod 8), for k=  83
  67^2 =   96 mod  191 (=7 mod 8), for k=  95
  26^2 =   97 mod  193 (=1 mod 8), for k=  96
  10^2 =  100 mod  199 (=7 mod 8), for k=  99

Two questions:
1. Can it be proven that x^2=(k+1) mod (q=2k+1) has solution for q=+/-1 mod 8 only?
2. Is there anything common in these two approaches (equations x^2=2 and x^2=k+1)?

[alpertron]

Originally Posted by WsF

Two questions:
1. Can it be proven that x^2=(k+1) mod (q=2k+1) has solution for q=+/-1 mod 8 only?
2. Is there anything common in these two approaches (equations x^2=2 and x^2=k+1)?

First notice that x^2 = 1 (mod 2k+1) has solutions: x = (+/-)1.

Now 1 = 2k+2 = 2(k+1) (mod 2k+1)

This means that k+1 is a quadratic residue if and only if 2 is a quadratic residue mod 2k+1: if x^2 = 2 and y^2 = k+1 then xy = (+/-)1 (mod 2k+1)

[WsF]

Can we obtain more strict restriction on q? In the short listing presented above for 50<k<100 (49 numbers) only 11 of them have solutions [59 and 80 two solutions] of x^2=2 and y^2=k+1 (at the same time, as you've shown).
In the range 1<k<10^4 there are 2527 solutions, but the number of k's is smaller since there are multiple solutions, e.g. for q=19873 (k=9936) x=411, 3250, 4933, 7772. So, the number of solutions is more or less OK (one fourth) but the number of k's (so q's) is smaller.
In the range 1<k<10^4 a number of different k's is 1798. Is there a simple rule to eliminate this 0.25-0.18=0.07=7.0% of the range investigated? This 7% in the range gives 28% (702/2500) in a set of q=+/-1 mod 8.

[science_man_88]

Originally Posted by WsF

Can we obtain more strict restriction on q? In the short listing presented above for 50<k<100 (49 numbers) only 11 of them have solutions [59 and 80 two solutions] of x^2=2 and y^2=k+1 (at the same time, as you've shown).
In the range 1<k<10^4 there are 2527 solutions, but the number of k's is smaller since there are multiple solutions, e.g. for q=19873 (k=9936) x=411, 3250, 4933, 7772. So, the number of solutions is more or less OK (one fourth) but the number of k's (so q's) is smaller.
In the range 1<k<10^4 a number of different k's is 1798. Is there a simple rule to eliminate this 0.25-0.18=0.07=7.0% of the range investigated? This 7% in the range gives 28% (702/2500) in a set of q=+/-1 mod 8.

I've been doing some thought on Mersenne number factors and I've found something I like and that's that the odds of a number with 3 factors having 2 of the same modulo 24 is 80% if I do my math correctly ( used some scripting to help).

[ewmayer]

Quick necropost to tie up a few loose ends related to the extra power of 2 (over the 2^(n+1) known to Euler) proved to be present in Fermat number factors by Lucas. In the first quoted snip below I've modified my initial notation (replacing q by p for the factor and p by 2^n for the Fermat number exponent ... I had originally used q,p by way of analogy with Mersenne number factors):

Originally Posted by ewmayer

If p is a proper factor of F(n), then the group defined by arithmetic modulo p has order p-1, and thus 2*2^n must divide p-1. [Thus], Fermat number factors must have the form p = j*2^(n+1) + 1.

In this case, because the term multiplied by j is even rather than odd, we cannot conclude that j is a multiple of 2 based on a simple parity argument. The great Edouard Lucas (yep, that Lucas) was the first to show j is in fact itself even, i.e. Fermat factors have form k*2^(n+2) + 1; when I get a chance to look up his proof of that fact I'll add it to this post if it's sufficiently simple to follow.

Later I added

Originally Posted by ewmayer

I was looking over several of these long-dormant threads on the Math forum today, and see that Bob Silverman gives a nice proof of the latter fact (using the theory of quadratic residues and Euler's criterion) on this thread:

http://www.mersenneforum.org/showthread.php?t=2811

Here is what RDS wrote there:

Originally Posted by Bob Silverman

Assume 2^2^n + 1 = 0 mod p
Then 2^2^n = -1 mod p
2^2^(n+1) = 1 mod p
By Lagrange's Thm, the order of any element must divide the order of the
group. The order of the group is p-1, hence

2^(n+1) | p - 1 and therefore p = k* 2^(n+1) + 1 for some k.

But we can say more. Note that for n > 1, we also have p = 1 mod 8.
By quadratic reciprocity 2 is a quadratic residue. From Euler's criteria we
then obtain:

2^ ((p-1)/2) = 1 mod p and hence (2^(n+1)) | (p-1)/2. This last result
yields p = k^2^(n+2) + 1.

Euler's criterion says that a^((p-1)/2) = 1 or -1 mod p depending on
whether a is (resp.) a residue or non-residue.

Note that we can also prove the same thing without invoking quadratic reciprocity (or perhaps better, without doing so explicitly). As Bob notes (following Lucas' argument), assuming that n > 1, any factor p must == 1 (mod 8), thus 2 is a quadratic residue (mod p), i.e. there exists an integer m such that m^2 == 2 (mod p). [QR]

For this altrnate proof we want to make use of the fact that 2^2^(n+1) == +1 (mod p), so raise both sides of [QR] to the 2^(n+1)th power:

(m^2)^2^(n+1) = m^2^(n+2) == 2^2^(n+1) == +1 (mod p),

from which it immediately follows that the image of m has order 2^(n+2) in the multiplicative group (mod p),
thus we have added one more power of 2 to the basic form of our factors: p == 1 (mod 2^(n+2)).