A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

ganeshie8

  • one year ago

\(\gcd((p+1)/2,~p-1) = ?\) \(p\) is an odd prime

  • This Question is Closed
  1. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    what is the GCD algorithm

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

    wolfram says the answer is always either 2 or 1 http://www.wolframalpha.com/input/?i=Table%5Bgcd%28%28p%2B1%29%2F2%2C+p-1%29%2C+%7Bp%2C3%2C13%7D%5D

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

    gcd(a, b) = gcd(a-b, b) = gcd(a, b-a)

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

    i have been messing with that but no success..

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

    1/2, 2, 1/2, 1

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

    okay (p+1)/2 = p/2 + 1/2, and p-1 = 2*(p/2 - 1/2)

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

    |dw:1440466619213:dw|

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

    i think showing this pattern recurring is better

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

    we can show that all oodds will be 1 and 2 repeating

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

    let p=2n+1

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

    GCD((2n+1)+1)/2,2n-1)

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

    \(p\) is given as an odd prime so..

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

    if we show this happens to all odd numbers then we can atleast say it happens to all odd primes, the patternn of the 1s and 2s might be random

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

    GCD((2n+1)+1)/2,2n-1) = 1 or 2 in fact we can evn do 1 step better by changing n=2k and 2k+1

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

    to show every 2nd add is 2 and every 1st odd is 1

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

    Oh! for odd numbers also it is giving 1 or 2 didn't notice before.. interesting..

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

    right

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

    oops i mean (2n-1)-1

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

    |dw:1440467089588:dw|

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

    or 1

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

    lets see every 4th odd is 1 when odd of form 4k+1 when odd of form 4k+3 we have 2s

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

    Nice! it works perfectly! GCD((2n+1)+1)/2,2n-1) = GCD(n+1, 2n) = GCD(n+1, n-1) = GCD(2, n-1)

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

    ooo okay that looks neater

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

    when odd of form 4k+1 we have 1s as GCD when odd of form 4k+3 we have 2s

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

    if p = 4k+1, then (p+1)/2 = (4k+1 + 1)/2 = 2k+1 clearly 2 doesn't divide 2k+1, so gcd = 1

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

    yep what u solved for already shows

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

    (2,n-1)

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

    every 2nd n has 2, every 1st n has 1 gcd

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

    if p = 4k+3, then (p+1)/2 = (4k+3 + 1)/2 = 2k+2 = 2(k+1) so gcd = 2 this form looks better to me as it says when exactly is gcd 1 or 2

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

    and since ur looking at the numers of form 2n+1 that shows 4k+1 and 4k+4 have 1 and 2 GCD respectively

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

    4k+3*

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

    http://prntscr.com/88jluw this line u did here pretty much is 100% completed work

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

    \[\gcd((p+1)/2,~p-1) = \left\{\begin{array}{}1&:&p\equiv 1\pmod{4}\\2&:&p\equiv 3\pmod{4}\\ \end{array}\right.\]

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

    okay now to figure out something how the order of 1s and 2s follow for primes that will be something

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

    thats just like asking if there are an even number of oodds or an odd number of odds between each prime number

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

    feels almost as complex as knowing the next prime number itself

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

    the same applies to primes as well right.. if it works for odd numbers, then it works for odd primes too...

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

    yeah

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

    but u dont know if its a 1 or a 2

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

    it would be interesting if it was like always alternating perfectly

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

    i am pretty sure its quite random, just like primes

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

    ohk you're thinking of sorting them..

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

    it would be interesting if u could prove something based on density of primes and stuff

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

    yea the primes don't alternate between : {4k+1, 4k+3, 4k+1, 4k+3,...} so there should not exist any pattern like : {1, 2, 1, 2, ...}

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

    |dw:1440468566168:dw|

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

    ya im saying it would be interseting if we can prove something abot the 1s and 2s if like there should be more 2s or more 1s, or if its truly random or some pattern exist and such

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

    the mysteriess

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

    lol

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

    so basically you're asking, which set is bigger : \(\{p:\text{p is an odd prime of form 4k+1}\}\) or \(\{p:\text{p is an odd prime of form 4k+3}\}\)

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

    oh true

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

    they both are infinite sets and have same cardinality, but it might look intresting to see the density graph for each of them..

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

    wow! you're not the first person to observe that, this looks interesting In number theory, Chebyshev's bias is the phenomenon that most of the time, there are more primes of the form 4k + 3 than of the form 4k + 1, up to the same limit. This phenomenon was first observed by Chebyshev in 1853.

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

    oh cool

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

    I wonder if there are more primes of the form 6n+1 or 6n+5 while we're at it.

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

    Also I wonder if we can help sort the 4n+1 and 4n+3 primes by acknowledging they are really both 2n+1 primes. So what I mean is this is part of a larger tree that will sort further: 8n+1, 8n+3, 8n+5, 8n+7 So we can see that we are further cutting apart 4n+1 --> 8n+1, 8n+5 4n+3 --> 8n+3, 8n+7 If that makes sense, since this gives us a way to try to understand them better?

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

    just completed reading first page of this http://www.jstor.org/stable/27641834?&seq=1#page_scan_tab_contents looks interesting.. i wish i had access to the full doc

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

    its kind of cool the difference looks like its increasing constantly but around some binomial distribution increase

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

    Fascinating, the difference between them in the "race" isn't very far all the way up to 100,000 cool

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

    Might be time to make some programs :P

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

    we should consider log sets

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

    Fun fact: All Mersenne primes are of the form 4n+3

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

    like instead of considering sets of 10,20,30 how about sets of length approximately e and e^2 , e^3

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

    i always wonder how these numbers that are discovered more purely hold up against these random things

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

    it could result in a linear growth of the different between team 1 and team 3 primes

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

    difference*

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

    e,pi,phi lets gooo lol

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

    then e*pi*phi

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

    it seems the prime number theorem also works independently for each of the forms : 1 mod4 and 3 mod4 so the asymptotic behavior is same for each of them https://gyazo.com/3a056dd0d8a7c6c07dbae6b805c379df

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

    extension of prime number theorem to arithmetic progressions is something beyong my grasp..

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

    u know something knowing someone like chebyshev was the one to discover it, he probably showed something like the difference is getting less and less proportionally and maybe show how the standard deviation could be changing approximately too

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

    i was working on something similiar to this the other day on here, i found out it was something very similar to the central limit theorem

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

    interesting, central limit theorem relates sampling distributions to sample distribution right ?

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

    yeah

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

    it comes in trying to answer this question " if u notice some standard deviation for n samples, what standard deviation will you notice for k*n samples"

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

    the more samples u take, the more steep the normal curve of the distribution of samples becomes ?

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

    i didnt really finish it lol i just got some integral expression

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

    http://prntscr.com/88k0av http://prntscr.com/88k0hm i got upto there and forgot about it xD

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

    but i think the steps i took there is pretty logical its how someone naive would try to approach it

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

    like if u flip 2 coins heads and tails, you will expect quite a bit of variation often

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

    Ahh okay, i remember it from some highschool level statistics course.. i don't think they took time to prove CLT but i remember doing many problems that use CLT. .

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

    and how the variation changes can be shown with some combinatorics

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

    by looking at hte prob of 2 heads and so on, then u can do the same thing with 10 coins and see how the prob changes then you try to relate the 2 prbabilities as a function of the grown in sample space

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

    and u end up with the central limit theorem i think

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

    u wud expect bigger fluctuations around the mean for smaller sample spaces because theres higher probabilties for the values around the mean there

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

    |dw:1440471255706:dw|

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

    ``` 8n+1 counter = 2384 8n+3 counter = 2409 8n+5 counter = 2399 8n+7 counter = 2399 ``` So here's the output of looking at the number of primes up to 100,000 similar to how they did it here where @ganeshie8 showed us earlier http://www.jstor.org/stable/27641834?&seq=1#page_scan_tab_contents

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

    You can see that 8n+1 counter and 8n+3 counter's total will add up to 4783 which is the value of 4n+1 like we'd expect, listed on his site. Just thought it'd be interesting to show, I can put my Java code if you're curious.

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

    ``` 4n+1 --> 8n+1, 8n+5 4n+3 --> 8n+3, 8n+7 ``` kai just a basic question, you're splitting 4n+1 into two subtrees by considering n=even/odd right ?

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

    That's one way to look at it, yeah

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

    Here's my code, check it out and play around: https://repl.it/BD31/1

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

    it is very interesting, how evenly they distribute themselves among 16a+b progressions!

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

    Yeah I'm not sure if this is to be expected or not for them to be so uniformly distributed like this, very interesting

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

    Also if you see any ways to make my code faster, I think my prime checking method is kind of poorly made but it gets the job done at least haha

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

    Uh oh I think I made a tiny bug left in there

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

    i came across this witty limit just some time back \[\lim\limits_{n\to\infty} \dfrac{n\log n}{p_n} = 1\] \(p_n\) is nth prime not gonna share the proof as i don't wanto spoil the fun incase if you haven't seen it before..

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

    ``` 16n+1 counter = 1188 16n+3 counter = 1208 16n+5 counter = 1200 16n+7 counter = 1200 16n+9 counter = 1196 16n+11 counter = 1201 16n+13 counter = 1199 16n+15 counter = 1199 ``` That looks better I think

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

    Oh that looks fun like a modification on the prime number theorem thingy maybe? I'll try playing around.

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

    haha all i can think of is putting sqrt for that n ``` for (int i = 2; i < Math.sqrt(n); i++) ```

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

    yes it has to do with prime number thm..

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

    Oh right of course! XD

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

    Ahhh also it looks like \(p_n\)~ n log n

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

    Improving the code slightly https://repl.it/BD31/2 I got some fun results up to a million ``` max = 1000000 16n+1 counter = 9841 16n+3 counter = 9838 16n+5 counter = 9816 16n+7 counter = 9832 16n+9 counter = 9878 16n+11 counter = 9815 16n+13 counter = 9807 16n+15 counter = 9837 max = 1000000 4n+1 counter = 39342 4n+3 counter = 39322 ``` Interesting how close it stays, it is still only 20 higher, very peculiar!

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

    I think I'll start making some methods to calculate the standard deviation and mean and things like that

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

    Although maybe have something like an ordered dependent mean so we can see when one surpasses the other or look at the stability of these things with each new number added

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

    Or any other kind of fun ideas we should try looking at?

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

    sometimes i use lookup tables for prime numbers instead of generating them everytime http://primes.utm.edu/lists/small/millions/ just to make it run faster..

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

    i never had to wry about primes beyond 50 million using code before.. i can wget them and upload the file in JSON format if you want..

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

    I think I can play with them, but I think before I worry about optimizing my code to look at some 50 million crazy primes I think playing around and generating the only 100,000 primes every time doesn't really slow me down too much to look at stufff.

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

    I guess what I'm saying is I just wanna see if we can find anything cool, and if we think it's worth looking at then we can look past the small stuff and see if this extends to the millions of primes or whatever. Right now I'm not sure what to think about all this so I don't want to put too much effort into something I might not use tomorrow XD

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

    ``` for (int i = 3; i < Math.sqrt(n); i += 2) ``` this returns true for numbers of form \(p^2\) too.. need an equality there when i ran ur program, it didnt change the counter for 4n+3 for obvious reasons :)

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

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

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.