 mersenneforum.org > Math Prime conjecture
 Register FAQ Search Today's Posts Mark Forums Read  2012-09-19, 16:06 #34 alpertron   Aug 2002 Buenos Aires, Argentina 72×29 Posts Based on the previous post: let n = (22p -2p+1)/3 where p is a prime number, is it true that 2n-1 = 1 (mod n) ?   2012-09-19, 16:55   #35
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

2·32·5·17 Posts Quote:
 Originally Posted by alpertron Based on the previous post: let n = (22p -2p+1)/3 where p is a prime number, is it true that 2n-1 = 1 (mod n) ?
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.   2012-09-19, 17:18 #36 alpertron   Aug 2002 Buenos Aires, Argentina 142110 Posts Thanks.   2021-03-20, 08:03 #37 Mounir   Mar 2021 110 Posts 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!   2021-03-21, 16:14 #38 kijinSeija   Mar 2021 France 1216 Posts 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   2021-03-21, 22:43 #39 MattcAnderson   "Matthew Anderson" Dec 2010 Oregon, USA 17608 Posts In My Humble Opinion (IMHO) the even numbers are easier to keep track of   2021-03-22, 03:03   #40
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

100110100001002 Posts Quote:
 Originally Posted by kijinSeija 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
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.   2021-05-23, 15:32   #41
kijinSeija

Mar 2021
France

2×32 Posts Quote:
 Originally Posted by LaurV 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.

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 :)   2021-05-23, 16:55 #42 slandrum   Jan 2021 California 3·101 Posts 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.   2021-05-23, 17:09   #43
kijinSeija

Mar 2021
France

1216 Posts Quote:
 Originally Posted by slandrum 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.
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.   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Steve One Miscellaneous Math 53 2019-03-18 00:34 Alberico Lepore Alberico Lepore 7 2018-02-16 08:27 Godzilla Miscellaneous Math 5 2016-05-16 12:44 miket Miscellaneous Math 6 2013-05-22 05:26 Templus Lounge 9 2006-03-14 16:30

All times are UTC. The time now is 14:40.

Wed Jan 19 14:40:43 UTC 2022 up 180 days, 9:09, 0 users, load averages: 1.98, 1.74, 1.67 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔