anonymous
  • anonymous
Need help with a discrete math problem.
Mathematics
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
chestercat
  • chestercat
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
anonymous
  • 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
  • anonymous
@phi
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
  • anonymous
I'm not understanding where all the numbers come from
anonymous
  • anonymous
I'm not sure exactly what we are calling x =\
anonymous
  • anonymous
I thought p was the prime number
phi
  • phi
the prime has 2^.....161 your p has 2^....167 which is 2^6 bigger
anonymous
  • anonymous
oh! I read the question wrong.
anonymous
  • anonymous
so we still have to find the gcd between 2^6 x + 3^2 * 9 and 2^6 x + 5*13 then?
phi
  • phi
yes
phi
  • phi
but 63 should be factored into 7* 3^2 (I have a typo up above)
anonymous
  • anonymous
ah ok, so 2^6 x + 7* 3^2 and 2^6 x + 5*13
anonymous
  • anonymous
And I have no clue how to find the gcd of that.
phi
  • phi
I don't do number theory, but my first thought is gcd = 1
anonymous
  • 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
  • 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
  • phi
both are divisible by 2 ?
anonymous
  • 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
  • anonymous
I guess, I'm not sure.
phi
  • phi
I don't know. I would look at the text book
anonymous
  • anonymous
The text book doesn't make any sense to me at all :\
anonymous
  • anonymous
but thanks for the help I will keep trying
phi
  • phi
ok
anonymous
  • 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
  • phi
interesting, but your problem has awfully big numbers.
anonymous
  • anonymous
yeah
anonymous
  • anonymous
My teacher said the size of the numbers shouldn't make any difference in solving the problem though.
anonymous
  • anonymous
@jim_thompson5910 @ganeshie8 @.Sam. Anyone know how to solve this problem?
DebbieG
  • 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
  • anonymous
Ok thanks.
anonymous
  • 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
  • anonymous
Some of my notes on how to start the problem. m = 2^k - 1 n = 2^k + 1 n - m = 2
anonymous
  • 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
  • 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
  • anonymous
yes, that is what we are looking for
anonymous
  • anonymous
Wait, if p = 257,885,161−1 we would be looking for 2^p⋅26+1,2^p⋅26−1 right?
anonymous
  • anonymous
2^p⋅2^6+1,2^p⋅2^6−1
anonymous
  • anonymous
lol I don't know if that is right either
anonymous
  • anonymous
So yeah, if the prime equals p, what you said would be right.
DebbieG
  • 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
  • anonymous
If we let p = 2^257,885,161 then that would be correct
DebbieG
  • DebbieG
Oh crap, wait a sec...... none of this works.
DebbieG
  • 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
  • anonymous
Yeah that makes sense, but where to go from there is the problem...
anonymous
  • anonymous
I'm gonna start a new question with what I have so far.
anonymous
  • 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
  • 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
  • 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
  • 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
  • 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
  • anonymous
Hahahaha
anonymous
  • anonymous
Wow, thats awesome! :D
DebbieG
  • DebbieG
Pretty easy once you know the "trick", huh? As is usually the case.... lol.
anonymous
  • anonymous
Yeah seriously...and thanks again for all the help! :)
DebbieG
  • DebbieG
you're welcome. :)

Looking for something else?

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