Find Mersenne Primes twice as fast?

[CRGreathouse]

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.

[Nick]

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\).

[a1call]

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:

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.

[CRGreathouse]

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.

[a1call]

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?

[science_man_88]

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}

[a1call]

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.

[CRGreathouse]

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).

[science_man_88]

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.

[a1call]

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.

[CRGreathouse]

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.