|
Prime conjecture
Let m be a positive odd integer.
If 2[SUP]m[/SUP] = 2 (mod. m(m-1)) then m is a prime. True or False? This is true for m = 3, 7, 19, 43, 127, 163, 379, 487, 883, 1459, 2647, 3079, 3943, 5419, 9199, 11827, 14407, 16759, 18523, 24967, 26407, 37339, 39367. These are all primes and there are no other values lessthan 40 003. Is it possible to prove the conjecture? |
I have no idea if it is provable or not, but there are only two more solutions below 10^9:
42463, 71443 |
[QUOTE=Stan;311835]Let m be a positive odd integer.
If 2m = 2 (mod. m(m-1)) then m is a [B][COLOR=#ff0000]prime[/COLOR][/B]. True or False? This is true for m = 3, 7, 19, 43, 127, 163, 379, 487, 883, 1459, 2647, 3079, 3943, 5419, 9199, 11827, 14407, 16759, 18523, 24967, 26407, 37339, 39367. These are all primes and there are no other values lessthan 40 003. Is it possible to prove the [B][COLOR=#ff0000]conjecture[/COLOR][/B]?[/QUOTE] for these value of m these become: 6 = 2 mod (9-3=6) which is false 14 = 2 mod (49-7=42) which is false 38 = 2 mod (361-19=342) which is false the main problem is that m(m-1) = m^2-m which is larger than 2m once m>3 so all m>3 fail this test. or at least that's my interpretation of it. I looked up your phrasing and found it on mathhelpforum.com and apparently it's 2^m not 2m as it reads here. |
[QUOTE=retina;311838]I have no idea if it is provable or not, but there are only two more solutions below 10^9:
42463, 71443[/QUOTE]:redface: Scratch that. My minion's little task turns out to be in error. There are indeed a lot more solutions for that up to 10^9. Here are the first few (all prime): 42463, 71443, 77659, 95923, 99079, 113779, 117307, 143263, 174763, 175447, 184843, 265483, 304039, 308827, 318403, 351919, 370387, 388963, 524287, 543607, 554527, 581743, 585847, 674083, 688087, 698923, ... |
[QUOTE=retina;311842]:redface: Scratch that. My minion's little task turns out to be in error.
There are indeed a lot more solutions for that up to 10^9. Here are the first few (all prime): 42463, 71443, 77659, 95923, 99079, 113779, 117307, 143263, 174763, 175447, 184843, 265483, 304039, 308827, 318403, 351919, 370387, 388963, 524287, 543607, 554527, 581743, 585847, 674083, 688087, 698923, ...[/QUOTE] They posted again in homework help it looks like. |
Prime conjecture
[QUOTE=Stan;311835]Let m be a positive odd integer.
If 2[SUP]m[/SUP] = 2 (mod. m(m-1)) then m is a [B][COLOR=#ff0000]prime[/COLOR][/B]. True or False? This is true for m = 3, 7, 19, 43, 127, 163, 379, 487, 883, 1459, 2647, 3079, 3943, 5419, 9199, 11827, 14407, 16759, 18523, 24967, 26407, 37339, 39367. These are all primes and there are no other values lessthan 40 003. Is it possible to prove the [B][COLOR=#ff0000]conjecture[/COLOR][/B]?[/QUOTE] I hope the above is now correct. |
nevermind, was not correct.
|
Mersenne prime sequence
If it is possible to prove the following conjecture then I can prove the existance of an infinite sequence of Mersenne primes and I can represent them as an algebraic expression. However, they are not representable as numbers.
Let m be a positive odd integer. If 2[SUP]m[/SUP] = 2 (mod. m(m-1)) then m is a [B][COLOR=#ff0000]prime[/COLOR][/B]. True or False? This is true for m = 3, 7, 19, 43, 127, 163, 379, 487, 883, 1459, 2647, 3079, 3943, 5419, 9199, 11827, 14407, 16759, 18523, 24967, 26407, 37339, 39367, and these are all prime. I can find no composite integers for which the statement holds. Is it possible to prove the [B][COLOR=#ff0000]conjecture[/COLOR][/B]? |
[QUOTE=ATH;311848]nevermind, was not correct.[/QUOTE]
see also: [url]http://mersenneforum.org/showthread.php?p=311833[/url] [url]http://mersenneforum.org/showthread.php?p=311851[/url] and probably more. oh yeah I forgot I originally found it correctly on: [URL="http://mathhelpforum.com/number-theory/203024-prime-conjecture.html"]http://mathhelpforum.com/number-theory/203024-prime-conjecture.html[/URL] |
[QUOTE=Stan;311851]If it is possible to prove the following conjecture then I can prove the existance of an infinite sequence of Mersenne primes and I can represent them as an algebraic expression. However, they are not representable as numbers.
Let m be a positive odd integer. If 2[SUP]m[/SUP] = 2 (mod. m(m-1)) then m is a [B][COLOR=#ff0000]prime[/COLOR][/B]. True or False? This is true for m = 3, 7, 19, 43, 127, 163, 379, 487, 883, 1459, 2647, 3079, 3943, 5419, 9199, 11827, 14407, 16759, 18523, 24967, 26407, 37339, 39367, and these are all prime. I can find no composite integers for which the statement holds. Is it possible to prove the [B][COLOR=#ff0000]conjecture[/COLOR][/B]?[/QUOTE] well reformatting gets to: M[SUB]m[/SUB] = 1 mod (m(m-1)) we know: M[SUB]m[/SUB] = 1 mod m, if m is prime so M[SUB]m[/SUB] would need the correct residue mod (m-1) for this to work. |
Dude, did you really need to start 3 separate threads on this? I merged all of 'em here.
|
So it seems to be two tests rolled into one: one 2-PRP and the other a quazi-PRP (2[SUP]m[/SUP]-2==0 (MOD m-1)). To pass the second test, the number cannot be divisble by 2 or 3, but quite a few composites pass. Now, need to find a intersection of 2-pseudopromes with the second test.....
|
[QUOTE=Batalov;311883]So it seems to be two tests rolled into one: one 2-PRP and the other a quazi-PRP (2[SUP]m[/SUP]-2==0 (MOD m-1)). To pass the second test, the number cannot be divisble by 2 or 3, but quite a few composites pass. Now, need to find a intersection of 2-pseudopromes with the second test.....[/QUOTE]
what I was going on is on is if x mod y=z and x mod a=z x mod ay=z so one we thing we know is for prime m, (2^m-1) mod m = 1 but the 1 mod (m-1) is the hard part, because M[SUB]m[/SUB] mod (m-1) will not always be 1 even if m is prime. my reasoning could be a heuristic at best I think. |
553 cases up to 5*10[sup]9[/sup], all prime.
[CODE]3 7 19 43 127 163 379 487 883 1459 2647 3079 3943 5419 9199 11827 14407 16759 18523 24967 26407 37339 39367 42463 71443 77659 95923 99079 113779 117307 143263 174763 175447 184843 265483 304039 308827 318403 351919 370387 388963 524287 543607 554527 581743 585847 674083 688087 698923 796447 821143 863299 1352107 1500283 1663579 1738423 1825867 1829563 2128267 3099727 3504439 3511999 3559627 3949723 4037923 5181103 5215267 5235679 5451643 5477599 6049639 6381667 7003963 7261003 7948207 8338303 8821387 9216019 9299179 9464743 10678879 10828063 11010007 11152303 11238739 11604223 12198859 12216583 12781063 13546279 13691287 14255587 15328783 15574843 16178023 16263367 16346107 16420447 16942339 17007103 17360407 19448983 19456039 20059327 20730979 21016423 21170647 23309047 23375059 24504607 24627079 25790563 25863463 26170747 26464159 27076519 27219403 28210267 29587699 29822479 29884303 30001267 30353443 30954799 31374379 31505923 32880223 33218803 35309107 36506863 38420803 39177559 40417219 41073859 42347467 42384547 42633379 42929083 43121863 43349419 44671663 48534067 48790099 49138867 49261339 51021307 52603363 54296299 55637443 55734967 56177227 56852839 57513727 58346947 59138983 60440059 61749703 63089083 63178543 63400807 65349019 65820439 66727963 72227863 76700527 77708647 80648947 82944163 84039607 84612403 85392007 86093443 86714839 92956627 94306843 94436119 96109903 99284347 99580447 99789103 103691503 104437999 109211887 115838479 126904807 127359919 135661303 137959039 140812183 141363307 144082639 144837883 147083203 166912327 173605699 173630647 180066079 190008019 190339759 199752967 210375523 211274407 216683587 222012379 227389303 230308723 230760307 232771159 233125939 234198343 242121643 243886483 248832487 252118819 253873999 254389087 256326607 257588647 258280327 264241027 266986399 267130459 268435459 268958719 272434807 273180979 280847323 282920527 283362787 287517007 295921999 296565067 298433647 301397923 303445927 305853787 311074507 314416243 323134939 327071683 328561759 343194139 343453447 344829367 345787219 350273323 355789099 379319599 384096007 390144763 393665203 420828703 421700707 427282939 434513647 436042279 441145279 441249607 443352043 453047743 479548987 489489967 490876219 491405779 497756827 504453799 514453843 515152387 523265023 535723147 536903683 541064959 543132703 555747319 558332839 562166263 568273483 588277243 592383943 592415587 597498679 599258899 602224603 606322963 608696047 616562983 621341659 627539767 627570343 632714167 634471219 637422283 641171539 643804687 650050759 687685699 693336043 701257663 702595027 710792839 731065987 731305387 753233419 761677183 763167259 768304027 769127563 780403303 790080607 792691327 792723079 799113463 804072739 818429347 823638943 843446899 844955119 846233083 852994927 860073187 877073023 885968443 890175259 914857147 918684343 933223519 939941983 942614983 943248727 953345863 954375283 999463879 1009422163 1029804679 1031629663 1033367707 1037073619 1040211559 1046723203 1061506783 1080203923 1091264887 1093705579 1104670603 1115255503 1123640659 1125342079 1136963467 1148361103 1152288019 1168386283 1177058863 1185892219 1193265739 1200392299 1222954363 1225697887 1230322087 1255147867 1258794919 1258810687 1260462547 1261278379 1269241219 1287986023 1296743743 1305198007 1317332647 1326749383 1333750699 1360020943 1366979167 1394163583 1396819999 1403743447 1404169579 1406616247 1423563499 1425849643 1435739299 1466000047 1472700223 1487318659 1504844083 1541069503 1544777407 1545457159 1548791119 1554086647 1573652683 1601630659 1618470883 1624805407 1630068787 1631881567 1636267879 1658516623 1677210319 1678111723 1699881247 1725420439 1738793323 1790767819 1803318679 1806673807 1818968887 1848710467 1865614507 1868904787 1881173323 1893692683 1895992939 1931414059 1952089147 1970138539 2038728007 2059349419 2067259699 2075498479 2077075603 2084971267 2091189367 2091909727 2094940423 2103772987 2112971239 2140976503 2144504503 2175205159 2191912003 2194978339 2199012463 2208438919 2229169279 2231061967 2270797579 2279118547 2280587779 2307382687 2310672799 2348390563 2365685407 2389936039 2402358967 2402877583 2415919123 2430487459 2442354139 2470916827 2494627687 2536357699 2541324619 2547534403 2549775187 2554735303 2560246543 2621221723 2657455939 2670226399 2678545423 2690722963 2704532167 2711118439 2726234659 2788704199 2795184127 2799052579 2800915363 2801693287 2816279119 2818736299 2819825947 2863125847 2869302367 2897139799 2918039419 3015382483 3047453767 3052295947 3088747243 3103616899 3124912447 3160216459 3202842763 3214342279 3253594087 3259112599 3259246663 3269670139 3321648163 3325775923 3357003259 3360948067 3370017043 3413876383 3416771863 3432700783 3445083307 3533072383 3576243799 3593032507 3602177083 3613845943 3618404623 3620180467 3671856259 3710372023 3724555339 3757637647 3765443599 3775383487 3777023359 3792352579 3799374499 3817958383 3915594019 3918154843 3920301883 3931259347 3969801739 4082339143 4117273903 4121077087 4189124143 4190287627 4192754563 4194812287 4215744307 4218235183 4218578659 4250765947 4265260903 4299319963 4315936759 4320036883 4395421423 4441298527 4451932423 4506632803 4600515043 4605999679 4621035259 4634822683 4677743683 4678535107 4775021443 4790257543 4794087187 4845966427 4869584623 4874416219 4908225043 4942554247[/CODE] |
[QUOTE=science_man_88;311857]well reformatting gets to:
M[SUB]m[/SUB] = 1 mod (m(m-1)) we know: M[SUB]m[/SUB] = 1 mod m, if m is prime so M[SUB]m[/SUB] would need the correct residue mod (m-1) for this to work.[/QUOTE] I can prove the correct residue for particular values of m, should the conjecture be provable. |
[QUOTE=Stan;311897]I can prove the correct residue for particular values of m, should the conjecture be provable.[/QUOTE]
the residue not already listed must be 1 for your conjecture to work at last check. |
[QUOTE=science_man_88;311898]the residue not already listed must be 1 for your conjecture to work at last check.[/QUOTE]
just realized that doesn't matter except to tell which m it will find not what type. because M[SUB]m[/SUB] mod m =1 is needed for the formula and that only happens if m is prime it proves m is prime. Now what's the proof of the infinitude of the Mersenne primes ? |
A comparison with the Wieferich primes might be fruitful.
|
This conjecture is false, and a counterexample can be "analytically" computed. You have not so much chance to find a counterexample by trials.
[CODE] (16:37:10) gp > Mod(2,(2^43-1)*(2^43-2))^(2^43-1) %3 = Mod(2, 77371252455309878902128642) (16:37:16) gp > Mod(2,(2^163-1)*(2^163-2))^(2^163-1) %4 = Mod(2, 136703170298938245273281389194851335334573089430790701237314721230585174013975804408997831182909442) (16:37:26) gp >[/CODE]None of those are primes, and the same for all the numbers in ATH's list which are not exponents of a mersenne prime. Edit: a nice puzzle should be to find the smallest counterexample (i.e. below 2^43-1). |
[QUOTE=LaurV;311946]
Edit: a nice puzzle should be to find the smallest counterexample (i.e. below 2^43-1).[/QUOTE] With some GPU assist, this should be very doable [Actually, it is doable even w/o GPU, but...]. Perhaps rogue can adopt his wwww code to search for them. EDIT:- We can just start with the list of base 2 psuedoprimes (as mentioned by SB), duh! EDIT: [URL="http://www.cecm.sfu.ca/Pseudoprimes/"]This[/URL] list should be sufficient |
You didn't have to check for 2-PRP (obvious for 2^n-1), just for the condition #2:
Mod(2,2^43-2)^(2^43-1)==2 %9 = 1 See post #12. |
Yes, sure. And I could use 1<<43-1 :razz: (which is faster, but may confuse the OP).
I just wanted to show it clear why is so. Of course I considered the fact that for every prime p, we have Mp is a 2-SPRP. This is how I constructed the counterexample, observing that if p is (using your terminology) quasi-prime, then 2^p-1 is also quasi prime. That is why for all primes p in ATH's list, then 2^p-1 will also be in ATH's list. But except p=3, 7, 127, few others, all remaining have Mp composite, but Mp is 2-SPRP and 2-quasiPrime. So here we are. I did not "check" for it, I just typed it. :razz: as I said, it is "analytically" constructed. |
The answer is 91625794219
|
:max:I've spent too much time trying to find a Carmichael number with this property. Didn't find one.
Then, the b-list for A001567 turned out to be enough. (too easy!) Now, tried axn's Galway list. (took some time to fetch!) ==> Just this value and 2^43-1. |
[QUOTE=Batalov;311954]91625794219[/QUOTE]
:tu: :tu: (I was thinking about fetching that list when I get home after work, but I just arrived and sat down and saw your result. Well done! Respect!) |
[QUOTE=Batalov;311954]Now, tried axn's Galway list. (took some time to fetch!)
==> Just this value and 2^43-1.[/QUOTE] Tested this list of 31,894,014 SPRP base2 < 2[sup]64[/sup]: [URL="http://www.cecm.sfu.ca/Pseudoprimes/index-2-to-64.html"]http://www.cecm.sfu.ca/Pseudoprimes/index-2-to-64.html[/URL] and found two more composite example: 1557609722332488343 18216643597893471403 So 4 total < 2[sup]64[/sup]. |
I realized I had to test all 118,968,378 base 2 prps below 2[sup]64[/sup] not "just" the strong prps, but this gave no other solutions.
|
[QUOTE=LaurV;311946]This conjecture is false, and a counterexample can be "analytically" computed. You have not so much chance to find a counterexample by trials.
[CODE] (16:37:10) gp > Mod(2,(2^43-1)*(2^43-2))^(2^43-1) %3 = Mod(2, 77371252455309878902128642) (16:37:16) gp > Mod(2,(2^163-1)*(2^163-2))^(2^163-1) %4 = Mod(2, 136703170298938245273281389194851335334573089430790701237314721230585174013975804408997831182909442) (16:37:26) gp >[/CODE]None of those are primes, and the same for all the numbers in ATH's list which are not exponents of a mersenne prime. Edit: a nice puzzle should be to find the smallest counterexample (i.e. below 2^43-1).[/QUOTE] Trying gp>Mod(2,(2^127-1)*(2^127-2))^(127-1) produced a similar result. E.g. %1 = Mod(2, a very long even number) Does this mean 2[SUP]127[/SUP]-1 is not prime, or am I being silly? What does Mod(2, 77371252455309878902128642) imply? |
@Batalov: see? what did I tell you? :razz:
@Stan: The "even" number you see is the product of m and m-1, where m=2^43-1. The small program proves that [COLOR=Red][B]2^m is equal to 2[/B][/COLOR] (mod m(m-1)) for this particular m, which is composite, therefore your conjecture is false, because I found a composite m for which 2^m=2 (mod m(m-1)). Read the small gp example as: [tex]2^{2^{43}-1}=2[/tex] when you interpret it (mod [tex](2^{43}-1)\cdot(2^{43}-1-1)[/tex]). The expression "a^b (mod c)" is written in pari/gp as "Mod(a,c)^b". edit: Regardless of the fact that your expression is wrong, as you only raise the number at 127-1, and not at 2^127-1, in your example m=2^127-1 which is prime, but in mine, 2^43-1 is NOT, and still verifies your conjecture. |
[QUOTE=Stan;312079]Does this mean 2[SUP]127[/SUP]-1 is not prime, or am I being silly?
What does Mod(2, 77371252455309878902128642) imply?[/QUOTE] It implies nothing, because you haven't proven any properties of your "test". Furthermore, the contributors to this thread proved the opposite of what you sought: as demonstrated above, both prime and composite numbers can pass the test. Therefore: passing the test implies nothing about the character of the input number. |
[QUOTE=LaurV;312083]@Batalov: see? what did I tell you? :razz:
[/QUOTE] I know. I think I gathered that you suggested to speak slowly... and verbously. Ok, this can be done. Let's do this: [CODE]Suppose 2^m = 2 (MOD m(m-1)) This means: 2^m - 2 = k m(m-1), with some k This in turn means 1) 2^m - 2 = 0 (MOD m) AND 2) 2^m - 2 = 0 (MOD m-1) Now, condition 1) is the 2-PRP test. All primes and composite numbers in sequence [URL="https://oeis.org/A001567"]A001567[/URL] pass it. Condition 2) is just some conguence - many prime and composite numbers pass it. Counterexamples 91625794219, 2^43-1 and others demonstrate that there exist composites that pass both tests (or equivalently, the original proposed test). Also, many primes do not pass the OP test. Therefore, the OP test does not improve on the 2-PRP test and if anything, only make the 2-PRP test worse. P.S. Of course, in the context of Mersenne numbers alone, 2-PRP test is moot: all of them pass it. [/CODE] |
:tu: Much better than I could say it!
|
It is interesting to notice that 91625794219 = (2[SUP]38[/SUP] - 2[SUP]19[/SUP] + 1)/3
|
Based on the previous post: let n = (2[SUP]2p[/SUP] -2[SUP]p[/SUP]+1)/3 where p is a prime number, is it true that 2[SUP]n-1[/SUP] = 1 (mod n) ?
|
[QUOTE=alpertron;312175]Based on the previous post: let n = (2[SUP]2p[/SUP] -2[SUP]p[/SUP]+1)/3 where p is a prime number, is it true that 2[SUP]n-1[/SUP] = 1 (mod n) ?[/QUOTE]
Nice problem. Proof: let p>2 prime number Observe that: (2^(2*p)-2^p+1)/3 | 2^(6*p)-1 so it is enough to prove that for p>2: 2^(n-1)==1 mod 2^(6*p)-1 it is equivalent to n-1==0 mod (6*p) so (2^(2*p)-2^p-2)/3==0 mod (6*p) (18*p)|2^p*(2^p-1)-2 Let p>3 then it is true mod p (use Fermat's little theorem), 2 also divides, this is trivial since 2^p is even. For 9 use: p=6k+-1 then 2^p=={2,5} mod 9, for the two cases: 2^p*(2^p-1)-2=={0,18}==0 mod 9. Since 2,9,p are relative prime numbers for p>3 it means that the divisibility is also true for 2*9*p=18*p. For p=3: 2^(n-1)==1 mod n is also true. |
Thanks.
|
Hi everyone
I know I am a bit late.... BUT I have the answer to your problem: take N = 2^524287 - 1. Notice that 524287 = 2^19 - 1, this is a clue for the proof ;) Indeed, you just need to consider the sequence X(n+1) = 2^X(n) - 1 with X(0) = 19 and proove that all terms of the sequence verify X(n)*X(n+1) divide 2^X(n) - 2. Have a nice day! |
Hi
I would like to know if a^(2^n) mod (2^n-1) = a² when a is between 0 and sqrt(2^n-1) and a is an integer when 2^n-1 is prime and only if it's prime ? I tried this with some Mersenne exposant and it apparently works. It can't be used to eliminate non-Mersenne exponant quickly ? Thanks :D |
In My Humble Opinion (IMHO) the even numbers are easier to keep track of
|
[QUOTE=kijinSeija;574293]Hi
I would like to know if a^(2^n) mod (2^n-1) = a² when a is between 0 and sqrt(2^n-1) and a is an integer when 2^n-1 is prime and only if it's prime ? I tried this with some Mersenne exposant and it apparently works. It can't be used to eliminate non-Mersenne exponant quickly ? Thanks :D[/QUOTE] That is a PRP test in disguise. From Fermat theorem, a^p=a (mod p) if p is prime. Amplify with a, you get a^(p+1)=a^2 (mod p). Replace p with Mp and you have your test. Replace a with 3 and that's what P95 and gpuOwl are doing. Yes, it can be used to eliminate composite Mp's, but not "fast". Well, not faster than we are doing already. |
[QUOTE=LaurV;574334]That is a PRP test in disguise. From Fermat theorem, a^p=a (mod p) if p is prime. Amplify with a, you get a^(p+1)=a^2 (mod p). Replace p with Mp and you have your test. Replace a with 3 and that's what P95 and gpuOwl are doing.
Yes, it can be used to eliminate composite Mp's, but not "fast". Well, not faster than we are doing already.[/QUOTE] Hi and thanks for your reply. And by the way I noticed something interesting : if a+b+c = 2^n-1 you can found number with a²+b²+c² = (4^n-1)/3 and it seems it works with Mersenne number (it seems it doesn't work with composite Mersenne number like 2^11-1 or 2^23-1) For example 4+2+1 = 7 (2^3-1) and 4²+2²+1² = 21 (4^3-1)/3 another example : 14+9+8 = 31 (2^5-1) and 14²+9²+8² = 341 (4^5-1)/3 There is a way to explain this ? Thanks :) |
I'm not sure what you are trying to say here...
4+3+0 = 7 (2^3-1), but 4^2 + 3^2 + 0^2 = 25 which is not (4^3-1)/3 13 + 10 + 8 = 31 (2^5-1) but 13^2 + 10^2 + 8^2 = 333 which is not (4^5-1)/3 So clearly there's something I'm missing. |
[QUOTE=slandrum;578931]I'm not sure what you are trying to say here...
4+3+0 = 7 (2^3-1), but 4^2 + 3^2 + 0^2 = 25 which is not (4^3-1)/3 13 + 10 + 8 = 31 (2^5-1) but 13^2 + 10^2 + 8^2 = 333 which is not (4^5-1)/3 So clearly there's something I'm missing.[/QUOTE] I mean you can find three random numbers (a, b, c) that respect that : a+b+c = 2^n-1 and a²+b²+c²=(4^n-1)/3 If a+b+c is a prime Mersenne number. you can't find any numbers for example for a+b+c = 2^11-1 and a²+b²+c² for (4^11-1)/3 it seems it doesn't exist. |
| All times are UTC. The time now is 17:36. |
Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.