Question

Need help with a discrete math problem.

Contriutor to the Great Internet Mersenne Prime Search, Curtix Cooper, of the Iniversity of Central Missouri, recently discovered that 2^57,885,161 - 1 is prime. To date, no larger number has been shown to be prime. What is the greatest common divisor of 2^57,885,161 - 1 and 2^57,885,161 + 1?

Answer 1

Do you have any ideas?

Answer 2

not really

Answer 3

Do you know how to start?

Answer 4

Well I know how to find the gcd of smaller numbers like 16 and 27 by dividing the larger number by the smaller number. Then I take the remainder and divide the smaller number by the remainder and continue that process until the remainder is 0. That leaves me with the answer. But with a number this big that process would take very long. So I'm not really sure how to start.

Answer 5

So if I used that approach perhaps I could cancel the 2^.........'s and be left with +1 and -1?

Answer 6

When subtracting

Answer 7

Is that your final answer?

Answer 8

no

Answer 9

do you know how it is done?

Answer 10

Hmm, the number being prime probably has something to do with the problem

Answer 11

idk =\

Answer 12

It does.

Answer 13

But I have no clue how that would play into the solution.

Answer 14

=(

Answer 15

Help me with it? :O

Answer 16

Find out the prime in the would be with the remainder of 0

Answer 17

Well, let \(2^{57,885,161}-1=p\). Then you're asked to find the gcd of \(p\) and \(p+2\). Since both \(p\) and 2 are prime, any common divisor greater than 1 must divide both \(p\) and 2.

Does this make sense, and can you finish it from here?

Answer 18

Sort of makes sense

Answer 19

how did you get the p and p + 2?

Answer 20

2^n - 1, is prime ... this is given, let it be p

2^n - 1 + 2 = 2^n + 1 = p+2

Answer 21

ah that makes sense

Answer 22

Alright, thanks for the help everyone! I will look over it some more and see if I can get it all making sense.

Answer 23

Ok good luck:)