Skip to main content

Questions tagged [mersenne-numbers]

For specific number theory question related to Mersenne numbers.

Filter by
Sorted by
Tagged with
-2 votes
0 answers
44 views

Proving that for every prime number $p$, the number $2^p - 1$ is either prime or divisible by a prime $q$ such that $q \equiv 3 \pmod{4}$. [duplicate]

Is it true for every prime number $p$, the number $2^p - 1$ is either prime or divisible by a prime $q$ such that $q \equiv 3 \pmod{4}$?
Anon's user avatar
  • 7
1 vote
0 answers
65 views

New Mersenne Primes Found -- Need help with Lucas-Lehmer Tests Please. [closed]

I wrote some Python3 code last night to work on this problem for fun and seemingly stumbled upon two new Mersenne Primes. I'm still learning so I don't quite understand how to format the Lucas-Lehmer ...
Jay's user avatar
  • 19
2 votes
0 answers
81 views

Let p and q be prime numbers with $p \equiv 3 \pmod 4$ and $q=2p+1$. Prove that $2^{p} - 1$ is prime only when $p=3$

Task: Let p and q be prime numbers with $p \equiv 3 \ \pmod 4$ and $q=2p+1$. Prove that $2^{p} - 1$ is prime only when $p=3$. This question has been asked on this forum for a long time, but I have ...
Little Mandelbrot's user avatar
-1 votes
1 answer
153 views

Can it be proven that the reduced digit sum of Mersenne primes, except 3 and 7, is always 1 or 4?

For the first 36 Mersenne numbers (M(n)) I have calculated M(n)(mod 9) and the reduced digit sum of M(n). For n > 0, I found repeating sequences of respectively 1,3,7,6,4,0 and 1,3,7,6,4,9. Also, I ...
Mark's user avatar
  • 21
1 vote
1 answer
99 views

About divisors of Mersenne numbers [closed]

1. Any Mersenne number $M_p,~p ≡ 3 \pmod 4$ where $p$ is a prime, can be represented as: $$(8px+2p+1)(8py+1) = M_p,~0 ≤ x ≤ \frac{M_p - 1 - 2p}{8p},~ 0 ≤ y ≤ \frac{\frac{M_p}{2p + 1} - 1}{8p}$$ 2. Any ...
Nikolay Gladkov's user avatar
1 vote
0 answers
138 views

$2^n + 3$ and $2^{n+1} + 3$ both prime?

It seems there are infinitely many primes of the form $2^n + 3$. It seems that the density is about the same density as primes below $n$ at least for small $n$. What surprised me is I found solutions ...
mick's user avatar
  • 16.1k
8 votes
3 answers
342 views

How many numbers in the interior of Pascal's triangle are Mersenne numbers?

Consider the interior of Pascal's triangle, i.e. the triangle without numbers of the form $\binom{n}{0},\binom{n}{1},\binom{n}{n-1},\binom{n}{n}$. How many numbers in the interior of Pascal's ...
Dan's user avatar
  • 23.9k
3 votes
1 answer
206 views

A question about prime factorization of composite Mersenne numbers and $(2^p-2)/(2 \cdot p)$

Mersenne numbers are numbers of the form $2^p-1$ where $p$ is a prime number. Some of them are prime for exemple $2^5-1$ or $2^7-1$ and some of them are composite like $2^{11}-1$ or $2^{23}-1$. I'm ...
Aurel-BG's user avatar
  • 131
0 votes
0 answers
58 views

Is there a positive integer $n$ such that every $n$-Mersenne prime generates a prime?

First, some definitions. A $1$-Mersenne prime is just a Mersenne prime. Now, let $n$ be a positive integer. If $p$ is an $n$-Mersenne prime, and $2^p - 1$ is itself a prime, then $2^p - 1$ is said to ...
user107952's user avatar
  • 20.9k
3 votes
0 answers
93 views

A Mersenne number is never a Carmichael number

I am tasked with proving that all Mersenne composites (that is, composite numbers of the form $2^n -1$) are either always Carmichael numbers or never are. Running some tests, I have found some ...
Rararat's user avatar
  • 345
1 vote
0 answers
218 views

An explanation of why the Lucas-Lehmer Primality Test works: is this OK?

I've always wondered why the Lucas-Lehmer Primality Test works. After studying it, I came up with an explanation. I hope you can help me confirm and complete it. A Mersenne prime is a number of the ...
CuriousAboutNumbers's user avatar
3 votes
1 answer
135 views

Decimation of Maximal-length sequence

Consider a Maximal-length sequence (hereby M-sequence) $S$ of minimal period $2^n-1$, as produced by an LFSR with a binary primitive polynomial. Note $s_0,s_1,\ldots$ the bits of $S$. For some integer ...
fgrieu's user avatar
  • 1,768
2 votes
0 answers
78 views

Mersenne number variant

It appears that all numbers of the form $(6^p-1)/5$ for prime $p$ are square free and are coprime to each other. Is this true? This seems like it might be related to Mersenne numbers, except with 6 ...
Brad's user avatar
  • 21
2 votes
0 answers
60 views

Generalization of Mersenne Primes

Besides Mersenne primes, are there any other known conditions for the natural numbers $n$ and $m$ under which the natural number ${n^m - n + 1}$ is "unusually likely" to be prime? By ...
MathNeophyte's user avatar
2 votes
0 answers
142 views

Squarefreeness Mersenne Numbers

In this page of Caldwell, after the proof of the link with Wieferich primes and pointing out that the two known ones can't be divisors of any Mersenne numbers, in the Comment he asserts «... so $M_q$ ...
Falcon's user avatar
  • 111
2 votes
0 answers
52 views

Numbers of divisors for a Mersenne number

Recently I encountered a problem: If n is a positive integer, then is the number of divisors of $2^n - 1$ less or greater than the number of divisors of n? I tried factoring and taking modulo n but ...
notabot's user avatar
  • 21
1 vote
1 answer
77 views

Use Mersenne numbers to prove that there are infinitely many prime numbers.

When reading the book Mersenne Numbers and Fermat Numbers, after proving that: for any positive integers m,n, it holds $\gcd(M_n,M_m)=1$ if and only if $\gcd(m,n)=1$, it says that this allows us to ...
Lumos's user avatar
  • 121
0 votes
0 answers
33 views

About repunit and Mersenne numbers

Let $r_n=11..11$ be the repunit of 1 repeated n times. In base 10, we have $r_n= (11..11)_{10}=\frac 19 (10^n-1)$ with a repetition of 1 n times. I would like to prove that if n is composite, then $...
Pascal's user avatar
  • 3,781
2 votes
0 answers
77 views

Finding prime numbers with mod function with respect to given odd number $'a'$ between $2^n$ and $2^{n+1}$

Here are few steps which made sense when analysing the prime numbers Step 1: For any odd number "$a \in Z^+ $" e.g. 17 Step 2 : $a$ is $2^{n} < a < 2^{n+1}$ Step 3: now get the list ...
Sivakumar Krishnamoorthi's user avatar
2 votes
1 answer
266 views

Lucas-Lehmer test for Mersenne and Wagstaff numbers?

Here is what I observed : Let $M_p = 2^p-1$ for Mersenne numbers and $W_p = (2^p+1)/3$ for Wagstaff numbers with $p$ a prime number > $2$ Let the sequence $S_i = 6 \cdot S_{i-1}^2 + 18 \cdot S_{i-1}...
kijinSeija's user avatar
5 votes
0 answers
169 views

Density of extended Mersenne numbers?

Consider the subset of odd positive integers defined and constructed as follows by these rules : A) $1$ is in the set. B) if $x$ is in the set , then $2x + 1$ is in the set. C) if $x$ and $y$ are in ...
mick's user avatar
  • 16.1k
0 votes
1 answer
99 views

Subarray Sum Equals K - If the same prefix sum is encountered why does it follow 1,3,7,15,31 pattern?

This is an interesting property I have noticed in the problem: Subarray Sum Equals K The basic algorithm is as follows: You start with calculating the prefix (running sum). You check if the ...
ng.newbie's user avatar
  • 1,025
0 votes
0 answers
78 views

Odd Composite Proof

When $n$ is an odd natural composite number, $\frac{2^n + 1}{3}$ is always composite. Prove this conjecture. I'm not 100% sure but I let $n$ = $2c+1$ = $ab$, where $c$ is a natural number including $0$...
user avatar
1 vote
0 answers
244 views

Remarks on Lucas–Lehmer test

I was looking for a way to derive the elements of the sequence in a different way in the Lucas–Lehmer test with $ \quad p \quad$an odd prime. we know that $ \quad s_0=4 \quad $ and $ \quad s_i=s_{i-1}^...
user140242's user avatar
2 votes
1 answer
122 views

Expected size of least prime factor of $(16^p-1)/15$

Let's define a function $g(x)$ as follows: $g(x)=-x+\displaystyle\sum_{\substack{3\le p\le x/2}\\{p \text{ prime}}}{\log_2 \left( \text{LeastPrimeFactor} \left( \frac{16^p-1}{15} \right) \right) }$ ...
Brett Berger's user avatar
1 vote
2 answers
207 views

Condition for $8p+1$ divides $2^p-1$?

Here is what I observed : Let $8p+1 = (2a-1)^2+64(2b-1)^2$ with $a$ and $b$ be a positive integers, $p$ and $8p+1$ both prime numbers. Then $8p+1$ divides $2^p-1$ only if you can write $8p+1$ as $(2a-...
kijinSeija's user avatar
2 votes
0 answers
175 views

A note on conjecture that all the Mersenne numbers are square-free

Today, I am posting an approach that seems too elementary to validate. The approach is developed by me while reading the 1967 work of L. Warren and H. Bray. In their article, "On the square-...
Aziz's user avatar
  • 191
1 vote
0 answers
80 views

A diophantine equation inspired in a conjecture due to Gica and Luca

In this post I consider the equation $$k\cdot x=y^2+z^2(x^2-2)-2\tag{1}$$ over odd integers $y\geq 1$ and $z\geq 1$, and over integers $k\geq 1$ and Mersenne exponents $x\geq 13$ such that $x^2-2$ is ...
user759001's user avatar
1 vote
1 answer
98 views

Assume that there are infinitely many Mersenne primes, prove there are infinitely many positive integers m and n such that $\phi(m)=\sigma(n)$.

Conjecture 3 of chapter 1 states that there are infinitely many Mersenne prime numbers. Mersenne prime numbers are integers that are in the form of $2^p-1$ where p is prime.The first 3 Mersenne prime ...
Jack Hilton-Jones's user avatar
1 vote
0 answers
101 views

Is this a valid proof concerning Mersenne Primes?

I am very new to proofs, and I learned that for $2^c-1=n$, if $c$ is composite, then $n$ is composite. I recently learned about proofs by contradiction, so here is my attempt at proving this ...
TreeGuy's user avatar
  • 186
0 votes
1 answer
73 views

$n$ is prime if $M_n\equiv 1\pmod{n}$

Let $M_n$ the $n$-th Mersenne number (A000225). I am trying to prove that if n is prime then $2^n-1=M_n\equiv 1\pmod{n}$. I'm sure it should be easy to get out of fermat's little theorem ($c^{n-1}\...
Luis Alexandher's user avatar
3 votes
0 answers
103 views

What can be said about the primality of Zsigmondy Numbers?

Let $\mathcal{Z}(n,a,b)=\frac{\Phi_n(a,b)}{\gcd (\Phi_n(a,b),n)}$ by the $n$-th Zsigmondy number to base $(a,b)$, where $\Phi_n(a,b)$ is the $n$-th homogeneous cyclotomic polynomial. Zsigmondy proved ...
Tejas Rao's user avatar
  • 1,940
-1 votes
2 answers
250 views

Is $3$ the only prime that is both a Mersenne prime and a Fermat prime?

A Mersenne prime is a prime of the form $2^n-1$. A Fermat prime is a prime of the form $2^n+1$. Despite the two being superficially very similar, it is conjectured that there are infinitely many ...
Jose Arnaldo Bebita Dris's user avatar
3 votes
0 answers
364 views

Show that if $n$ is a positive integer greater than $1$, then the Mersenne number $M_n$ cannot be the power of a positive integer.

Question Show that if $n$ is a positive integer greater than $1$, then the Mersenne number $M_n$ cannot be the power of a positive integer. My Progress As Image As Text Let $M_n = 2^n - 1$ be a ...
Kaustubh Limaye's user avatar
4 votes
1 answer
158 views

Why do Mersenne numbers work?

In Matt Parker's book: "Things to make and do in the fourth dimension", he says that mathematicians have long known that for $2^n - 1$, if $n$ is not prime then the number cannot be prime. I ...
Spammer's user avatar
  • 91
2 votes
1 answer
99 views

Primality criterion for Mersenne numbers involving Euler's totient function

I am looking for a proof of the following claim: Let $M_p=2^p-1$ where $p$ is a prime . Denote Euler's totient function by $\varphi(n)$ . Then, $$M_p \text{ is prime iff } \varphi(M_p) \equiv 2 \pmod{...
Pedja's user avatar
  • 12.9k
3 votes
2 answers
555 views

Why are the Mersenne numbers so factor-poor?

The Mersenne numbers (those numbers of the form $2^N-1$), like any positive integers greater than 1, may be either prime (having no divisors1 other than 1), or composite (able to be produced by the ...
Vikki's user avatar
  • 131
1 vote
1 answer
296 views

How to prove than $a+b+c = 2^n-1$ and $a^2+b^2+c^2 = (4^n-1)/3$ have integer solutions only with Mersenne exponent or exponents of Mersenne exponent?

I noticed something with Mersenne numbers : you can write it with the form $a+b+c = 2^n-1$ and $a²+b²+c² = (4^n-1)/3$ when $n$ is a odd Mersenne exponent (3, 5, 7, 13 ...) or an exponent of a odd ...
kijinSeija's user avatar
3 votes
1 answer
182 views

How are all Mersenne primes are of the form $27x^2+4y^2$ (except 3 and 7)?

I noticed something interesting with Mersenne primes numbers: You can write it with the form $27x^2+4y^2$ except for 3 and 7 but it seems to work with all other Mersenne primes numbers and their ...
kijinSeija's user avatar
33 votes
0 answers
1k views

For any fixed integer $ a \gt 1 $, how do you prove that $\frac{a^p-1}{a-1}$ is not always prime given prime $ p \not \mid a-1$?

I assumed this would be easy to prove but it turned out to be quite hard since the go to methods don't work on this problem. Once we fix any $a\gt 1$, we need an algorithm to produce a prime $p$ that ...
arbashn's user avatar
  • 685
0 votes
2 answers
741 views

Mersenne primes and the modulus operation [closed]

Let $p=2^q-1$ be a Mersenne prime. I then want to prove that $$ x\equiv ((x \text{ mod } 2^q) + \lfloor x/2^q\rfloor) \quad(\text{mod } p) $$ How do I do this? Any sort of help would be greatly ...
TheCollegeStudent's user avatar
5 votes
3 answers
458 views

Divisibility of Mersenne numbers

Is there a way to prove that $2$ is the only prime that never divides $2^n-1$ ? Obviously we can ignore all primes that are themselves of this form. Some other examples: $$5\,|\,2^4-1 \qquad 9\,|\,2^6-...
Christian's user avatar
  • 2,125
2 votes
1 answer
56 views

For any odd number, $n$, does there always exist $k$ such that $2^k-1$ is a multiple of $n$?

I assume the statement is true, and I'm sure there may substantial evidence for is (such as it being a sequence on the OEIS). However I'm unsure if this is a well-known theorem (solved or not), or of ...
Graviton's user avatar
  • 4,472
6 votes
2 answers
495 views

Mersenne primes before computers

On the Wikipedia page there is an ordered list of Mersenne primes and the dates they were discovered. The largest such primes and most recent discoveries were made with the help computers. But the ...
no lemon no melon's user avatar
0 votes
2 answers
245 views

Distinct Mersenne numbers are relatively prime specific proof verification [duplicate]

As the title states, I'm supposed to prove for distinct primes $p_1,p_2 >2$ the primes dividing $2^{p_1}-1$ and $2^{p_2}-1$ are distinct. The Wikipedia page on Theorems about Mersenne Numbers ...
no lemon no melon's user avatar
0 votes
2 answers
106 views

Are there any plausible arguments for the infinity of right shifted prime numbers? [closed]

By "right shifted prime numbers" I mean prime numbers of the form: $p_r \equiv$ $ 1 $ $mod $ $6$. $p_l \equiv$ $5$ $mod$ $6$ on the other side would be a left shifted prime number. Since all ...
Eugen's user avatar
  • 238
4 votes
1 answer
250 views

Most efficient way to square modulo a Mersenne prime

I realise this question is somewhere in between Math StackExchange and StackOverflow. So forgive me if this is too much of a practical question, it would probably too theoretical elsewhere. I am ...
Matteo Monti's user avatar
2 votes
2 answers
101 views

Connections between Mersenne Primes and Codes

I recently watched the video for the talk The Biggest Known Prime Number (slides located here) by Keith Conrad, which is on Mersenne primes $M_n = 2^n-1$. It is well-known that such numbers can be ...
Mark Schultz-Wu's user avatar
3 votes
1 answer
171 views

How to check whether Mersenne number is a prime or composite by using theorem $q = 2kp + 1$?

How to know that whether any Mersenne Number, $M_{m}$ whether is a prime, or composite? I have learnt that $M_{m}=2^m-1$ , for $m$ is any positive interger. And there is a theorem, says that : if $p$ ...
Gambit's user avatar
  • 285
1 vote
1 answer
135 views

Use the quadratic reciprocity to show that 5 is a square modulo $M_l$ if and only if $l$ ≡ 1 (mod 4).

Let $l$ be an odd prime such that $M_l = 2^l − 1$ is a Mersenne prime. Use the quadratic reciprocity to show that 5 is a square modulo $M_l$ if and only if $l$ ≡ 1 (mod 4). Here's what I know: Using ...
lexren17's user avatar