Proth Primes: Coefficient & Exponent Relations

In summary, a Proth number is a number of the form k*2^n+1, where k is an odd positive integer and n is a positive integer such that 2^n>k. The presence of a prime Proth number can indicate certain relationships between the exponent n and coefficient k, such as n being congruent to 1 mod 2 and greater than 1 implying a GCD of (k-1,3)=1, and n being congruent to 0 mod 2 implying a GCD of (k+1,3)=1. This may also have connections to the sieve of eratosthenes and the distribution of twin primes. Further exploration into these relationships could potentially lead to a better understanding
  • #1
pedja
15
0
Definition: Proth number is a number of the form :

[itex]k\cdot 2^n+1[/itex]

where [itex]k[/itex] is an odd positive integer and [itex]n[/itex] is a positive integer such that : [itex]2^n>k[/itex]

My question : If Proth number is prime number are there some other known relations in addition to [itex]2^n>k[/itex] , between exponent [itex]n[/itex] and coefficient [itex]k[/itex] ?
 
Physics news on Phys.org
  • #2


[itex]( n \equiv 1 \pmod 2 \land n > 1) \Rightarrow \gcd(k-1,3)=1 [/itex]

[itex] n \equiv 0 \pmod 2 \Rightarrow \gcd(k+1,3)=1 [/itex]
 
  • #3


I would think it has something to do with the sieve of eratosthenes, where the twin primes revolve around multiples of 6. The formula would give the lesser value for the twin primes.

A few years ago, i decided to look into the riemann hypothesis. I noticed that using the sieve of eratosthenes, there is an obvious pattern for composite numbers. The pattern gets more complex after regions of primes squared. I started to develop a formula but it got more complex with each region, and didn't seam like a good basis for an equation, so I put it off.
 

What are Proth Primes?

Proth primes are a special type of prime number that follow the form of n = k * 2^m + 1, where n is a prime number, k is an odd number, and m is a positive integer.

What is the significance of Proth Primes?

Proth primes have significance in number theory and cryptography. They are used in the construction of pseudorandom number generators and in the RSA encryption algorithm.

How are Proth primes related to coefficients and exponents?

The coefficients and exponents in the Proth prime formula (n = k * 2^m + 1) play a crucial role in determining whether a number is a Proth prime. The coefficient k must be an odd number and the exponent m must be a positive integer for a number to be a Proth prime.

How are Proth primes tested for primality?

Proth primes can be tested for primality using the Proth's theorem, which states that if n = k * 2^m + 1 is a Proth prime, then for every a such that 1 < a < n-1, a^(n-1)/2 ≡ ±1 (mod n). This means that if the remainder of a^(n-1)/2 divided by n is not equal to ±1, then n is not a Proth prime.

Are there any known relationships between Proth primes and other types of primes?

There are some known relationships between Proth primes and other types of primes, such as Mersenne primes and Fermat primes. For example, every Mersenne prime is also a Proth prime, but not every Proth prime is a Mersenne prime.

Similar threads

  • Linear and Abstract Algebra
Replies
2
Views
852
  • Linear and Abstract Algebra
Replies
8
Views
959
  • Linear and Abstract Algebra
Replies
11
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
676
  • Calculus and Beyond Homework Help
Replies
3
Views
482
  • Linear and Abstract Algebra
Replies
3
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
888
  • Linear and Abstract Algebra
Replies
4
Views
1K
  • Precalculus Mathematics Homework Help
Replies
9
Views
1K
  • Linear and Abstract Algebra
Replies
9
Views
2K
Back
Top