parity of period of continued fraction of square root of prime number $p$
up vote
3
down vote
favorite
It is known that the period of continued fraction of a prime $sqrt p$ is odd if and only if $p equiv 1 pmod 4$. So when $p equiv 3 pmod 4$, the period is even.
But how do I prove the period of continued fraction of $sqrt p$ where $p$ $equiv 3 pmod 8$ is $2n$ ($n$ is odd) while the period of continued fraction of $sqrt p$ where $p$ $equiv 7 pmod 8$ is $2n$ ($n$ is even)?
I tried some examples and find that $x^2-pcdot y^2=2(-1)^n$ appears in the half of the period $- 1$ where $x$ and $y$ are its convergent, for instance continued fraction of $sqrt p$ is $[a_0 ; a_1,a_2,cdotcdotcdot,a_n]$, then $p_{frac n 2 -1}$ and $q_{frac n 2 -1}$ satisfies the equation $x^2-pcdot y^2=2(-1)^n$ where $x=p_{frac n 2 -1}$ and $y=q_{frac n 2-1}$.
I recall that Legendre symbol $left(displaystyle frac {~2~}{~p~}right)$ is $1$ when $p equiv 7 pmod 8$ while $left(displaystyle frac {~2~}{~p~}right)$ is $-1$ when $p equiv 3 pmod 8$, but cannot figure it out how I can relate them.
Is this the right way to approach?
number-theory prime-numbers continued-fractions
edited Nov 21 at 11:49
amWhy
191k27223438
asked Dec 5 '16 at 10:34
lmatz
163
add a comment |
up vote
3
down vote
favorite
It is known that the period of continued fraction of a prime $sqrt p$ is odd if and only if $p equiv 1 pmod 4$. So when $p equiv 3 pmod 4$, the period is even.
But how do I prove the period of continued fraction of $sqrt p$ where $p$ $equiv 3 pmod 8$ is $2n$ ($n$ is odd) while the period of continued fraction of $sqrt p$ where $p$ $equiv 7 pmod 8$ is $2n$ ($n$ is even)?
I tried some examples and find that $x^2-pcdot y^2=2(-1)^n$ appears in the half of the period $- 1$ where $x$ and $y$ are its convergent, for instance continued fraction of $sqrt p$ is $[a_0 ; a_1,a_2,cdotcdotcdot,a_n]$, then $p_{frac n 2 -1}$ and $q_{frac n 2 -1}$ satisfies the equation $x^2-pcdot y^2=2(-1)^n$ where $x=p_{frac n 2 -1}$ and $y=q_{frac n 2-1}$.
I recall that Legendre symbol $left(displaystyle frac {~2~}{~p~}right)$ is $1$ when $p equiv 7 pmod 8$ while $left(displaystyle frac {~2~}{~p~}right)$ is $-1$ when $p equiv 3 pmod 8$, but cannot figure it out how I can relate them.
Is this the right way to approach?
number-theory prime-numbers continued-fractions
edited Nov 21 at 11:49
amWhy
191k27223438
asked Dec 5 '16 at 10:34
lmatz
163
1
Can you give any reference for the fact you gave in first line?
– Seewoo Lee
Feb 9 '17 at 15:20
@See-WooLee: It looks like a proof of the hard direction (if p is 1 mod 4, then the period is odd) follows from a theorem of Rippon and Taylor in mathstat.dal.ca/FQ/Papers1/42-2/quartrippon02_2004.pdf; they also reference that the result appears in an earlier paper in German by Perron from the 50s.
– sibilant
Feb 27 at 21:03
add a comment |
up vote
3
down vote
favorite
up vote
3
down vote
favorite
It is known that the period of continued fraction of a prime $sqrt p$ is odd if and only if $p equiv 1 pmod 4$. So when $p equiv 3 pmod 4$, the period is even.
But how do I prove the period of continued fraction of $sqrt p$ where $p$ $equiv 3 pmod 8$ is $2n$ ($n$ is odd) while the period of continued fraction of $sqrt p$ where $p$ $equiv 7 pmod 8$ is $2n$ ($n$ is even)?
I tried some examples and find that $x^2-pcdot y^2=2(-1)^n$ appears in the half of the period $- 1$ where $x$ and $y$ are its convergent, for instance continued fraction of $sqrt p$ is $[a_0 ; a_1,a_2,cdotcdotcdot,a_n]$, then $p_{frac n 2 -1}$ and $q_{frac n 2 -1}$ satisfies the equation $x^2-pcdot y^2=2(-1)^n$ where $x=p_{frac n 2 -1}$ and $y=q_{frac n 2-1}$.
I recall that Legendre symbol $left(displaystyle frac {~2~}{~p~}right)$ is $1$ when $p equiv 7 pmod 8$ while $left(displaystyle frac {~2~}{~p~}right)$ is $-1$ when $p equiv 3 pmod 8$, but cannot figure it out how I can relate them.
Is this the right way to approach?
number-theory prime-numbers continued-fractions
edited Nov 21 at 11:49
amWhy
191k27223438
asked Dec 5 '16 at 10:34
lmatz
163
It is known that the period of continued fraction of a prime $sqrt p$ is odd if and only if $p equiv 1 pmod 4$. So when $p equiv 3 pmod 4$, the period is even.
But how do I prove the period of continued fraction of $sqrt p$ where $p$ $equiv 3 pmod 8$ is $2n$ ($n$ is odd) while the period of continued fraction of $sqrt p$ where $p$ $equiv 7 pmod 8$ is $2n$ ($n$ is even)?
I tried some examples and find that $x^2-pcdot y^2=2(-1)^n$ appears in the half of the period $- 1$ where $x$ and $y$ are its convergent, for instance continued fraction of $sqrt p$ is $[a_0 ; a_1,a_2,cdotcdotcdot,a_n]$, then $p_{frac n 2 -1}$ and $q_{frac n 2 -1}$ satisfies the equation $x^2-pcdot y^2=2(-1)^n$ where $x=p_{frac n 2 -1}$ and $y=q_{frac n 2-1}$.
I recall that Legendre symbol $left(displaystyle frac {~2~}{~p~}right)$ is $1$ when $p equiv 7 pmod 8$ while $left(displaystyle frac {~2~}{~p~}right)$ is $-1$ when $p equiv 3 pmod 8$, but cannot figure it out how I can relate them.
Is this the right way to approach?
number-theory prime-numbers continued-fractions
number-theory prime-numbers continued-fractions
edited Nov 21 at 11:49
amWhy
191k27223438
asked Dec 5 '16 at 10:34
lmatz
163
edited Nov 21 at 11:49
amWhy
191k27223438
asked Dec 5 '16 at 10:34
lmatz
163
edited Nov 21 at 11:49
amWhy
191k27223438
edited Nov 21 at 11:49
amWhy
191k27223438
edited Nov 21 at 11:49
amWhy
191k27223438
191k27223438
asked Dec 5 '16 at 10:34
lmatz
163
asked Dec 5 '16 at 10:34
lmatz
163
asked Dec 5 '16 at 10:34
lmatz
163
163
1
Can you give any reference for the fact you gave in first line?
– Seewoo Lee
Feb 9 '17 at 15:20
@See-WooLee: It looks like a proof of the hard direction (if p is 1 mod 4, then the period is odd) follows from a theorem of Rippon and Taylor in mathstat.dal.ca/FQ/Papers1/42-2/quartrippon02_2004.pdf; they also reference that the result appears in an earlier paper in German by Perron from the 50s.
– sibilant
Feb 27 at 21:03
add a comment |
1
Can you give any reference for the fact you gave in first line?
– Seewoo Lee
Feb 9 '17 at 15:20
@See-WooLee: It looks like a proof of the hard direction (if p is 1 mod 4, then the period is odd) follows from a theorem of Rippon and Taylor in mathstat.dal.ca/FQ/Papers1/42-2/quartrippon02_2004.pdf; they also reference that the result appears in an earlier paper in German by Perron from the 50s.
– sibilant
Feb 27 at 21:03
1
1
Can you give any reference for the fact you gave in first line?
– Seewoo Lee
Feb 9 '17 at 15:20
Can you give any reference for the fact you gave in first line?
– Seewoo Lee
Feb 9 '17 at 15:20
@See-WooLee: It looks like a proof of the hard direction (if p is 1 mod 4, then the period is odd) follows from a theorem of Rippon and Taylor in mathstat.dal.ca/FQ/Papers1/42-2/quartrippon02_2004.pdf; they also reference that the result appears in an earlier paper in German by Perron from the 50s.
– sibilant
Feb 27 at 21:03
@See-WooLee: It looks like a proof of the hard direction (if p is 1 mod 4, then the period is odd) follows from a theorem of Rippon and Taylor in mathstat.dal.ca/FQ/Papers1/42-2/quartrippon02_2004.pdf; they also reference that the result appears in an earlier paper in German by Perron from the 50s.
– sibilant
Feb 27 at 21:03
add a comment |
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2044705%2fparity-of-period-of-continued-fraction-of-square-root-of-prime-number-p%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
Can you give any reference for the fact you gave in first line?
– Seewoo Lee
Feb 9 '17 at 15:20
@See-WooLee: It looks like a proof of the hard direction (if p is 1 mod 4, then the period is odd) follows from a theorem of Rippon and Taylor in mathstat.dal.ca/FQ/Papers1/42-2/quartrippon02_2004.pdf; they also reference that the result appears in an earlier paper in German by Perron from the 50s.
– sibilant
Feb 27 at 21:03