mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Other Mathematical Topics

Reply
 
Thread Tools
Old 2019-02-18, 14:50   #1
dabler
 
dabler's Avatar
 
"David Barina"
Jul 2016
Brno

3×11 Posts
Default 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.
dabler is offline   Reply With Quote
Old 2019-02-18, 20:46   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

5·1,811 Posts
Default

YiFan's answer there is already good.

Quote:
Originally Posted by dabler View Post
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.
Batalov is offline   Reply With Quote
Old 2019-02-19, 13:40   #3
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2·23·71 Posts
Default

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...
Dr Sardonicus is offline   Reply With Quote
Old 2019-02-19, 17:13   #4
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

11100001102 Posts
Default

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.
danaj is offline   Reply With Quote
Old 2019-02-25, 10:13   #5
dabler
 
dabler's Avatar
 
"David Barina"
Jul 2016
Brno

3×11 Posts
Default 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.
dabler is offline   Reply With Quote
Old 2019-02-25, 14:09   #6
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2·23·71 Posts
Default

Quote:
Originally Posted by dabler View Post
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
Dr Sardonicus is offline   Reply With Quote
Old 2019-02-25, 18:00   #7
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

5×1,811 Posts
Question

Quote:
Originally Posted by dabler View Post
@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...

... is that what your alternative definition helpfully suggests?
Batalov is offline   Reply With Quote
Old 2019-02-25, 18:32   #8
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

16E616 Posts
Default

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).
CRGreathouse is offline   Reply With Quote
Old 2019-02-26, 01:05   #9
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2·23·71 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
Dr Sardonicus is offline   Reply With Quote
Old 2019-02-27, 17:20   #10
dabler
 
dabler's Avatar
 
"David Barina"
Jul 2016
Brno

3×11 Posts
Default 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.
dabler is offline   Reply With Quote
Old 2019-02-27, 18:31   #11
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

10000011100112 Posts
Default

No, not even that. By your logic, what determines that 11 is prime? 2^11-1 is not prime, yet 11 is prime.
VBCurtis is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
How to add relations from alternate sources during nfs() EdH YAFU 5 2013-04-23 15:55
Alternate means of primality testing Dougy Math 24 2009-10-08 19:40
Mersenne Numbers: Definition R.D. Silverman Math 47 2009-09-24 05:23
any alternate places to download... ixfd64 Lounge 8 2009-07-09 02:09
Suggestion: Alternate exponent distribution 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.