parity of period of continued fraction of square root of prime number $p$
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 '18 at 11:49
amWhy
192k28224439
asked Dec 5 '16 at 10:34
lmatz
163
add a comment |
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 '18 at 11:49
amWhy
192k28224439
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 '18 at 21:03
add a comment |
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 '18 at 11:49
amWhy
192k28224439
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 '18 at 11:49
amWhy
192k28224439
asked Dec 5 '16 at 10:34
lmatz
163
edited Nov 21 '18 at 11:49
amWhy
192k28224439
asked Dec 5 '16 at 10:34
lmatz
163
edited Nov 21 '18 at 11:49
amWhy
192k28224439
edited Nov 21 '18 at 11:49
amWhy
192k28224439
edited Nov 21 '18 at 11:49
amWhy
192k28224439
192k28224439
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 '18 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 '18 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 '18 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 '18 at 21:03
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
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 '18 at 21:03