Question

Need help with a discrete math problem.

Answer 1

So I was thinking I could set (2^57,885,167 - 1) = p

I would then need to solve for the gcd of p and p+2.

Is this right and how would I get the gcd of p and p+2?

Answer 2

@phi

Answer 3

if we call the prime x
to get your p: 2^6*x + 2^6 -1 = 64x +63 = 2^6 x + 3^2 * 9
p+2 is 64x+65 = 2^6 x + 5*13

Answer 4

I'm not understanding where all the numbers come from

Answer 5

I'm not sure exactly what we are calling x =\

Answer 6

I thought p was the prime number

Answer 7

the prime has 2^.....161

your p has 2^....167 which is 2^6 bigger

Answer 8

oh! I read the question wrong.

Answer 9

so we still have to find the gcd between 2^6 x + 3^2 * 9 and 2^6 x + 5*13 then?

Answer 10

yes

Answer 11

but 63 should be factored into 7* 3^2 (I have a typo up above)

Answer 12

ah ok, so 2^6 x + 7* 3^2 and 2^6 x + 5*13

Answer 13

And I have no clue how to find the gcd of that.

Answer 14

I don't do number theory, but my first thought is gcd = 1

Answer 15

So what if we let (2^57,885,161 - 1) = p

Since both p and 2 are prime, wouldn't any common divisor greater than 1

divide both p and 2?

Answer 16

let (2^57,885,161 - 1) = p
then neither of these is evenly divisible by p
2^6 p + 7* 3^2 and 2^6 p + 5*13

Answer 17

both are divisible by 2 ?

Answer 18

hmm, I *don't(lol) really understand it that well. I would think there would be a fairly simple solution though. Does discrete math go into number theory?

Answer 19

I guess, I'm not sure.

Answer 20

I don't know. I would look at the text book

Answer 21

The text book doesn't make any sense to me at all :\

Answer 22

but thanks for the help I will keep trying

Answer 23

ok

Answer 24

Hmm I wonder if this would have anything to do with it http://math.stackexchange.com/questions/7473/prove-that-gcdan-1-am-1-a-gcdn-m-1

Answer 25

interesting, but your problem has awfully big numbers.

Answer 26

yeah

Answer 27

My teacher said the size of the numbers shouldn't make any difference in solving the problem though.

Answer 28

@jim_thompson5910 @ganeshie8 @.Sam.

Anyone know how to solve this problem?

Answer 29

So we have that \(\Large 2^{57,885,161}-1\) is prime.

Now we want to find the GCD of

\(\Large 2^{57,885,167}-1\) and \(\Large 2^{57,885,167}+1\)

And...

\(\Large 2^{57,885,167}=2^{57,885,161}\cdot2^{6}\)

OK, that's as far as I've gotten, lol. I like this problem, but am not sure what to do with it. If I have any ideas, I'll let you know.

Answer 30

Ok thanks.

Answer 31

My teacher was saying to make a substitution for the power. like x = 57,885,161 and figure out how to solve that. He said the size of the power doesn't make a difference. But I don't know how that would work out.

Answer 32

Some of my notes on how to start the problem.

m = 2^k - 1

n = 2^k + 1

n - m = 2

Answer 33

Let 257,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.

This is apparently how it is suppose to start. But I don't understand how that makes it easier to solve.

Answer 34

Now, wait... either I misunderstand the problem, or you mistated it.... if the prime = p, then aren't we looking for the GCD of:

\(\Large p\cdot2^6+1, p\cdot2^6-1\) ??

Which still differ by 2.... but not quite what you said above.

Answer 35

yes, that is what we are looking for

Answer 36

Wait, if p = 257,885,161−1 we would be looking for 2^p⋅26+1,2^p⋅26−1 right?

Answer 37

2^p⋅2^6+1,2^p⋅2^6−1

Answer 38

lol I don't know if that is right either

Answer 39

So yeah, if the prime equals p, what you said would be right.

Answer 40

I don't know, I'm getting confused....
We want the GCD of \(\Large p\cdot2^6+1, p\cdot2^6-1\) where p= the prime number.

ok, I guess it depends on what we let p=.....

Answer 41

If we let p = 2^257,885,161 then that would be correct

Answer 42

Oh crap, wait a sec...... none of this works.

Answer 43

The prime number is \(\Large 2^{57,885,161}-1\)

We want GCF of \(\Large 2^{57,885,167}-1,2^{57,885,167}+1\)

which is \(\Large 2^{57,885,161}\cdot 2^6-1,2^{57,885,161}\cdot 2^6+1\)

So letting \(\Large p=2^{57,885,161}-1\) doesn't work.....

But I guess we can let \(\Large p=57,885,161\) (call it the"prime's power"?)

And then we can say that we need the GCF of:
\(\Large 2^p\cdot 2^6-1,2^p\cdot 2^6+1\)

which I think is what you were trying to say above.... but I don't know where that gets us.... lol

Answer 44

Yeah that makes sense, but where to go from there is the problem...

Answer 45

I'm gonna start a new question with what I have so far.

Answer 46

Well I guess I'm gonna try to look in the book some more and see if I can find anything else. Thank you so much for all the help!

Answer 47

Sure, sorry we didn't come up with anything more successful... there must be some theorem that you can use that we are just missing....?

Answer 48

I don't really know I have a few notes written down for this type of problem but I can't make much sense of them lolz.
_______________________________________

gcd(n, n+1) = 1

d|n, d|n+1

d*k1 = n d*k2 = n+1

______________________________________

d|m, d|n --> d|(m+n)

d|m i.e. m = dki m+n = d(k+l)

d|n i.e. n=dl i.e. d|(m+n)

______________________________________

m = 2^k - 1

n = 2^k + 1

n - m = 2

Answer 49

OK, wait... I was looking up some number theory/ GCD stuff. I found this:

(a, b) = (a+kb, b) for any integer k

HAH! So tell me if this works.....


\(\Large (2^p\cdot 2^6-1,2^p\cdot 2^6+1)\)

Now let k=-1, so we subtract the first one from the second one:

\(\Large 2^p\cdot 2^6+1-(2^p\cdot 2^6-1)=2\)

So now we have:
\(\Large (2^p\cdot 2^6-1,2)\)

Which..... pretty unquestionably.... is 1. Methinks?

Answer 50

I got this from here:
http://www.millersville.edu/~bikenaga/number-theory/gcd/gcd.pdf

Bottom of pg 1 - top of pg 2.

Answer 51

Hahahaha

Answer 52

Wow, thats awesome! :D

Answer 53

Pretty easy once you know the "trick", huh? As is usually the case.... lol.

Answer 54

Yeah seriously...and thanks again for all the help! :)

Answer 55

you're welcome. :)