mersenneforum.org > Math Find Mersenne Primes twice as fast?
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2016-09-07, 17:43   #12
CRGreathouse

Aug 2006

598710 Posts

Quote:
 Originally Posted by a1call 2^n-1 does not generate all the of odd primes. It does not generate 3,5,11,13,...
Again, you misunderstand Devaraj. He's not claiming that 2^n - 1 = 5 for some integer n, but rather that 5 | (2^n - 1) for some integer n.

 2016-09-07, 20:12 #13 Nick     Dec 2012 The Netherlands 23·32·52 Posts We can do something similar with polynomials. Let p be a prime number, and take any non-zero polynomial f with coefficients from the integers modulo p. Then f has the form $f=a_0+a_1x+a_2x^2+a_3x^3+\ldots +a_mx^m$ where m can be chosen so that $$a_m\neq 0$$. We call m the degree of f. If the degree of f is 0 then we simply have $$f=a_0$$ and call f a constant polynomial. We call the non-zero constant polynomials units - they play the same role as 1 (and -1) in the integers because they divide everything. If $$a_m=1$$, we say the polynomial is monic. Any non-zero polynomial can be turned into a monic polynomial by dividing by a unit, so in practice we can work with monic polynomials (just as we usually prefer positive integers in Number Theory). We call f irreducible if it is not a unit and cannot be written as the product of two polynomials unless one of them is a unit. The monic irreducible polynomials here play the role of the prime numbers in Number Theory. Now let n be an integer with n≥1. If we multiply together all the monic irreducible polynomials whose degree divides n, it can be shown that we get the polynomial $$x^{p^n}-x$$. In particular, any monic irreducible polynomial with coefficients in the integers modulo p and whose degree divides n (except the polynomial x itself) is a factor of $$x^{p^n-1}-1$$.
2016-09-07, 22:48   #14
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

2,333 Posts

Quote:
 Originally Posted by CRGreathouse Again, you misunderstand Devaraj. He's not claiming that 2^n - 1 = 5 for some integer n, but rather that 5 | (2^n - 1) for some integer n.
I don't know how you could get that from:
Quote:
 the only exponential function that generates all the odd primes is 2^n-1.
And I don't know how that can even make any sense.
105 divides all the positive odd primes less than 8 and it is not of the form 2^n-1 but it is of the form/equal to 2^7-13.
I think perhaps you are the one who misunderstood him.

Last fiddled with by a1call on 2016-09-07 at 22:50

2016-09-08, 01:14   #15
CRGreathouse

Aug 2006

5,987 Posts

Quote:
 Originally Posted by a1call I don't know how you could get that from
I get it from the part just after that where he references a sequence in the OEIS. You probably would have figured it out too if you'd looked it up.

 2016-09-08, 01:30 #16 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 2,333 Posts May be I just don't have the gray matter to understand what is being said. I was out and about all day and posting via smart phone. Did not have a chance to look up the sequence: https://oeis.org/A123239 So is he saying that: * "Primes that do not divide 2^n-1 for any n" constitute the set of all odd prime numbers? That doesn't seem right. How about 23|2^11-1 to keep the exponent a prime for a better likelihood. * What is exactly different between 2^n-1 & 3^n-2 * There are primes that can divide 3^n-2 (5) and there are primes that can't (2). * There are primes that can divide 2^n-1 (23) and ..... * Are there no odd primes that do not divide 2^n-1 for at least one n? is that what being said here? Last fiddled with by a1call on 2016-09-08 at 01:39
2016-09-08, 01:50   #17
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

20E216 Posts

Quote:
 Originally Posted by a1call * What is exactly different between 2^n-1 & 3^n-2 * There are primes that can divide 3^n-2 (5) and there are primes that can't (2). * There are primes that can divide 2^n-1 (23) and ..... * Are there no odd primes that do not divide 2^n-1 for at least one n? is that what being said here?
one allows fermat's little theorem to be applied and the other doesn't would be my first guess ( if it wasn't obvious from the post I made above) as to my comment about polynomials you can use modular arithmetic and algebra to figure most of it out.edit: along with the pigeonhole principle. edit2: actually it's saying Primes that do not divide 2^n-1 for any n constitute the set {2}

Last fiddled with by science_man_88 on 2016-09-08 at 01:56

 2016-09-08, 02:09 #18 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 91D16 Posts I can see that 2^n-1 can be divisible by any odd prime number. What I have trouble figuring out is how 3^n-2 can not be divided by 3 for any integer n. Thinking out loud: 3^n-2=3m 3^n=3m+2 (that makes sense and would make sense for any non zero integer, indivisible by 3 instead of 2 such as 3^n-1) obviously 3^n-3k can and will always be divisible by 3 3^n-2=11m 3^n=11m+2 This is more difficult for me to see 11m+2 can certainly be divisible by 3. Why it can't be a power of 3, no clue. Last fiddled with by a1call on 2016-09-08 at 02:16
 2016-09-08, 02:09 #19 CRGreathouse     Aug 2006 5,987 Posts For every prime p > 2, there is some integer n such that p | (2^n - 1). But the same is not true for 3^n - 2: there are infinitely many primes p such that p does not divide 3^n - 2 for any integer n. devarajkandadai claimed that the first case was unique [among exponentials] and the second was generic, but that is not correct: there are others like, say, 4^n - 64 which should have the same property (here we can insist that n > 3 to avoid triviality).
2016-09-08, 02:23   #20
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts

Quote:
 Originally Posted by a1call 3^n=11m+2 This is more difficult for me to see 11m+2 can certainly be divisible by 3. Why it can't be a power of 3, no clue.
okay first things first the pigeonhole principle basically says that if you try to place more than n objects (numbers in this case) in n boxes ( congruences classes in this case) you can't have a scenario where only one object can be in all boxes (i.e at least two objects must share the same box).

based on this we can already conclude that if n>11 that at least one n<=11 shares a congruence class with it so we only need to check up to n=11. now let's check the first 11 n values mod 11:

3^1=3 mod 11
3^2=9 mod 11
3^3=5 mod 11
3^4=4 mod 11
3^5=1 mod 11
3^6=3 mod 11 <- looping value already we can stop ( due to a modular property).

there is no 2 mod 11 value in our loop therefore using the fact it will loop we can conclude that no n value produces 2 mod 11.

2016-09-08, 02:35   #21
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

44358 Posts

Quote:
 Originally Posted by science_man_88 okay first things first the pigeonhole principle basically says that if you try to place more than n objects (numbers in this case) in n boxes ( congruences classes in this case) you can't have a scenario where only one object can be in all boxes (i.e at least two objects must share the same box). based on this we can already conclude that if n>11 that at least one n<=11 shares a congruence class with it so we only need to check up to n=11. now let's check the first 11 n values mod 11: 3^1=3 mod 11 3^2=9 mod 11 3^3=5 mod 11 3^4=4 mod 11 3^5=1 mod 11 3^6=3 mod 11 <- looping value already we can stop ( due to a modular property). there is no 2 mod 11 value in our loop therefore using the fact it will loop we can conclude that no n value produces 2 mod 11.
yes observation of repeating sequence of reminders would eliminate the possibility.
Thank you, Science man.

 2016-09-08, 03:33 #22 CRGreathouse     Aug 2006 10111011000112 Posts Yes, well done sm88. My example of 4^n - 64 was constructed to take advantage of this property in a way that guarantees that I get the divisibility promised: since it's 0 at n = 3 , any prime not dividing 4 will loop back through that modular 0.

 Similar Threads Thread Thread Starter Forum Replies Last Post Alberico Lepore Alberico Lepore 10 2018-01-31 19:26 BenR Computer Science & Computational Number Theory 2 2016-03-27 00:37 Andrew Thall GPU Computing 109 2014-07-28 22:14 houding PrimeNet 1 2014-02-24 20:25 Dresdenboy Programming 10 2004-02-29 17:27

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

Fri Jan 27 18:40:22 UTC 2023 up 162 days, 16:08, 0 users, load averages: 1.44, 1.31, 1.28

Copyright ©2000 - 2023, 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.

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