Need help with a discrete math problem.

- anonymous

Need help with a discrete math problem.

- Stacey Warren - Expert brainly.com

Hey! We 've verified this expert answer for you, click below to unlock the details :)

- chestercat

I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!

- anonymous

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?

##### 1 Attachment

- anonymous

@phi

- phi

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

Looking for something else?

Not the answer you are looking for? Search for more explanations.

## More answers

- anonymous

I'm not understanding where all the numbers come from

- anonymous

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

- anonymous

I thought p was the prime number

- phi

the prime has 2^.....161
your p has 2^....167 which is 2^6 bigger

- anonymous

oh! I read the question wrong.

- anonymous

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

- phi

yes

- phi

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

- anonymous

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

- anonymous

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

- phi

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

- anonymous

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?

- phi

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

- phi

both are divisible by 2 ?

- anonymous

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?

- anonymous

I guess, I'm not sure.

- phi

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

- anonymous

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

- anonymous

but thanks for the help I will keep trying

- phi

ok

- anonymous

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

- phi

interesting, but your problem has awfully big numbers.

- anonymous

yeah

- anonymous

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

- anonymous

@jim_thompson5910 @ganeshie8 @.Sam.
Anyone know how to solve this problem?

- DebbieG

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.

- anonymous

Ok thanks.

- anonymous

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.

- anonymous

Some of my notes on how to start the problem.
m = 2^k - 1
n = 2^k + 1
n - m = 2

- anonymous

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.

- DebbieG

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.

- anonymous

yes, that is what we are looking for

- anonymous

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

- anonymous

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

- anonymous

lol I don't know if that is right either

- anonymous

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

- DebbieG

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=.....

- anonymous

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

- DebbieG

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

- DebbieG

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

- anonymous

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

- anonymous

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

- anonymous

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!

- DebbieG

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....?

- anonymous

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

- DebbieG

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?

- DebbieG

I got this from here:
http://www.millersville.edu/~bikenaga/number-theory/gcd/gcd.pdf
Bottom of pg 1 - top of pg 2.

- anonymous

Hahahaha

- anonymous

Wow, thats awesome! :D

- DebbieG

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

- anonymous

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

- DebbieG

you're welcome. :)

Looking for something else?

Not the answer you are looking for? Search for more explanations.