Generalizing algebraic factors on Riesel bases

[gd_barnes]

All factors up to 250 and their associated modulos have now been added to the 3rd post. I'm now in the process of checking the pages to see if any k's can be removed as a result of this analysis. I'll edit this post if I find any.

Edit: No new k's with partial algebraic factors were found, mainly because for the higher bases, we've mostly tested ones with fairly low conjectures at this point.

Note the interesting pattern of the Fibonacci numbers. Based on the observed pattern, I'll throw out the following before actually testing it:

A factor of 1597 occurs on b==(1596 mod 1597) where k=m^2 and m==(610 or 987 mod 1597).
-and-
A similar situation exists for a factor of 28657 on b==(28656 mod 28657).

Edit: I've now tested it. It is correct! :-) Aren't number patterns just grand?

So, here's a math puzzle for everyone. What is the next factor in this pattern?

[gd_barnes]

I have now turned this into a "formal" conjecture to cover all situations for all bases where f is a factor on odd-n and algebraic factors occur on even-n to make a full covering set for the form k*b^n-1.

See the 3rd post here for a specific defined set of conditions.

If there are any mathematics majors or enthusiasts that could come up with a formal proof, I'd be very interested to see it.

Edit: I have now asked for input on it in the GIMPS math forum.

[10metreh]

The algebraic factors will always be there as long as k is a square. The values of b and m don't matter.

I have worked out (after multiple scribblings) that your conjecture is equivalent to this:

For prime f == 1 (mod 4), there are always exactly 2 values z < f for which z² == f-1 (mod f).

I.e. x and y must be unique.


My simplification stems from the fact that when n is odd, bⁿ must be equivalent to b (mod f). As k*bⁿ == 1 (mod f) (this must be true for f to appear as a factor), k*b must also == 1 (mod f).

From here one can deduce that k == b (mod f).

Therefore m² == f-1 (mod f).

So x and y are the values of z < f for which z² == f-1 (mod f).


If x and y are unique, it is easy to prove that x+y must equal f, and Gary mentioned this in post 11: (note that f-x = y)

(f-x)²-x² = f²-2fx+x²-x² = f²-2fx, which is divisble by f.

Therefore y² (mod f) = x² (mod f)

This shows that x,y pairs where x+y = f have the same value mod f, so this applies for the value f-1 (mod f). If x and y is the only such pair, then x+y must equal f.


It is also very easy to show that f must be 1 (mod 4): I have already shown that m² == f-1 (mod f), and if f == 3 (mod f), then m² == 2 (mod 4). This is clearly impossible.


So we must prove that x and y are unique, i.e. that there cannot be more than 1 pair.


Edit: Aha!

Suppose there are 2 numbers, c and d (d > c) (equivalent to x and y but not necessarily fulfilling c+d = f), where 0 < c,d < f and c² and d² both == f-1 (mod f).

Therefore d²-c² = ef, where e is any whole number (not 2.718...).

Factorizing: (d+c)(d-c) = ef

f is prime, so either d+c or d-c must equal f.

If d-c equals f, then either c ≤ 0 or d > f, contradicting 0 < c,d < f.

Therefore d+c = f.

However, if there were two pairs of x and y, then it would have been possible to choose c and d so that c+d did not equal f.

Therefore there is only one x,y pair, so x and y are unique. QED


I have not detailed every single obvious part of the proof, but I think it is complete. Feel free to tell me if there is a gap (but not in an RDS way).

What I haven't worked out is how to determine x and y without working out the squares of each whole number below f (mod f).

[10metreh]

Well, no-one has pointed out a flaw after 7 hours, but then again, no-one has said that my proof is sound either...

[CRGreathouse]

Originally Posted by 10metreh

Well, no-one has pointed out a flaw after 7 hours, but then again, no-one has said that my proof is sound either...

I posted in the other thread. Your proof looks fine [modulo a minor concern raised on the other thread] but I have no idea how it relates to what gd_barnes wrote.

[10metreh]

For CRUS purposes:

Here is a table of x and y for each b = 4m where b+1 (= f) is prime, from b = 250 to 1000. gd_barnes is probably the only person who will understand this.

256  16, 241
268  82, 187
276  60, 217
280  53, 228
292  138, 155
312  25, 288
316  114, 203
336  148, 189
348  136, 213
352  42, 311
372  104, 269
388  115, 274
396  63, 334
400  20, 381
408  143, 266
420  29, 392
432  179, 254
448  67, 382
456  109, 348
460  48, 413
508  208, 301
520  235, 286
540  52, 489
556  118, 439
568  86, 483
576  24, 553
592  77, 516
600  125, 476
612  35, 578
616  194, 423
640  154, 487
652  149, 504
660  106, 555
672  58, 615
676  26, 651
700  135, 566
708  96, 613
732  353, 380
756  87, 670
760  39, 722
768  62, 707
772  317, 456
796  215, 582
808  318, 491
820  295, 526
828  246, 583
852  333, 520
856  207, 650
876  151, 726
880  387, 494
928  324, 605
936  196, 741
940  97, 844
952  442, 511
976  252, 725
996  161, 836

[Random Poster]

Originally Posted by 10metreh

Here is a table of x and y for each b = 4m where b+1 (= f) is prime, from b = 250 to 1000. gd_barnes is probably the only person who will understand this.

Why do you post a table that can be generated by a single line of code:

for(m=63,250,p=4*m+1;if(isprime(p),x=lift(sqrt(Mod(-1,p)));print(4*m"  "x", "p-x)))

That's PARI/GP code; other such programs will have something similar.

[Random Poster]

Originally Posted by 10metreh

I have not detailed every single obvious part of the proof, but I think it is complete. Feel free to tell me if there is a gap (but not in an RDS way).

The only problem I have with this is that your apparent result is so blindingly obvious fact of elementary number theory that you shouldn't need a pageful of rambling notation to "prove" it. (I don't mean to sound like Silverman, but you really should know what you are doing.)

Originally Posted by 10metreh

What I haven't worked out is how to determine x and y without working out the squares of each whole number below f (mod f).

There are efficient algorithms to take modular square roots; just use a program that implements one (see my other post).

[10metreh]

Originally Posted by Random Poster

The only problem I have with this is that your apparent result is so blindingly obvious fact of elementary number theory that you shouldn't need a pageful of rambling notation to "prove" it. (I don't mean to sound like Silverman, but you really should know what you are doing.)

In which case you need to give gd_barnes a telling off too. After all he was the one who asked someone to "prove" it.

[Random Poster]

Originally Posted by 10metreh

In which case you need to give gd_barnes a telling off too. After all he was the one who asked someone to "prove" it.

Why? What gd_barnes asked proof for was essentially this: "Let f be the greatest common divisor of m²+1 and b+1. If f is greater than 1, then m²bⁿ-1 is composite for all n." (This is actually stronger than what he wanted, since he restricted f to be prime and equal to b+1.) I don't see anything wrong with asking that, even if he didn't present it very well, and even though the statement is rather obviously true. But a proper response to that, in my opinion, would have been a compact reformulation of the statement and a short assertion that it's indeed true. Your response, on the other hand, was full of trivial detail and (like CRGreathouse said) not very clear about how it related to the original problem. I don't think that kind of thing is helpful to anyone.

[CRGreathouse]

Thank you, Random Poster; I don't think I would have figured that out on my own!