Modular inverse of a fraction vs just the numerator
$begingroup$
I found an unintuitive result, and I'd like help understanding why this is the case. I was experimenting with the sequence given by $a_n = 1 + frac{1}{a_{n-1}}, a_1 = 1$. This sequence goes like $1, 2, frac{3}{2}, frac{5}{3}, frac{8}{5}, frac{13}{8}...$ and produces a Fibonacci-esque relation between the numerators and denominators.
Now, I tried writing the similar sequence $b_n = 1 + (b_{n-1})^{-1} mod 13$, where the $^{-1}$ denotes the modular inverse. $b_1 = 1$ as well, so the sequence goes $1, 1 + 1 = 2, 1 + 7 = 8, 1 + 5 = 6, 1 + 11 = 12, 1 + 12 = 0$.
If you compare the two sequences, $b_n$ hits 0 at the same time the numerator of $a_n$ hits 13, which is 0 mod 13. My question is, why does this happen? The intuitive result in my mind is that if $b_n = 0$ and $a_n = frac{p}{q}$, then the conclusion wouldn't be that the numerator of $p$ is divisible by 13, but rather that $p * (q)^{-1}$ would be divisible by 13, where $q^{-1}$ is the modular inverse of $q$ mod 13, as you would convert the whole fraction to mod 13.
So anyway, my question is, is there an intuitive way of understanding why just the numerator is the one that will be divisible mod 13, rather than the entire fraction $a_n$?
modular-arithmetic
asked Dec 24 '18 at 21:34
johnrolfejohnrolfe
91
$endgroup$
add a comment |
$begingroup$
I found an unintuitive result, and I'd like help understanding why this is the case. I was experimenting with the sequence given by $a_n = 1 + frac{1}{a_{n-1}}, a_1 = 1$. This sequence goes like $1, 2, frac{3}{2}, frac{5}{3}, frac{8}{5}, frac{13}{8}...$ and produces a Fibonacci-esque relation between the numerators and denominators.
Now, I tried writing the similar sequence $b_n = 1 + (b_{n-1})^{-1} mod 13$, where the $^{-1}$ denotes the modular inverse. $b_1 = 1$ as well, so the sequence goes $1, 1 + 1 = 2, 1 + 7 = 8, 1 + 5 = 6, 1 + 11 = 12, 1 + 12 = 0$.
If you compare the two sequences, $b_n$ hits 0 at the same time the numerator of $a_n$ hits 13, which is 0 mod 13. My question is, why does this happen? The intuitive result in my mind is that if $b_n = 0$ and $a_n = frac{p}{q}$, then the conclusion wouldn't be that the numerator of $p$ is divisible by 13, but rather that $p * (q)^{-1}$ would be divisible by 13, where $q^{-1}$ is the modular inverse of $q$ mod 13, as you would convert the whole fraction to mod 13.
So anyway, my question is, is there an intuitive way of understanding why just the numerator is the one that will be divisible mod 13, rather than the entire fraction $a_n$?
modular-arithmetic
asked Dec 24 '18 at 21:34
johnrolfejohnrolfe
91
$endgroup$
2
$begingroup$
Not sure why you are stressing $13$. Pretty easy to see that $a_n=frac {F_n}{F_{n-1}}$ since $F_n=F_{n-1}+F_{n-2}implies frac {F_n}{F_{n-1}}=1+frac {F_{n-2}}{F_{n-1}}$ and we can then check initial conditions. Is that what you are after?
$endgroup$
– lulu
Dec 24 '18 at 21:37
$begingroup$
Well, 13 was just an example. Similarly, if we use the sequence $b_n=1+(b_{n−1})^{−1}mod5$, then since $a_4 = frac{5}{2}$, it ends up being that $b_4 = 0 $. Essentially, what I'm doing when creating $b_n$ is just taking the $a_n$ sequence and converting the $frac{1}{a_{n-1}}$ to a modular inverse. The effect of this is that whenever the numerator of $a_k$ is divisible by a prime p, then the sequence $b_n = 1+(b_{n−1})^{−1}$ mod p will have $b_k$ equal to 0. Why is this so? Or at least, why is it the numerator of $a_k$ that is so important?
$endgroup$
– johnrolfe
Dec 24 '18 at 21:43
$begingroup$
Well, until you hit $0's$ in the denominator you can just reduce the rational form modulo the given prime, To stick with your $13$, the multiplicative inverse of $8pmod {13}$ is $5pmod {13}$. Thus where you have $frac n8$ rationally, you'd get $5npmod {13}$. This reasoning works modulo each prime.
$endgroup$
– lulu
Dec 24 '18 at 21:47
$begingroup$
Oh, that makes sense. Thank you for clarifying!
$endgroup$
– johnrolfe
Dec 24 '18 at 21:53
$begingroup$
See here for modular fractions. You are simply reducing the sequence $!bmod n,,$ which is well-defined for all fractions with denominator coprime $,n. $ You'll get the same result whatever order you do the mod reductions, e.g. doing it all rationally then doing one final mod reduction , vs. reducing everything right away (or mix and match) because modular reduction commutes with ring operations plus, times (and said inverses), i.e. it is a ring homomorphism.
$endgroup$
– Bill Dubuque
Dec 24 '18 at 22:48
add a comment |
$begingroup$
I found an unintuitive result, and I'd like help understanding why this is the case. I was experimenting with the sequence given by $a_n = 1 + frac{1}{a_{n-1}}, a_1 = 1$. This sequence goes like $1, 2, frac{3}{2}, frac{5}{3}, frac{8}{5}, frac{13}{8}...$ and produces a Fibonacci-esque relation between the numerators and denominators.
Now, I tried writing the similar sequence $b_n = 1 + (b_{n-1})^{-1} mod 13$, where the $^{-1}$ denotes the modular inverse. $b_1 = 1$ as well, so the sequence goes $1, 1 + 1 = 2, 1 + 7 = 8, 1 + 5 = 6, 1 + 11 = 12, 1 + 12 = 0$.
If you compare the two sequences, $b_n$ hits 0 at the same time the numerator of $a_n$ hits 13, which is 0 mod 13. My question is, why does this happen? The intuitive result in my mind is that if $b_n = 0$ and $a_n = frac{p}{q}$, then the conclusion wouldn't be that the numerator of $p$ is divisible by 13, but rather that $p * (q)^{-1}$ would be divisible by 13, where $q^{-1}$ is the modular inverse of $q$ mod 13, as you would convert the whole fraction to mod 13.
So anyway, my question is, is there an intuitive way of understanding why just the numerator is the one that will be divisible mod 13, rather than the entire fraction $a_n$?
modular-arithmetic
asked Dec 24 '18 at 21:34
johnrolfejohnrolfe
91
$endgroup$
I found an unintuitive result, and I'd like help understanding why this is the case. I was experimenting with the sequence given by $a_n = 1 + frac{1}{a_{n-1}}, a_1 = 1$. This sequence goes like $1, 2, frac{3}{2}, frac{5}{3}, frac{8}{5}, frac{13}{8}...$ and produces a Fibonacci-esque relation between the numerators and denominators.
Now, I tried writing the similar sequence $b_n = 1 + (b_{n-1})^{-1} mod 13$, where the $^{-1}$ denotes the modular inverse. $b_1 = 1$ as well, so the sequence goes $1, 1 + 1 = 2, 1 + 7 = 8, 1 + 5 = 6, 1 + 11 = 12, 1 + 12 = 0$.
If you compare the two sequences, $b_n$ hits 0 at the same time the numerator of $a_n$ hits 13, which is 0 mod 13. My question is, why does this happen? The intuitive result in my mind is that if $b_n = 0$ and $a_n = frac{p}{q}$, then the conclusion wouldn't be that the numerator of $p$ is divisible by 13, but rather that $p * (q)^{-1}$ would be divisible by 13, where $q^{-1}$ is the modular inverse of $q$ mod 13, as you would convert the whole fraction to mod 13.
So anyway, my question is, is there an intuitive way of understanding why just the numerator is the one that will be divisible mod 13, rather than the entire fraction $a_n$?
modular-arithmetic
modular-arithmetic
asked Dec 24 '18 at 21:34
johnrolfejohnrolfe
91
asked Dec 24 '18 at 21:34
johnrolfejohnrolfe
91
asked Dec 24 '18 at 21:34
johnrolfejohnrolfe
91
asked Dec 24 '18 at 21:34
johnrolfejohnrolfe
91
asked Dec 24 '18 at 21:34
johnrolfejohnrolfe
91
91
2
$begingroup$
Not sure why you are stressing $13$. Pretty easy to see that $a_n=frac {F_n}{F_{n-1}}$ since $F_n=F_{n-1}+F_{n-2}implies frac {F_n}{F_{n-1}}=1+frac {F_{n-2}}{F_{n-1}}$ and we can then check initial conditions. Is that what you are after?
$endgroup$
– lulu
Dec 24 '18 at 21:37
$begingroup$
Well, 13 was just an example. Similarly, if we use the sequence $b_n=1+(b_{n−1})^{−1}mod5$, then since $a_4 = frac{5}{2}$, it ends up being that $b_4 = 0 $. Essentially, what I'm doing when creating $b_n$ is just taking the $a_n$ sequence and converting the $frac{1}{a_{n-1}}$ to a modular inverse. The effect of this is that whenever the numerator of $a_k$ is divisible by a prime p, then the sequence $b_n = 1+(b_{n−1})^{−1}$ mod p will have $b_k$ equal to 0. Why is this so? Or at least, why is it the numerator of $a_k$ that is so important?
$endgroup$
– johnrolfe
Dec 24 '18 at 21:43
$begingroup$
Well, until you hit $0's$ in the denominator you can just reduce the rational form modulo the given prime, To stick with your $13$, the multiplicative inverse of $8pmod {13}$ is $5pmod {13}$. Thus where you have $frac n8$ rationally, you'd get $5npmod {13}$. This reasoning works modulo each prime.
$endgroup$
– lulu
Dec 24 '18 at 21:47
$begingroup$
Oh, that makes sense. Thank you for clarifying!
$endgroup$
– johnrolfe
Dec 24 '18 at 21:53
$begingroup$
See here for modular fractions. You are simply reducing the sequence $!bmod n,,$ which is well-defined for all fractions with denominator coprime $,n. $ You'll get the same result whatever order you do the mod reductions, e.g. doing it all rationally then doing one final mod reduction , vs. reducing everything right away (or mix and match) because modular reduction commutes with ring operations plus, times (and said inverses), i.e. it is a ring homomorphism.
$endgroup$
– Bill Dubuque
Dec 24 '18 at 22:48
add a comment |
2
$begingroup$
Not sure why you are stressing $13$. Pretty easy to see that $a_n=frac {F_n}{F_{n-1}}$ since $F_n=F_{n-1}+F_{n-2}implies frac {F_n}{F_{n-1}}=1+frac {F_{n-2}}{F_{n-1}}$ and we can then check initial conditions. Is that what you are after?
$endgroup$
– lulu
Dec 24 '18 at 21:37
$begingroup$
Well, 13 was just an example. Similarly, if we use the sequence $b_n=1+(b_{n−1})^{−1}mod5$, then since $a_4 = frac{5}{2}$, it ends up being that $b_4 = 0 $. Essentially, what I'm doing when creating $b_n$ is just taking the $a_n$ sequence and converting the $frac{1}{a_{n-1}}$ to a modular inverse. The effect of this is that whenever the numerator of $a_k$ is divisible by a prime p, then the sequence $b_n = 1+(b_{n−1})^{−1}$ mod p will have $b_k$ equal to 0. Why is this so? Or at least, why is it the numerator of $a_k$ that is so important?
$endgroup$
– johnrolfe
Dec 24 '18 at 21:43
$begingroup$
Well, until you hit $0's$ in the denominator you can just reduce the rational form modulo the given prime, To stick with your $13$, the multiplicative inverse of $8pmod {13}$ is $5pmod {13}$. Thus where you have $frac n8$ rationally, you'd get $5npmod {13}$. This reasoning works modulo each prime.
$endgroup$
– lulu
Dec 24 '18 at 21:47
$begingroup$
Oh, that makes sense. Thank you for clarifying!
$endgroup$
– johnrolfe
Dec 24 '18 at 21:53
$begingroup$
See here for modular fractions. You are simply reducing the sequence $!bmod n,,$ which is well-defined for all fractions with denominator coprime $,n. $ You'll get the same result whatever order you do the mod reductions, e.g. doing it all rationally then doing one final mod reduction , vs. reducing everything right away (or mix and match) because modular reduction commutes with ring operations plus, times (and said inverses), i.e. it is a ring homomorphism.
$endgroup$
– Bill Dubuque
Dec 24 '18 at 22:48
2
2
$begingroup$
Not sure why you are stressing $13$. Pretty easy to see that $a_n=frac {F_n}{F_{n-1}}$ since $F_n=F_{n-1}+F_{n-2}implies frac {F_n}{F_{n-1}}=1+frac {F_{n-2}}{F_{n-1}}$ and we can then check initial conditions. Is that what you are after?
$endgroup$
– lulu
Dec 24 '18 at 21:37
$begingroup$
Not sure why you are stressing $13$. Pretty easy to see that $a_n=frac {F_n}{F_{n-1}}$ since $F_n=F_{n-1}+F_{n-2}implies frac {F_n}{F_{n-1}}=1+frac {F_{n-2}}{F_{n-1}}$ and we can then check initial conditions. Is that what you are after?
$endgroup$
– lulu
Dec 24 '18 at 21:37
$begingroup$
Well, 13 was just an example. Similarly, if we use the sequence $b_n=1+(b_{n−1})^{−1}mod5$, then since $a_4 = frac{5}{2}$, it ends up being that $b_4 = 0 $. Essentially, what I'm doing when creating $b_n$ is just taking the $a_n$ sequence and converting the $frac{1}{a_{n-1}}$ to a modular inverse. The effect of this is that whenever the numerator of $a_k$ is divisible by a prime p, then the sequence $b_n = 1+(b_{n−1})^{−1}$ mod p will have $b_k$ equal to 0. Why is this so? Or at least, why is it the numerator of $a_k$ that is so important?
$endgroup$
– johnrolfe
Dec 24 '18 at 21:43
$begingroup$
Well, 13 was just an example. Similarly, if we use the sequence $b_n=1+(b_{n−1})^{−1}mod5$, then since $a_4 = frac{5}{2}$, it ends up being that $b_4 = 0 $. Essentially, what I'm doing when creating $b_n$ is just taking the $a_n$ sequence and converting the $frac{1}{a_{n-1}}$ to a modular inverse. The effect of this is that whenever the numerator of $a_k$ is divisible by a prime p, then the sequence $b_n = 1+(b_{n−1})^{−1}$ mod p will have $b_k$ equal to 0. Why is this so? Or at least, why is it the numerator of $a_k$ that is so important?
$endgroup$
– johnrolfe
Dec 24 '18 at 21:43
$begingroup$
Well, until you hit $0's$ in the denominator you can just reduce the rational form modulo the given prime, To stick with your $13$, the multiplicative inverse of $8pmod {13}$ is $5pmod {13}$. Thus where you have $frac n8$ rationally, you'd get $5npmod {13}$. This reasoning works modulo each prime.
$endgroup$
– lulu
Dec 24 '18 at 21:47
$begingroup$
Well, until you hit $0's$ in the denominator you can just reduce the rational form modulo the given prime, To stick with your $13$, the multiplicative inverse of $8pmod {13}$ is $5pmod {13}$. Thus where you have $frac n8$ rationally, you'd get $5npmod {13}$. This reasoning works modulo each prime.
$endgroup$
– lulu
Dec 24 '18 at 21:47
$begingroup$
Oh, that makes sense. Thank you for clarifying!
$endgroup$
– johnrolfe
Dec 24 '18 at 21:53
$begingroup$
Oh, that makes sense. Thank you for clarifying!
$endgroup$
– johnrolfe
Dec 24 '18 at 21:53
$begingroup$
See here for modular fractions. You are simply reducing the sequence $!bmod n,,$ which is well-defined for all fractions with denominator coprime $,n. $ You'll get the same result whatever order you do the mod reductions, e.g. doing it all rationally then doing one final mod reduction , vs. reducing everything right away (or mix and match) because modular reduction commutes with ring operations plus, times (and said inverses), i.e. it is a ring homomorphism.
$endgroup$
– Bill Dubuque
Dec 24 '18 at 22:48
$begingroup$
See here for modular fractions. You are simply reducing the sequence $!bmod n,,$ which is well-defined for all fractions with denominator coprime $,n. $ You'll get the same result whatever order you do the mod reductions, e.g. doing it all rationally then doing one final mod reduction , vs. reducing everything right away (or mix and match) because modular reduction commutes with ring operations plus, times (and said inverses), i.e. it is a ring homomorphism.
$endgroup$
– Bill Dubuque
Dec 24 '18 at 22:48
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%2f3051656%2fmodular-inverse-of-a-fraction-vs-just-the-numerator%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.
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%2f3051656%2fmodular-inverse-of-a-fraction-vs-just-the-numerator%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
2
$begingroup$
Not sure why you are stressing $13$. Pretty easy to see that $a_n=frac {F_n}{F_{n-1}}$ since $F_n=F_{n-1}+F_{n-2}implies frac {F_n}{F_{n-1}}=1+frac {F_{n-2}}{F_{n-1}}$ and we can then check initial conditions. Is that what you are after?
$endgroup$
– lulu
Dec 24 '18 at 21:37
$begingroup$
Well, 13 was just an example. Similarly, if we use the sequence $b_n=1+(b_{n−1})^{−1}mod5$, then since $a_4 = frac{5}{2}$, it ends up being that $b_4 = 0 $. Essentially, what I'm doing when creating $b_n$ is just taking the $a_n$ sequence and converting the $frac{1}{a_{n-1}}$ to a modular inverse. The effect of this is that whenever the numerator of $a_k$ is divisible by a prime p, then the sequence $b_n = 1+(b_{n−1})^{−1}$ mod p will have $b_k$ equal to 0. Why is this so? Or at least, why is it the numerator of $a_k$ that is so important?
$endgroup$
– johnrolfe
Dec 24 '18 at 21:43
$begingroup$
Well, until you hit $0's$ in the denominator you can just reduce the rational form modulo the given prime, To stick with your $13$, the multiplicative inverse of $8pmod {13}$ is $5pmod {13}$. Thus where you have $frac n8$ rationally, you'd get $5npmod {13}$. This reasoning works modulo each prime.
$endgroup$
– lulu
Dec 24 '18 at 21:47
$begingroup$
Oh, that makes sense. Thank you for clarifying!
$endgroup$
– johnrolfe
Dec 24 '18 at 21:53
$begingroup$
See here for modular fractions. You are simply reducing the sequence $!bmod n,,$ which is well-defined for all fractions with denominator coprime $,n. $ You'll get the same result whatever order you do the mod reductions, e.g. doing it all rationally then doing one final mod reduction , vs. reducing everything right away (or mix and match) because modular reduction commutes with ring operations plus, times (and said inverses), i.e. it is a ring homomorphism.
$endgroup$
– Bill Dubuque
Dec 24 '18 at 22:48