mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Conjectures 'R Us

Reply
 
Thread Tools
Old 2010-04-02, 03:11   #12
gd_barnes
 
gd_barnes's Avatar
 
May 2007
Kansas; USA

27BF16 Posts
Default

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
gd_barnes is offline   Reply With Quote
Old 2010-04-02, 03:55   #13
gd_barnes
 
gd_barnes's Avatar
 
May 2007
Kansas; USA

52·11·37 Posts
Default

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
gd_barnes is offline   Reply With Quote
Old 2010-04-02, 11:13   #14
10metreh
 
10metreh's Avatar
 
Nov 2008

2·33·43 Posts
Default

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
10metreh is offline   Reply With Quote
Old 2010-04-02, 18:25   #15
10metreh
 
10metreh's Avatar
 
Nov 2008

44228 Posts
Default

Well, no-one has pointed out a flaw after 7 hours, but then again, no-one has said that my proof is sound either...
10metreh is offline   Reply With Quote
Old 2010-04-02, 19:05   #16
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

586310 Posts
Default

Quote:
Originally Posted by 10metreh View Post
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
CRGreathouse is offline   Reply With Quote
Old 2010-04-03, 07:50   #17
10metreh
 
10metreh's Avatar
 
Nov 2008

1001000100102 Posts
Default

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
10metreh is offline   Reply With Quote
Old 2010-04-03, 09:07   #18
Random Poster
 
Random Poster's Avatar
 
Dec 2008

179 Posts
Default

Quote:
Originally Posted by 10metreh View Post
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.
Random Poster is offline   Reply With Quote
Old 2010-04-03, 09:19   #19
Random Poster
 
Random Poster's Avatar
 
Dec 2008

179 Posts
Default

Quote:
Originally Posted by 10metreh View Post
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 View Post
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).
Random Poster is offline   Reply With Quote
Old 2010-04-03, 10:42   #20
10metreh
 
10metreh's Avatar
 
Nov 2008

2·33·43 Posts
Default

Quote:
Originally Posted by Random Poster View Post
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.
10metreh is offline   Reply With Quote
Old 2010-04-03, 21:48   #21
Random Poster
 
Random Poster's Avatar
 
Dec 2008

179 Posts
Default

Quote:
Originally Posted by 10metreh View Post
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.
Random Poster is offline   Reply With Quote
Old 2010-04-03, 23:36   #22
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

16E716 Posts
Default

Thank you, Random Poster; I don't think I would have figured that out on my own!
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Algebraic factors in sieve files pepi37 Conjectures 'R Us 95 2017-07-04 13:37
Riesel and Sierp numbers bases <= 1024 R. Gerbicz Conjectures 'R Us 22 2009-12-29 20:21
Riesel/Sierp #'s for bases 3, 7, and 15 Siemelink Conjectures 'R Us 105 2009-09-04 06:40
Algebraic factors henryzz ElevenSmooth 13 2007-12-18 09:12
Sierpinski/ Riesel bases 6 to 18 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.