mukushla Group Title Find all prime numbers $$p$$ such that$\frac{2^{p-1}-1}{p}$is a perfect square one year ago one year ago

1. mukushla Group Title

@ganeshie8 @sauravshakya

2. mukushla Group Title

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

3. eliassaab Group Title

*

4. eliassaab Group Title

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

5. eliassaab Group Title

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

6. mukushla Group Title

yes sir thats just $$p=3,7$$

7. sauravshakya Group Title

@ganeshie8 got any idea?

8. ganeshie8 Group Title

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

9. ganeshie8 Group Title

not getting any ideas :S

10. mukushla Group Title

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

11. ganeshie8 Group Title

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

12. mukushla Group Title

no this is not about factoring after this

13. ganeshie8 Group Title

left side factors are co-prime

14. mukushla Group Title

ahh thats the point gane

15. ganeshie8 Group Title

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

16. ganeshie8 Group Title

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

17. ganeshie8 Group Title

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

18. mukushla Group Title

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

19. ganeshie8 Group Title

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

20. ganeshie8 Group Title

il grab som coffee brb :)

21. mukushla Group Title

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$

22. mukushla Group Title

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

23. mukushla Group Title

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

24. ganeshie8 Group Title

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 ?

25. mukushla Group Title

gane im wrong

26. mukushla Group Title

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

27. mukushla Group Title

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

28. mukushla Group Title

@ganeshie8

29. mukushla Group Title

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$$

30. mukushla Group Title

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?

31. mukushla Group Title

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

32. mukushla Group Title

$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$$

33. experimentX Group Title

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

34. mukushla Group Title

these values makes that expression integer ??

35. experimentX Group Title

the above expression is a perfect square.

36. experimentX Group Title

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

37. mukushla Group Title

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

38. experimentX Group Title

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

39. experimentX Group Title

I'm not good with modular arithmetic

40. mukushla Group Title

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?

41. experimentX Group Title

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.

42. mukushla Group Title

what is integerpart function in matlab?

43. experimentX Group Title
44. mukushla Group Title

45. experimentX Group Title

Damn

46. experimentX Group Title

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

47. experimentX Group Title
48. mukushla Group Title

i got it

49. mukushla Group Title

i think MATLAB cuts the fractional part for big numbers

50. experimentX Group Title

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

51. mukushla Group Title

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

52. experimentX Group Title

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

53. mukushla Group Title

lol...my windows calc

54. experimentX Group Title

looks like matlab is unable to handle it.

55. mukushla Group Title

yeah :/

56. experimentX Group Title

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

57. mukushla Group Title

:D

58. ganeshie8 Group Title

$$(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 ?

59. mukushla Group Title

$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

60. ganeshie8 Group Title

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

61. ganeshie8 Group Title

and second case is obvious !!

62. mukushla Group Title