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

- ganeshie8

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

- Stacey Warren - Expert brainly.com

Hey! We 've verified this expert answer for you, click below to unlock the details :)

- katieb

I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!

- dan815

what is the GCD algorithm

- ganeshie8

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

- ganeshie8

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

Looking for something else?

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

## More answers

- ganeshie8

i have been messing with that
but no success..

- dan815

1/2, 2, 1/2, 1

- dan815

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

- ganeshie8

|dw:1440466619213:dw|

- dan815

i think showing this pattern recurring is better

- dan815

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

- dan815

let p=2n+1

- dan815

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

- ganeshie8

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

- dan815

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

- dan815

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

- dan815

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

- ganeshie8

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

- dan815

right

- dan815

oops i mean (2n-1)-1

- dan815

|dw:1440467089588:dw|

- dan815

or 1

- dan815

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

- ganeshie8

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

- dan815

ooo okay that looks neater

- dan815

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

- ganeshie8

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

- dan815

yep what u solved for already shows

- dan815

(2,n-1)

- dan815

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

- ganeshie8

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

- dan815

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

- dan815

4k+3*

- dan815

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

- ganeshie8

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

- dan815

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

- dan815

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

- dan815

feels almost as complex as knowing the next prime number itself

- ganeshie8

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

- dan815

yeah

- dan815

but u dont know if its a 1 or a 2

- dan815

it would be interesting if it was like always alternating perfectly

- dan815

i am pretty sure its quite random, just like primes

- ganeshie8

ohk you're thinking of sorting them..

- dan815

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

- ganeshie8

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, ...}

- ganeshie8

|dw:1440468566168:dw|

- dan815

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

- dan815

the mysteriess

- dan815

lol

- ganeshie8

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}\}\)

- dan815

oh true

- ganeshie8

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

- ganeshie8

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.

- dan815

oh cool

- Empty

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

- Empty

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?

- ganeshie8

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

- dan815

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

- Empty

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

- Empty

Might be time to make some programs :P

- dan815

we should consider log sets

- Empty

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

- dan815

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

- dan815

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

- dan815

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

- dan815

difference*

- dan815

e,pi,phi lets gooo lol

- dan815

then e*pi*phi

- ganeshie8

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

- ganeshie8

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

- dan815

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

- dan815

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

- ganeshie8

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

- dan815

yeah

- dan815

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"

- ganeshie8

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

- dan815

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

- dan815

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

- dan815

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

- dan815

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

- ganeshie8

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

- dan815

and how the variation changes can be shown with some combinatorics

- dan815

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

- dan815

and u end up with the central limit theorem i think

- dan815

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

- dan815

|dw:1440471255706:dw|

- Empty

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

- Empty

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.

- ganeshie8

```
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 ?

- Empty

That's one way to look at it, yeah

- Empty

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

- ganeshie8

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

- Empty

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

- Empty

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

- Empty

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

- ganeshie8

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

- Empty

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

- Empty

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

- ganeshie8

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

- ganeshie8

yes it has to do with prime number thm..

- Empty

Oh right of course! XD

- Empty

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

- Empty

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!

- Empty

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

- Empty

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

- Empty

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

- ganeshie8

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

- ganeshie8

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

- Empty

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.

- Empty

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

- ganeshie8

```
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 :)

Looking for something else?

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