mersenneforum.org Alternate definition of prime numbers
 Register FAQ Search Today's Posts Mark Forums Read

 2019-02-18, 14:50 #1 dabler     "David Barina" Jul 2016 Brno 3×11 Posts Alternate definition of prime numbers Would anyone know the answer to this question? I am particularly interested in the part "if 2^n−1 is prime then also the n must be a prime." You can leave a comment directly on MSE or here.
2019-02-18, 20:46   #2
Batalov

"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

5·1,811 Posts

Quote:
 Originally Posted by dabler I am particularly interested in the part "if 2^n−1 is prime then also the n must be a prime."
This will not serve as any substitute for a definition of primes, because it does not define all primes.
2^11-1 is not prime so using your proposed part "if 2^n−1 is prime then also the n must be a prime", what can you say about 11? And yet 11 is prime.

 2019-02-19, 13:40 #3 Dr Sardonicus     Feb 2017 Nowhere 2·23·71 Posts My post here contains a link to a paper about "very short primality proofs." Alas, there is in general no quick way to find such a short proof...
 2019-02-19, 17:13 #4 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 11100001102 Posts Dudley's paper "Formulas for Primes" (1983) contains some little formulas that produce either prices or an accurate prime count. There is the generalization of Fermat's little theorem to polynomials: given n > 1 and 'a' coprime to n, n is prime if and only if (x+a)^n = (x^n + a) mod n for 'a' coprime to n. That's nice and short, albeit not very practical to actually use as is.
 2019-02-25, 10:13 #5 dabler     "David Barina" Jul 2016 Brno 3×11 Posts Re @Batalov: Since 2047 is not prime, the $2^{11}-1$ does not imply the primality of its exponent. The $2^p - 1$ must be a prime to prove the primality of p. A few days ago I also found a slightly more general definition: Let $p$ be an integer. Then $p$ is a prime number if and only if there is some integer $b\neq1$ such that $\frac{b^p-1}{b-1}$ is also a prime number. See MSE question on this. @Dr Sardonicus and danaj: Thank you both for the references. Especially the Lucas theorem is a definition I was looking for.
2019-02-25, 14:09   #6
Dr Sardonicus

Feb 2017
Nowhere

2·23·71 Posts

Quote:
 Originally Posted by dabler A few days ago I also found a slightly more general definition: Let $p$ be an integer. Then $p$ is a prime number if and only if there is some integer $b\neq1$ such that $\frac{b^p-1}{b-1}$ is also a prime number. See MSE question on this.
Even assuming this to be true, it would seem to be even more computationally useless than Wilson's Theorem (which at least is known to be true, and theoretically useful).

I have no idea what an upper bound for the first such b might be; without such a bound, the criterion would be computationally absolutely useless.

I looked for the smallest base b for each prime p up to 500. There are primes p for which the smallest positive base b is significantly greater than p.

prime p = 37, smallest b = 61
prime p = 179, smallest b = 304
prime p = 229, smallest b = 606
prime p = 233, smallest b = 602
prime p = 277, smallest b = 338
prime p = 421, smallest b = 808
prime p = 443, smallest b = 793
prime p = 491, smallest b = 514

Checking "negative bases" (i.e. (b^p + 1)/(b+1) for p > 2 and b > 1) turned up the singularly stubborn case p = 233. The smallest base for which (b^233 + 1)/(b+1) is a (pseudo)prime, is b = 489.

Last fiddled with by Dr Sardonicus on 2019-02-25 at 14:19 Reason: gixnif topsy

2019-02-25, 18:00   #7
Batalov

"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

5×1,811 Posts

Quote:
 Originally Posted by dabler @Batalov: The $2^p - 1$ must be a prime to prove the primality of p.
That's marvelous.

So, let me wrap my head around this... In order to prove that a very small number is prime you must prove that a much larger number is prime. How do you, pray tell, prove that? By testing an even larger number, obviously? Unlike descent methods (solve a problem by splitting it into many small problems which can be split into problems smaller still) you propose to solve a small problem by anti-reducing it to a very large problem which in itself is not proven until you prove a gigantic problem ...which in itself is not proven until...

 2019-02-25, 18:32 #8 CRGreathouse     Aug 2006 16E616 Posts To expand on Batlov's incredulity, remember that induction is more than just the inductive step: it also includes the base case (or more generally, the base cases). When you're going down, you can be guaranteed to hit small enough numbers because the positive integers are well-founded under <. But they're not well-founded under >, because you can keep picking higher and higher numbers indefinitely, so it's hard to have a base case (and indeed, you do not).
2019-02-26, 01:05   #9
Dr Sardonicus

Feb 2017
Nowhere

2·23·71 Posts

Quote:
 Originally Posted by CRGreathouse When you're going down, you can be guaranteed to hit small enough numbers because the positive integers are well-founded under <. But they're not well-founded under >, because you can keep picking higher and higher numbers indefinitely, so it's hard to have a base case (and indeed, you do not).
Hmm. Sounds suspiciously like what used to be called "well-ordered."

Perhaps the method could be called reductio ad infinitum
:-D

 2019-02-27, 17:20 #10 dabler     "David Barina" Jul 2016 Brno 3×11 Posts Re: @Batalov Yes, now I see the definition is useless without some base case. There's only one interesting thing on that --- having all primes above a certain point as the base case, these primes determine all remaining primes below the point.
 2019-02-27, 18:31 #11 VBCurtis     "Curtis" Feb 2005 Riverside, CA 10000011100112 Posts No, not even that. By your logic, what determines that 11 is prime? 2^11-1 is not prime, yet 11 is prime.

 Similar Threads Thread Thread Starter Forum Replies Last Post EdH YAFU 5 2013-04-23 15:55 Dougy Math 24 2009-10-08 19:40 R.D. Silverman Math 47 2009-09-24 05:23 ixfd64 Lounge 8 2009-07-09 02:09 Knappo PrimeNet 10 2005-10-26 17:52

All times are UTC. The time now is 08:32.

Sun Jul 5 08:32:48 UTC 2020 up 102 days, 6:05, 1 user, load averages: 1.13, 1.17, 1.16