mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2016-09-07, 17:43   #12
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

598710 Posts
Default

Quote:
Originally Posted by a1call View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2016-09-07, 20:12   #13
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

23·32·52 Posts
Default

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\).
Nick is offline   Reply With Quote
Old 2016-09-07, 22:48   #14
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2,333 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
a1call is online now   Reply With Quote
Old 2016-09-08, 01:14   #15
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

5,987 Posts
Default

Quote:
Originally Posted by a1call View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2016-09-08, 01:30   #16
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2,333 Posts
Default

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
a1call is online now   Reply With Quote
Old 2016-09-08, 01:50   #17
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

20E216 Posts
Default

Quote:
Originally Posted by a1call View Post
* 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
science_man_88 is offline   Reply With Quote
Old 2016-09-08, 02:09   #18
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

91D16 Posts
Default

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
a1call is online now   Reply With Quote
Old 2016-09-08, 02:09   #19
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

5,987 Posts
Default

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).
CRGreathouse is offline   Reply With Quote
Old 2016-09-08, 02:23   #20
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts
Default

Quote:
Originally Posted by a1call View Post
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.
science_man_88 is offline   Reply With Quote
Old 2016-09-08, 02:35   #21
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

44358 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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.
a1call is online now   Reply With Quote
Old 2016-09-08, 03:33   #22
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

10111011000112 Posts
Default

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.
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
method to find primes (in a certain form) Alberico Lepore Alberico Lepore 10 2018-01-31 19:26
Fast modular reduction for primes < 512 bits? BenR Computer Science & Computational Number Theory 2 2016-03-27 00:37
Fast Mersenne Testing on the GPU using CUDA Andrew Thall GPU Computing 109 2014-07-28 22:14
DC chance to find Mersenne Prime houding PrimeNet 1 2014-02-24 20:25
Fast calculations modulo small mersenne primes like M61 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

Powered by vBulletin® Version 3.8.11
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.

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