mersenneforum.org Generalizing algebraic factors on Riesel bases
 Register FAQ Search Today's Posts Mark Forums Read

 2010-04-02, 03:11 #12 gd_barnes     May 2007 Kansas; USA 27BF16 Posts 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? Last fiddled with by gd_barnes on 2010-04-02 at 05:35
 2010-04-02, 03:55 #13 gd_barnes     May 2007 Kansas; USA 52·11·37 Posts 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. Last fiddled with by gd_barnes on 2010-04-02 at 04:08 Reason: edit
 2010-04-02, 11:13 #14 10metreh     Nov 2008 2·33·43 Posts 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 z2 == f-1 (mod f). I.e. x and y must be unique. My simplification stems from the fact that when n is odd, bn must be equivalent to b (mod f). As k*bn == 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 m2 == f-1 (mod f). So x and y are the values of z < f for which z2 == 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)2-x2 = f2-2fx+x2-x2 = f2-2fx, which is divisble by f. Therefore y2 (mod f) = x2 (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 m2 == f-1 (mod f), and if f == 3 (mod f), then m2 == 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 c2 and d2 both == f-1 (mod f). Therefore d2-c2 = 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). Last fiddled with by 10metreh on 2010-04-02 at 12:07
 2010-04-02, 18:25 #15 10metreh     Nov 2008 44228 Posts Well, no-one has pointed out a flaw after 7 hours, but then again, no-one has said that my proof is sound either...
2010-04-02, 19:05   #16
CRGreathouse

Aug 2006

586310 Posts

Quote:
 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.

Last fiddled with by CRGreathouse on 2010-04-02 at 19:05

 2010-04-03, 07:50 #17 10metreh     Nov 2008 1001000100102 Posts 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. Code: 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 Last fiddled with by gd_barnes on 2010-04-06 at 00:24 Reason: correct b+1=314, 318 to 312, 316
2010-04-03, 09:07   #18
Random Poster

Dec 2008

179 Posts

Quote:
 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:
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.

2010-04-03, 09:19   #19
Random Poster

Dec 2008

179 Posts

Quote:
 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.)
Quote:
 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).

2010-04-03, 10:42   #20
10metreh

Nov 2008

2·33·43 Posts

Quote:
 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.

2010-04-03, 21:48   #21
Random Poster

Dec 2008

179 Posts

Quote:
 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 m2+1 and b+1. If f is greater than 1, then m2bn-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.

 2010-04-03, 23:36 #22 CRGreathouse     Aug 2006 16E716 Posts Thank you, Random Poster; I don't think I would have figured that out on my own!

 Similar Threads Thread Thread Starter Forum Replies Last Post pepi37 Conjectures 'R Us 95 2017-07-04 13:37 R. Gerbicz Conjectures 'R Us 22 2009-12-29 20:21 Siemelink Conjectures 'R Us 105 2009-09-04 06:40 henryzz ElevenSmooth 13 2007-12-18 09:12 robert44444uk Conjectures 'R Us 139 2007-12-17 05:17

All times are UTC. The time now is 09:08.

Sat Aug 8 09:08:32 UTC 2020 up 22 days, 4:55, 1 user, load averages: 2.58, 2.22, 2.09