Does $N(mn)|N(m)N(n)$ for $gcd(m,n)=1$? (Fibonacci Sequence)
$begingroup$
Consider Fibonacci Sequence Mod m, n and mn. And let N(m) be the period of Fibonacci Sequence mod m. For several $m,n$ I tried to compare $N(mn)$ with $N(m)N(n)$. It looks that there is no specific pattern, but for $gcd(m,n)=1$ it looks $N(mn)|N(m)N(n)$. Could you write some hint, I don't know how to start proving if it is true?
number-theory divisibility fibonacci-numbers
edited Dec 4 '18 at 14:23
Chickenmancer
3,314724
asked Dec 4 '18 at 14:13
72D72D
512117
$endgroup$
add a comment |
$begingroup$
Consider Fibonacci Sequence Mod m, n and mn. And let N(m) be the period of Fibonacci Sequence mod m. For several $m,n$ I tried to compare $N(mn)$ with $N(m)N(n)$. It looks that there is no specific pattern, but for $gcd(m,n)=1$ it looks $N(mn)|N(m)N(n)$. Could you write some hint, I don't know how to start proving if it is true?
number-theory divisibility fibonacci-numbers
edited Dec 4 '18 at 14:23
Chickenmancer
3,314724
asked Dec 4 '18 at 14:13
72D72D
512117
$endgroup$
add a comment |
$begingroup$
Consider Fibonacci Sequence Mod m, n and mn. And let N(m) be the period of Fibonacci Sequence mod m. For several $m,n$ I tried to compare $N(mn)$ with $N(m)N(n)$. It looks that there is no specific pattern, but for $gcd(m,n)=1$ it looks $N(mn)|N(m)N(n)$. Could you write some hint, I don't know how to start proving if it is true?
number-theory divisibility fibonacci-numbers
edited Dec 4 '18 at 14:23
Chickenmancer
3,314724
asked Dec 4 '18 at 14:13
72D72D
512117
$endgroup$
Consider Fibonacci Sequence Mod m, n and mn. And let N(m) be the period of Fibonacci Sequence mod m. For several $m,n$ I tried to compare $N(mn)$ with $N(m)N(n)$. It looks that there is no specific pattern, but for $gcd(m,n)=1$ it looks $N(mn)|N(m)N(n)$. Could you write some hint, I don't know how to start proving if it is true?
number-theory divisibility fibonacci-numbers
number-theory divisibility fibonacci-numbers
edited Dec 4 '18 at 14:23
Chickenmancer
3,314724
asked Dec 4 '18 at 14:13
72D72D
512117
edited Dec 4 '18 at 14:23
Chickenmancer
3,314724
asked Dec 4 '18 at 14:13
72D72D
512117
edited Dec 4 '18 at 14:23
Chickenmancer
3,314724
edited Dec 4 '18 at 14:23
Chickenmancer
3,314724
edited Dec 4 '18 at 14:23
Chickenmancer
3,314724
3,314724
asked Dec 4 '18 at 14:13
72D72D
512117
asked Dec 4 '18 at 14:13
72D72D
512117
asked Dec 4 '18 at 14:13
72D72D
512117
512117
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Suppose $m$ and $n$ are coprime. Since $F_{j+N(m)N(n)} equiv F_j mod m$
and $F_{j+N(m)N(n)} equiv F_j mod n$ we have $F_{j+N(m)N(n)} equiv F_j mod mn$.
Thus $N(mn) mid N(m) N(n)$.
There's nothing special about Fibonacci numbers here: this would work for any sequence that is periodic mod $m$ and mod $n$.
answered Dec 4 '18 at 14:22
Robert IsraelRobert Israel
325k23214468
$endgroup$
1
$begingroup$
Could you explain in a little more detail? In particular, why are the statements involving mod true?
$endgroup$
– Chickenmancer
Dec 4 '18 at 14:24
$begingroup$
By definition, if a sequence $a_j$ is periodic mod $m$ with period $p$, $a_{j+kp} equiv a_j mod m$ for any integer $k$.
$endgroup$
– Robert Israel
Dec 4 '18 at 14:26
add a comment |
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%2f3025630%2fdoes-nmnnmnn-for-gcdm-n-1-fibonacci-sequence%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Suppose $m$ and $n$ are coprime. Since $F_{j+N(m)N(n)} equiv F_j mod m$
and $F_{j+N(m)N(n)} equiv F_j mod n$ we have $F_{j+N(m)N(n)} equiv F_j mod mn$.
Thus $N(mn) mid N(m) N(n)$.
There's nothing special about Fibonacci numbers here: this would work for any sequence that is periodic mod $m$ and mod $n$.
answered Dec 4 '18 at 14:22
Robert IsraelRobert Israel
325k23214468
$endgroup$
1
$begingroup$
Could you explain in a little more detail? In particular, why are the statements involving mod true?
$endgroup$
– Chickenmancer
Dec 4 '18 at 14:24
$begingroup$
By definition, if a sequence $a_j$ is periodic mod $m$ with period $p$, $a_{j+kp} equiv a_j mod m$ for any integer $k$.
$endgroup$
– Robert Israel
Dec 4 '18 at 14:26
add a comment |
$begingroup$
Suppose $m$ and $n$ are coprime. Since $F_{j+N(m)N(n)} equiv F_j mod m$
and $F_{j+N(m)N(n)} equiv F_j mod n$ we have $F_{j+N(m)N(n)} equiv F_j mod mn$.
Thus $N(mn) mid N(m) N(n)$.
There's nothing special about Fibonacci numbers here: this would work for any sequence that is periodic mod $m$ and mod $n$.
answered Dec 4 '18 at 14:22
Robert IsraelRobert Israel
325k23214468
$endgroup$
1
$begingroup$
Could you explain in a little more detail? In particular, why are the statements involving mod true?
$endgroup$
– Chickenmancer
Dec 4 '18 at 14:24
$begingroup$
By definition, if a sequence $a_j$ is periodic mod $m$ with period $p$, $a_{j+kp} equiv a_j mod m$ for any integer $k$.
$endgroup$
– Robert Israel
Dec 4 '18 at 14:26
add a comment |
$begingroup$
Suppose $m$ and $n$ are coprime. Since $F_{j+N(m)N(n)} equiv F_j mod m$
and $F_{j+N(m)N(n)} equiv F_j mod n$ we have $F_{j+N(m)N(n)} equiv F_j mod mn$.
Thus $N(mn) mid N(m) N(n)$.
There's nothing special about Fibonacci numbers here: this would work for any sequence that is periodic mod $m$ and mod $n$.
answered Dec 4 '18 at 14:22
Robert IsraelRobert Israel
325k23214468
$endgroup$
Suppose $m$ and $n$ are coprime. Since $F_{j+N(m)N(n)} equiv F_j mod m$
and $F_{j+N(m)N(n)} equiv F_j mod n$ we have $F_{j+N(m)N(n)} equiv F_j mod mn$.
Thus $N(mn) mid N(m) N(n)$.
There's nothing special about Fibonacci numbers here: this would work for any sequence that is periodic mod $m$ and mod $n$.
answered Dec 4 '18 at 14:22
Robert IsraelRobert Israel
325k23214468
edited Dec 4 '18 at 14:24
answered Dec 4 '18 at 14:22
Robert IsraelRobert Israel
325k23214468
answered Dec 4 '18 at 14:22
Robert IsraelRobert Israel
325k23214468
answered Dec 4 '18 at 14:22
Robert IsraelRobert Israel
325k23214468
325k23214468
1
$begingroup$
Could you explain in a little more detail? In particular, why are the statements involving mod true?
$endgroup$
– Chickenmancer
Dec 4 '18 at 14:24
$begingroup$
By definition, if a sequence $a_j$ is periodic mod $m$ with period $p$, $a_{j+kp} equiv a_j mod m$ for any integer $k$.
$endgroup$
– Robert Israel
Dec 4 '18 at 14:26
add a comment |
1
$begingroup$
Could you explain in a little more detail? In particular, why are the statements involving mod true?
$endgroup$
– Chickenmancer
Dec 4 '18 at 14:24
$begingroup$
By definition, if a sequence $a_j$ is periodic mod $m$ with period $p$, $a_{j+kp} equiv a_j mod m$ for any integer $k$.
$endgroup$
– Robert Israel
Dec 4 '18 at 14:26
1
1
$begingroup$
Could you explain in a little more detail? In particular, why are the statements involving mod true?
$endgroup$
– Chickenmancer
Dec 4 '18 at 14:24
$begingroup$
Could you explain in a little more detail? In particular, why are the statements involving mod true?
$endgroup$
– Chickenmancer
Dec 4 '18 at 14:24
$begingroup$
By definition, if a sequence $a_j$ is periodic mod $m$ with period $p$, $a_{j+kp} equiv a_j mod m$ for any integer $k$.
$endgroup$
– Robert Israel
Dec 4 '18 at 14:26
$begingroup$
By definition, if a sequence $a_j$ is periodic mod $m$ with period $p$, $a_{j+kp} equiv a_j mod m$ for any integer $k$.
$endgroup$
– Robert Israel
Dec 4 '18 at 14:26
add a comment |
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.
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%2f3025630%2fdoes-nmnnmnn-for-gcdm-n-1-fibonacci-sequence%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
