20190218, 14:50  #1 
"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.

20190218, 20:46  #2  
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3
5·1,811 Posts 
YiFan's answer there is already good.
Quote:
2^111 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. 

20190219, 17:13  #4 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
386_{16} 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. 
20190225, 10:13  #5 
"David Barina"
Jul 2016
Brno
3·11 Posts 
Re
@Batalov: Since 2047 is not prime, the does not imply the primality of its exponent. The must be a prime to prove the primality of p.
A few days ago I also found a slightly more general definition: Let be an integer. Then is a prime number if and only if there is some integer such that 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. 
20190225, 14:09  #6  
Feb 2017
Nowhere
3266_{10} Posts 
Quote:
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 20190225 at 14:19 Reason: gixnif topsy 

20190225, 18:00  #7 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3
5×1,811 Posts 
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 antireducing 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... ... is that what your alternative definition helpfully suggests? 
20190225, 18:32  #8 
Aug 2006
2×3×977 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 wellfounded under <. But they're not wellfounded 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).

20190226, 01:05  #9  
Feb 2017
Nowhere
2×23×71 Posts 
Quote:
Perhaps the method could be called reductio ad infinitum :D 

20190227, 17:20  #10 
"David Barina"
Jul 2016
Brno
21_{16} 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.

20190227, 18:31  #11 
"Curtis"
Feb 2005
Riverside, CA
1073_{16} Posts 
No, not even that. By your logic, what determines that 11 is prime? 2^111 is not prime, yet 11 is prime.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
How to add relations from alternate sources during nfs()  EdH  YAFU  5  20130423 15:55 
Alternate means of primality testing  Dougy  Math  24  20091008 19:40 
Mersenne Numbers: Definition  R.D. Silverman  Math  47  20090924 05:23 
any alternate places to download...  ixfd64  Lounge  8  20090709 02:09 
Suggestion: Alternate exponent distribution  Knappo  PrimeNet  10  20051026 17:52 