20100402, 03:11  #12 
May 2007
Kansas; USA
27BF_{16} 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 20100402 at 05:35 
20100402, 03:55  #13 
May 2007
Kansas; USA
5^{2}·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 oddn and algebraic factors occur on evenn to make a full covering set for the form k*b^n1.
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 20100402 at 04:08 Reason: edit 
20100402, 11:13  #14 
Nov 2008
2·3^{3}·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 z^{2} == f1 (mod f). I.e. x and y must be unique. My simplification stems from the fact that when n is odd, b^{n} must be equivalent to b (mod f). As k*b^{n} == 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^{2} == f1 (mod f). So x and y are the values of z < f for which z^{2} == f1 (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 fx = y) (fx)^{2}x^{2} = f^{2}2fx+x^{2}x^{2} = f^{2}2fx, which is divisble by f. Therefore y^{2} (mod f) = x^{2} (mod f) This shows that x,y pairs where x+y = f have the same value mod f, so this applies for the value f1 (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^{2} == f1 (mod f), and if f == 3 (mod f), then m^{2} == 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^{2} and d^{2} both == f1 (mod f). Therefore d^{2}c^{2} = ef, where e is any whole number (not 2.718...). Factorizing: (d+c)(dc) = ef f is prime, so either d+c or dc must equal f. If dc 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 20100402 at 12:07 
20100402, 18:25  #15 
Nov 2008
4422_{8} Posts 
Well, noone has pointed out a flaw after 7 hours, but then again, noone has said that my proof is sound either...

20100402, 19:05  #16 
Aug 2006
5863_{10} Posts 
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 20100402 at 19:05 
20100403, 07:50  #17 
Nov 2008
100100010010_{2} 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 20100406 at 00:24 Reason: correct b+1=314, 318 to 312, 316 
20100403, 09:07  #18  
Dec 2008
179 Posts 
Quote:
Code:
for(m=63,250,p=4*m+1;if(isprime(p),x=lift(sqrt(Mod(1,p)));print(4*m" "x", "px))) 

20100403, 09:19  #19  
Dec 2008
179 Posts 
Quote:
There are efficient algorithms to take modular square roots; just use a program that implements one (see my other post). 

20100403, 10:42  #20  
Nov 2008
2·3^{3}·43 Posts 
Quote:


20100403, 21:48  #21 
Dec 2008
179 Posts 
Why? What gd_barnes asked proof for was essentially this: "Let f be the greatest common divisor of m^{2}+1 and b+1. If f is greater than 1, then m^{2}b^{n}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.

20100403, 23:36  #22 
Aug 2006
16E7_{16} Posts 
Thank you, Random Poster; I don't think I would have figured that out on my own!

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Algebraic factors in sieve files  pepi37  Conjectures 'R Us  95  20170704 13:37 
Riesel and Sierp numbers bases <= 1024  R. Gerbicz  Conjectures 'R Us  22  20091229 20:21 
Riesel/Sierp #'s for bases 3, 7, and 15  Siemelink  Conjectures 'R Us  105  20090904 06:40 
Algebraic factors  henryzz  ElevenSmooth  13  20071218 09:12 
Sierpinski/ Riesel bases 6 to 18  robert44444uk  Conjectures 'R Us  139  20071217 05:17 