0
$\begingroup$

A Mersenne prime is a prime number that is one less than a power of two. Thus, it is a prime number of the form $M_n := 2^n−1$, where $n$ is a positive integer.

My question is: Are there any other integers greater than $2$ for which this property holds (e.g., $P=K^n−1$, for $K>2$)?

I tried a program on small prime numbers, but I discovered only Mersenne primes up to $2^{19}−1$.

$\endgroup$
3
  • 8
    $\begingroup$ For $K>2$ and $n>1$ we cannot have a prime since $K-1$ is a nontrivial factor.. The case $n=1$ is boring , since we just have $K-1$. what remains are the Mersenne primes. $\endgroup$
    – Peter
    Commented Jul 10 at 10:21
  • 3
    $\begingroup$ Try instead $(K^n-1)/(K-1)$, dividing out the invariant factor $K-1$. We call such numbers repunits base $K$, from their base-$K$ representations. $\endgroup$ Commented Jul 10 at 10:39
  • 1
    $\begingroup$ @OscarLanzi Or alternatively generalized Mersenne numbers. The other sort of numbers are $a^{2^n}+1$ , the generalized Fermat numbers , with the special case $a=2$ corresponding to the Fermat numbers. $\endgroup$
    – Peter
    Commented Jul 10 at 10:42

3 Answers 3

0
$\begingroup$

No, there are no other integers greater than $2$ that are guaranteed to be prime besides Mersenne primes. However, there are infinitely many prime numbers, and some of them will be greater than $2$ but not of the form $2^p - 1$ (where $p$ is prime). It's just that Mersenne primes have a specific form that makes them easier to test for primality.

May it helped you.

$\endgroup$
0
$\begingroup$

You have the factorization:

$$K^n-1=(K-1)(K^{n-1}+\ldots+K+1)$$ it is a product of two numbers, so in order for it to be prime we need $K-1=1$, that is $K=2$. This is necessary but not sufficient.

You also need $n$ to be prime, if not you will have $$K^{ab}-1=(K^a-1)(K^{a(b-1)}+K^{a(b-2)}+\ldots+K^b+1)$$

$\endgroup$
0
$\begingroup$

As suggested in the comments, you may want to consider the quotient

$Q=(K^n-1)/(K-1)$

instead, removing the factor $K-1$. This may be prime if $n$ is prime and some other pitfalls are avoided, including the following:

  • If $n$ divides $K-1$, then $Q$ will be divisible by $n$. This is evident from the "repunit" representation of $Q$ in base $K$. This representation passes the base-$K$ analogue of the "sum of digits" test for divisibility by $3$ or $9$ in base $10$.

  • If $n=4m+1$ and $K\equiv n\bmod 2n+1$ with both $n$ and $2n+1$ prime, then $Q$ will be divisible by $2n+1$. This comes about because $K\equiv n$ is a quadratic residue $\bmod(2n+1)$ under this condition, causing $K^n$ to become $\equiv 1\bmod 2n+1$. The smallest such case is $(5^5-1)/(5-1)$ being divisible by $11$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .