Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

mukushla

Find all prime numbers \(p\) such that\[\frac{2^{p-1}-1}{p}\]is a perfect square

  • one year ago
  • one year ago

  • This Question is Closed
  1. mukushla
    Best Response
    You've already chosen the best response.
    Medals 1

    @ganeshie8 @sauravshakya

    • one year ago
  2. mukushla
    Best Response
    You've already chosen the best response.
    Medals 1

    @Neemo this group is a good place for us amigo :)

    • one year ago
  3. eliassaab
    Best Response
    You've already chosen the best response.
    Medals 0

    *

    • one year ago
  4. eliassaab
    Best Response
    You've already chosen the best response.
    Medals 0

    \[ p=3 ;\, \quad \frac{2^{p-1}-1}{p}=1\\ p=7 ;\, \quad \frac{2^{p-1}-1}{p}=9\\ \]

    • one year ago
  5. eliassaab
    Best Response
    You've already chosen the best response.
    Medals 0

    I think that this is all the primes solutions. I am still working on proving it.

    • one year ago
  6. mukushla
    Best Response
    You've already chosen the best response.
    Medals 1

    yes sir thats just \(p=3,7\)

    • one year ago
  7. sauravshakya
    Best Response
    You've already chosen the best response.
    Medals 0

    @ganeshie8 got any idea?

    • one year ago
  8. ganeshie8
    Best Response
    You've already chosen the best response.
    Medals 1

    not yet, \(\frac{2^{p-1}-1}{p} = n^2\) \(2^{p-1} - 1= p*n^2\)

    • one year ago
  9. ganeshie8
    Best Response
    You've already chosen the best response.
    Medals 1

    not getting any ideas :S

    • one year ago
  10. mukushla
    Best Response
    You've already chosen the best response.
    Medals 1

    p=2 is not answer so p is odd\[(2^{\frac{p-1}{2}}-1)(2^{\frac{p-1}{2}}+1)=pn^2\]

    • one year ago
  11. ganeshie8
    Best Response
    You've already chosen the best response.
    Medals 1

    very well that makes sense muku.... now we use the factoring thing as we did in prev problems... or this one is hard ?

    • one year ago
  12. mukushla
    Best Response
    You've already chosen the best response.
    Medals 1

    no this is not about factoring after this

    • one year ago
  13. ganeshie8
    Best Response
    You've already chosen the best response.
    Medals 1

    left side factors are co-prime

    • one year ago
  14. mukushla
    Best Response
    You've already chosen the best response.
    Medals 1

    ahh thats the point gane

    • one year ago
  15. ganeshie8
    Best Response
    You've already chosen the best response.
    Medals 1

    so n^2 must equal to one of the factors ?

    • one year ago
  16. ganeshie8
    Best Response
    You've already chosen the best response.
    Medals 1

    or if one factor is 1, other factor can equal pn^2

    • one year ago
  17. ganeshie8
    Best Response
    You've already chosen the best response.
    Medals 1

    that looks wrong, cuz if n^2 = k^2m^2l^2... , then few prime factors for ex, k^2m^2 can make first factor, while remaining pl^2 can make the second factor.. hmm

    • one year ago
  18. mukushla
    Best Response
    You've already chosen the best response.
    Medals 1

    ur first guess is right but we need to make that more accurate

    • one year ago
  19. ganeshie8
    Best Response
    You've already chosen the best response.
    Medals 1

    we can say n^2 must equal one of the factors ? i dont see hw :|

    • one year ago
  20. ganeshie8
    Best Response
    You've already chosen the best response.
    Medals 1

    il grab som coffee brb :)

    • one year ago
  21. mukushla
    Best Response
    You've already chosen the best response.
    Medals 1

    ok suppose that p is divisor of first factor \[\frac{2^{\frac{p-1}{2}}-1}{p}(2^{\frac{p-1}{2}}+1)=n^2\]

    • one year ago
  22. mukushla
    Best Response
    You've already chosen the best response.
    Medals 1

    again\[\gcd(\frac{2^{\frac{p-1}{2}}-1}{p}\ , \ 2^{\frac{p-1}{2}}+1)=1\]

    • one year ago
  23. mukushla
    Best Response
    You've already chosen the best response.
    Medals 1

    so one of the factors is 1 and other is n^2

    • one year ago
  24. ganeshie8
    Best Response
    You've already chosen the best response.
    Medals 1

    i believe u muku but i dont understand how thats possible, \( \frac{2^{\frac{p-1}{2}}-1}{p}(2^{\frac{p-1}{2}}+1)=n^2 \) lets say first factor = k^2, and second factor = m^2 n = km hw can we say one of the factor must equal n^2 ?

    • one year ago
  25. mukushla
    Best Response
    You've already chosen the best response.
    Medals 1

    gane im wrong

    • one year ago
  26. mukushla
    Best Response
    You've already chosen the best response.
    Medals 1

    and ur last reply is our start point...so lets work on that

    • one year ago
  27. mukushla
    Best Response
    You've already chosen the best response.
    Medals 1

    but im sure this is right :) if \(ab=n^2\) and \(\gcd(a,b)=1\) then\[a=m^2\]\[b=k^2\]

    • one year ago
  28. mukushla
    Best Response
    You've already chosen the best response.
    Medals 1

    @ganeshie8

    • one year ago
  29. mukushla
    Best Response
    You've already chosen the best response.
    Medals 1

    suppose that \(p\) is a divisor of \(2^{\frac{p-1}{2}}-1\)\[\frac{2^{\frac{p-1}{2}}-1}{p}(2^{\frac{p-1}{2}}+1)=n^2\]this implies that\[\frac{2^{\frac{p-1}{2}}-1}{p}=k^2\]\[2^{\frac{p-1}{2}}+1=m^2\]\(m,k\) are odd numbers\[2^{\frac{p-1}{2}}+1=m^2=4t^2+4t+1\]\[2^{\frac{p-1}{2}}=4t^2+4t\]\[2^{\frac{p-1}{2}-2}=t(t+1)\]so \(t=1\) and \(p=7\)

    • one year ago
  30. mukushla
    Best Response
    You've already chosen the best response.
    Medals 1

    now suppose that \(p\) is a divisor of \(2^{\frac{p-1}{2}}+1\)\[\frac{2^{\frac{p-1}{2}}-1}{p}(2^{\frac{p-1}{2}}+1)=n^2\]this implies that\[\frac{2^{\frac{p-1}{2}}+1}{p}=k^2\]\[2^{\frac{p-1}{2}}-1=m^2\]now what?

    • one year ago
  31. mukushla
    Best Response
    You've already chosen the best response.
    Medals 1

    *my last reply\[(2^{\frac{p-1}{2}}-1)\frac{2^{\frac{p-1}{2}}+1}{p}=n^2\]

    • one year ago
  32. mukushla
    Best Response
    You've already chosen the best response.
    Medals 1

    \[2^{\frac{p-1}{2}}-1=m^2\]m is odd\[2^{\frac{p-1}{2}}-1=4t^2+4t+1\]\[2^{\frac{p-1}{2}}-2=4t(t+1)\]RHS is divisible by 4 but LHS not this implies that \(t=0\) so \(p=3\)

    • one year ago
  33. experimentX
    Best Response
    You've already chosen the best response.
    Medals 0

    here a numeric solution 1-1000 3 7 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997

    • one year ago
  34. mukushla
    Best Response
    You've already chosen the best response.
    Medals 1

    these values makes that expression integer ??

    • one year ago
  35. experimentX
    Best Response
    You've already chosen the best response.
    Medals 0

    the above expression is a perfect square.

    • one year ago
  36. experimentX
    Best Response
    You've already chosen the best response.
    Medals 0

    between 1000-10000, there is only 1009 1013 1019 1021

    • one year ago
  37. mukushla
    Best Response
    You've already chosen the best response.
    Medals 1

    exper are u sure? because p=113 dont makes it a perfect square

    • one year ago
  38. experimentX
    Best Response
    You've already chosen the best response.
    Medals 0

    i used this piece of code on matlab clc; p = primes(100000); for i=1:length(p) if rem(sqrt((2^(p(i)-1)-1)/p(i)),1) == 0; disp(p(i)); end; end

    • one year ago
  39. experimentX
    Best Response
    You've already chosen the best response.
    Medals 0

    I'm not good with modular arithmetic

    • one year ago
  40. mukushla
    Best Response
    You've already chosen the best response.
    Medals 1

    ahh...my guess is right we want this expression\[\frac{2^{p-1}-1}{p}\]to be a perfect square not an integer...can u write a little code for it?

    • one year ago
  41. experimentX
    Best Response
    You've already chosen the best response.
    Medals 0

    IDK how matlab works with big numbers... but that code should give you perfect square. for every prime p, the expression should be an integer by fermat last theorem.

    • one year ago
  42. mukushla
    Best Response
    You've already chosen the best response.
    Medals 1

    what is integerpart function in matlab?

    • one year ago
  43. experimentX
    Best Response
    You've already chosen the best response.
    Medals 0

    http://www.mathworks.com/matlabcentral/newsreader/view_thread/163080

    • one year ago
  44. mukushla
    Best Response
    You've already chosen the best response.
    Medals 1

    Access Denied

    • one year ago
  45. experimentX
    Best Response
    You've already chosen the best response.
    Medals 0

    Damn

    • one year ago
  46. experimentX
    Best Response
    You've already chosen the best response.
    Medals 0

    try viewing with this http://hidemyass.com/

    • one year ago
  47. mukushla
    Best Response
    You've already chosen the best response.
    Medals 1

    i got it

    • one year ago
  48. mukushla
    Best Response
    You've already chosen the best response.
    Medals 1

    i think MATLAB cuts the fractional part for big numbers

    • one year ago
  49. experimentX
    Best Response
    You've already chosen the best response.
    Medals 0

    might ... how do you know that 2^113 - 1/ 113 is not a perfect square.

    • one year ago
  50. mukushla
    Best Response
    You've already chosen the best response.
    Medals 1

    \[\sqrt{\frac{2^{112}-1}{113}}=6778608243699229.0869912287347921\]

    • one year ago
  51. experimentX
    Best Response
    You've already chosen the best response.
    Medals 0

    oh .. they are all primes ... didn't note that. BYW what calculator are you using? this is giving me ... e ....

    • one year ago
  52. mukushla
    Best Response
    You've already chosen the best response.
    Medals 1

    lol...my windows calc

    • one year ago
  53. experimentX
    Best Response
    You've already chosen the best response.
    Medals 0

    looks like matlab is unable to handle it.

    • one year ago
  54. mukushla
    Best Response
    You've already chosen the best response.
    Medals 1

    yeah :/

    • one year ago
  55. experimentX
    Best Response
    You've already chosen the best response.
    Medals 0

    i find numbers hard ... especially big numbers ... lol

    • one year ago
  56. mukushla
    Best Response
    You've already chosen the best response.
    Medals 1

    :D

    • one year ago
  57. ganeshie8
    Best Response
    You've already chosen the best response.
    Medals 1

    \((2^{\frac{p-1}{2}}-1)(2^{\frac{p-1}{2}}+1) = pn^2\) two cases : case I : \(p \ |\ (2^{\frac{p-1}{2}}-1) \) => \(2^{\frac{p-1}{2}}+1 = m^2\) \(m\) is an odd number \(2^{\frac{p-1}{2}}+1 = m^2 = (2t+1)^2\) \(2^{\frac{p-1}{2}-2} = m^2 = t(t+1)\) now what ? we do trial and error is it ? and hw do we knw only one solution exist for this case ?

    • one year ago
  58. mukushla
    Best Response
    You've already chosen the best response.
    Medals 1

    \[2^{\frac{p-1}{2}}+1 = m^2 = (2t+1)^2=4t^2+4t+1\]\[2^{\frac{p-1}{2}} =4t^2+4t=4t(t+1)\]\[2^{\frac{p-1}{2}-2}=t(t+1)\]if \(t>1\) RHS has a an odd factor but LHS is a power of 2 .. so t=1

    • one year ago
  59. ganeshie8
    Best Response
    You've already chosen the best response.
    Medals 1

    wow !! so RHS can have prime factorization in 2 only. beautiful proof muku :)

    • one year ago
  60. ganeshie8
    Best Response
    You've already chosen the best response.
    Medals 1

    and second case is obvious !!

    • one year ago
  61. mukushla
    Best Response
    You've already chosen the best response.
    Medals 1

    yes u made a good way...and finally we got it completely this posted regarding ur point http://openstudy.com/study#/updates/504857ade4b003bc12040f69 see sir @eliassaab reply

    • one year ago
    • Attachments:

See more questions >>>

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.