PSA on Mersenne primes

Number Theory Level 2

As of December 22, 2018, GIMPS has discovered the largest known prime number, $2^{82589933} - 1$ . Beating the previous record , $2^{77232917} - 1$ .

Without using any computer assistance, calculate the greatest common divisor , of the two numbers, 82589933 and 77232917.

The answer is 1.

2 solutions

Henry U
Dec 23, 2018

There is a theorem about Mersenne numbers

If $n$ is composite, then $M_n$ is also composite, and in particular $M_n$ is divisible by $M_m$ for all divisors $m$ of $n$ .

The contrapositive – which is also always true for true statements – of the first part of this theorem is

If $M_n$ is prime (not composite) then $n$ is also prime.

Since $2^{82589933}-1 = M_{82589933}$ and $2^{77232917}-1 = M_{77232917}$ are both prime, $82589933$ and $77232917$ also have to be prime.

From this, it follows directly that the two numbers can't have any common divisors, so their greatest common divisors is 1 .

Just about to use the Euclidean algorithm...

X X - 2 years, 5 months ago

That would take a little while... Do you know, if there is an approximation for the number of step the algoritm takes for 2 coprime integers?

Henry U - 2 years, 5 months ago

No, but I would like to know that!

X X - 2 years, 5 months ago

@X X – In the German Wikipedia article , it says that the worst case are numbers with ratio approximately $\phi$ and especially consecutive Fibonacci numbers, because they are also coprime and the algorithm generates all Fibonacci numbers before these two numbers. In this worst case, the worst-case number of steps is $\Theta(\log(ab))$ , but since every step takes time, the worst-case running time is $O(\log(ab)^3)$ .

Henry U - 2 years, 5 months ago

@Henry U – Oh wow, an unexpected lesson here. Thanks.

Pi Han Goh - 2 years, 5 months ago

@Henry U – Sorry, but can you explain what do $Θ(\log(ab))$ and $O(\log(ab)^3$ mean?

X X - 2 years, 5 months ago

@X X – Actually, I don't really know the difference between $\Omega$ and $O$ , but they mean that the function we are looking (the greatest common divisor) grows more or less like the function that is in the parentheses ( $\log(ab)$ .

For this comparison, we ignore constants and ower degree terms , for example you could write $3x^2-6x+10^6 = O(x^2)$ meaning that the function grows quadratically , so doubling the input will approximately multiply tbe outpit by 4.

The notation $f(x) = O(g(x))$ is not an equation, it's only a shorter form of $f(x) \in O(g(x))$ where $O(g(x))$ denotes the set of all functions that grow like $g(x)$ .

You can read more about this under the name Big-O-Notation

Henry U - 2 years, 5 months ago

@Henry U – Thank you!

X X - 2 years, 5 months ago

Sathvik Acharya
Apr 26, 2019

Theorem: $\text{gcd}(a^m-1,a^n-1)=a^{\text{gcd}(m,n)}-1$ In this case, $a=2, m=82589933$ and $n=77232917$ . By the above theorem, we have $\text{gcd}(2^{82589933}-1, 2^{77232917}-1)=2^{\text{gcd}(82589933, 77232917)}-1$ Since we are given that both $2^{82589933}-1$ and $2^{77232917}-1$ are primes, their greatest common divisor must be $1$ . Therefore, $2^{\text{gcd}(82589933, 77232917)}-1=1$ $\implies 2^{\text{gcd}(82589933, 77232917)}=2$ $\;\;\;\;\;\;\;\;\;\;\;\;\implies \text{gcd}(82589933, 77232917)=\boxed{1}$

PSA on Mersenne primes

The answer is 1.

2 solutions

0 pending reports