On Mersenne Numbers (number theory)

In summary, q divides 2^p-1 and 2^{q-1}-1 by definition of a prime divisor and Euler's theorem, respectively. Using the given equation, it can be shown that if the greatest common divisor of (2^{q-1}-1, 2^p-1) is equal to 2^{\gcd(q-1,p)} - 1, then the greatest common divisor of (q-1, p) is equal to p. This is because there are only two possible values for the greatest common divisor of (n,p) when p is prime: 1 and p. Therefore, q-1 must equal p and the greatest common divisor of (q-1, p
  • #1
louiswins
3
0

Homework Statement


For a positive integer k, the number [itex]M_k = 2^k - 1[/itex] is called the kth Mersenne number. Let p be an odd prime, and let q be a prime that divides [itex]M_p[/itex].

a. Explain why you know that q divides [itex]2^{q-1}-1[/itex].
I have done this already using Euler's theorem, since q prime implies [itex]\varphi(q) = q-1[/itex].

Here is the part that I'm having trouble with:
b. Given that [itex]\gcd(2^{q-1}-1, 2^p-1) = 2^{\gcd(q-1,p)} - 1[/itex], show that [itex]\gcd(q-1, p) = p[/itex].

Homework Equations


Nothing beyond the above.

The Attempt at a Solution


OK, I don't really know how to proceed. Working backwards, iff [itex]\gcd(q-1, p) = q[/itex], the given equation says

[itex]\gcd(2^p-1, 2^{q-1}-1) = 2^p-1[/itex], so
[itex]2^p-1 \mid 2^{q-1}-1[/itex],

but I don't know how to show this. We just have that [itex]q \mid 2^p-1[/itex] and [itex]q \mid 2^{q-1}-1[/itex].
 
Physics news on Phys.org
  • #2
There are only two possible values for gcd(n,p) when p is prime: 1 and p.
 
  • #3
Joffan said:
There are only two possible values for gcd(n,p) when p is prime: 1 and p.

Oh my goodness, you are absolutely right. I don't know how I overlooked this! :blushing:
 

1. What are Mersenne numbers?

Mersenne numbers are a special type of number in mathematics, named after the French mathematician and monk Marin Mersenne. These numbers are in the form of 2n - 1, where n is a positive integer. They are also known as Mersenne primes, as they are only prime numbers when n is also a prime number.

2. How are Mersenne numbers significant in number theory?

Mersenne numbers have been of great interest to mathematicians for centuries due to their unique properties. They have been used in various number theory problems, including the search for the largest known prime number. They are also connected to the famous unsolved problem in mathematics known as the Riemann hypothesis.

3. How many Mersenne numbers are known to exist?

As of 2021, 51 Mersenne primes have been discovered. However, it is believed that there are infinitely many Mersenne primes, but it is yet to be proven. The largest known Mersenne prime has over 24 million digits and was discovered in 2018.

4. Can Mersenne numbers be used for practical applications?

Mersenne numbers have limited practical applications, but they have been used in fields such as cryptography and computer science. They are also used as a benchmark for testing the performance of computer hardware, as they require a lot of computing power to be calculated.

5. Are there any famous problems related to Mersenne numbers?

One of the most famous problems related to Mersenne numbers is the Twin Prime Conjecture, which states that there are infinitely many pairs of prime numbers that differ by 2, such as 41 and 43. Mersenne numbers are also connected to the Goldbach's conjecture, which states that every even number greater than 2 can be expressed as the sum of two prime numbers.

Similar threads

  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
12
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
503
  • Calculus and Beyond Homework Help
Replies
12
Views
998
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
0
Views
66
  • Calculus and Beyond Homework Help
Replies
24
Views
673
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
865
  • Calculus and Beyond Homework Help
Replies
4
Views
635
Back
Top