anonymous
  • anonymous
Find all prime numbers \(p\) such that\[\frac{2^{p-1}-1}{p}\]is a perfect square
Meta-math
  • 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.
schrodinger
  • schrodinger
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
anonymous
  • anonymous
@ganeshie8 @sauravshakya
anonymous
  • anonymous
@Neemo this group is a good place for us amigo :)
anonymous
  • anonymous
*

Looking for something else?

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

More answers

anonymous
  • anonymous
\[ p=3 ;\, \quad \frac{2^{p-1}-1}{p}=1\\ p=7 ;\, \quad \frac{2^{p-1}-1}{p}=9\\ \]
anonymous
  • anonymous
I think that this is all the primes solutions. I am still working on proving it.
anonymous
  • anonymous
yes sir thats just \(p=3,7\)
anonymous
  • anonymous
@ganeshie8 got any idea?
ganeshie8
  • ganeshie8
not yet, \(\frac{2^{p-1}-1}{p} = n^2\) \(2^{p-1} - 1= p*n^2\)
ganeshie8
  • ganeshie8
not getting any ideas :S
anonymous
  • anonymous
p=2 is not answer so p is odd\[(2^{\frac{p-1}{2}}-1)(2^{\frac{p-1}{2}}+1)=pn^2\]
ganeshie8
  • ganeshie8
very well that makes sense muku.... now we use the factoring thing as we did in prev problems... or this one is hard ?
anonymous
  • anonymous
no this is not about factoring after this
ganeshie8
  • ganeshie8
left side factors are co-prime
anonymous
  • anonymous
ahh thats the point gane
ganeshie8
  • ganeshie8
so n^2 must equal to one of the factors ?
ganeshie8
  • ganeshie8
or if one factor is 1, other factor can equal pn^2
ganeshie8
  • ganeshie8
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
anonymous
  • anonymous
ur first guess is right but we need to make that more accurate
ganeshie8
  • ganeshie8
we can say n^2 must equal one of the factors ? i dont see hw :|
ganeshie8
  • ganeshie8
il grab som coffee brb :)
anonymous
  • anonymous
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\]
anonymous
  • anonymous
again\[\gcd(\frac{2^{\frac{p-1}{2}}-1}{p}\ , \ 2^{\frac{p-1}{2}}+1)=1\]
anonymous
  • anonymous
so one of the factors is 1 and other is n^2
ganeshie8
  • ganeshie8
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 ?
anonymous
  • anonymous
gane im wrong
anonymous
  • anonymous
and ur last reply is our start point...so lets work on that
anonymous
  • anonymous
but im sure this is right :) if \(ab=n^2\) and \(\gcd(a,b)=1\) then\[a=m^2\]\[b=k^2\]
anonymous
  • anonymous
@ganeshie8
anonymous
  • anonymous
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\)
anonymous
  • anonymous
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?
anonymous
  • anonymous
*my last reply\[(2^{\frac{p-1}{2}}-1)\frac{2^{\frac{p-1}{2}}+1}{p}=n^2\]
anonymous
  • anonymous
\[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\)
experimentX
  • experimentX
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
anonymous
  • anonymous
these values makes that expression integer ??
experimentX
  • experimentX
the above expression is a perfect square.
experimentX
  • experimentX
between 1000-10000, there is only 1009 1013 1019 1021
anonymous
  • anonymous
exper are u sure? because p=113 dont makes it a perfect square
experimentX
  • experimentX
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
experimentX
  • experimentX
I'm not good with modular arithmetic
anonymous
  • anonymous
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?
experimentX
  • experimentX
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.
anonymous
  • anonymous
what is integerpart function in matlab?
experimentX
  • experimentX
http://www.mathworks.com/matlabcentral/newsreader/view_thread/163080
anonymous
  • anonymous
Access Denied
experimentX
  • experimentX
Damn
experimentX
  • experimentX
try viewing with this http://hidemyass.com/
experimentX
  • experimentX
does this work for you http://2.hidemyass.com/ip-1/encoded/Oi8vd3d3Lm1hdGh3b3Jrcy5jb20vbWF0bGFiY2VudHJhbC9uZXdzcmVhZGVyL3ZpZXdfdGhyZWFkLzE2MzA4MA%3D%3D&f=norefer
anonymous
  • anonymous
i got it
anonymous
  • anonymous
i think MATLAB cuts the fractional part for big numbers
experimentX
  • experimentX
might ... how do you know that 2^113 - 1/ 113 is not a perfect square.
anonymous
  • anonymous
\[\sqrt{\frac{2^{112}-1}{113}}=6778608243699229.0869912287347921\]
experimentX
  • experimentX
oh .. they are all primes ... didn't note that. BYW what calculator are you using? this is giving me ... e ....
anonymous
  • anonymous
lol...my windows calc
experimentX
  • experimentX
looks like matlab is unable to handle it.
anonymous
  • anonymous
yeah :/
experimentX
  • experimentX
i find numbers hard ... especially big numbers ... lol
anonymous
  • anonymous
:D
ganeshie8
  • ganeshie8
\((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 ?
anonymous
  • anonymous
\[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
ganeshie8
  • ganeshie8
wow !! so RHS can have prime factorization in 2 only. beautiful proof muku :)
ganeshie8
  • ganeshie8
and second case is obvious !!
anonymous
  • anonymous
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

Looking for something else?

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