Mixing
About Congruences of $fracabmod n$ [closed]
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
Please forgive my cursory knowledge of modular arithmetic. My question is straightforward: is there a property of modular arithmetic that simplifies $fracabmod n$?
I attempted using the fact that $acdot bmod n equiv ((amod n)cdot(bmod n))mod n$ but found that $fracacdot nn mod n equiv a mod n$ does not hold.
Thank you. :)
modular-arithmetic
edited Jul 21 at 19:34
mrtaurho
700219
asked Jul 21 at 19:22
Tejas Rao
64
closed as unclear what you're asking by John Ma, José Carlos Santos, Shailesh, Taroccoesbrocco, Parcly Taxel Jul 22 at 5:04
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |Â
up vote
0
down vote
favorite
Please forgive my cursory knowledge of modular arithmetic. My question is straightforward: is there a property of modular arithmetic that simplifies $fracabmod n$?
I attempted using the fact that $acdot bmod n equiv ((amod n)cdot(bmod n))mod n$ but found that $fracacdot nn mod n equiv a mod n$ does not hold.
Thank you. :)
modular-arithmetic
edited Jul 21 at 19:34
mrtaurho
700219
asked Jul 21 at 19:22
Tejas Rao
64
closed as unclear what you're asking by John Ma, José Carlos Santos, Shailesh, Taroccoesbrocco, Parcly Taxel Jul 22 at 5:04
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
2
Is the / intended to be interpreted as division? You'll run into problems then in most scenarios and even run into problems defining it properly if you want to be strict. You can avoid the issue by instead talking about $acdot b^-1pmodn$ but you'll find that $b^-1$ only exists if $gcd(b,n)=1$.
– JMoravitz
Jul 21 at 19:26
I often get very cautious and nervous when I see the divison symbol in contexts that only apply to $mathbbZ$ (or non-fields in general).
– JuliusL33t
Jul 21 at 19:32
I don't know. It's like a razor sharp chainsaw. $frac 35 equiv 11mod 26$ can be a very useful tool in the right hands. Just make sure they are the right hands.
– fleablood
Jul 21 at 20:14
This answer might be relevant to this question. Perhaps this question might even be a duplicate of Doing modular division when denominator and modulus not coprime
– robjohn♦
Jul 21 at 21:49
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Please forgive my cursory knowledge of modular arithmetic. My question is straightforward: is there a property of modular arithmetic that simplifies $fracabmod n$?
I attempted using the fact that $acdot bmod n equiv ((amod n)cdot(bmod n))mod n$ but found that $fracacdot nn mod n equiv a mod n$ does not hold.
Thank you. :)
modular-arithmetic
edited Jul 21 at 19:34
mrtaurho
700219
asked Jul 21 at 19:22
Tejas Rao
64
Please forgive my cursory knowledge of modular arithmetic. My question is straightforward: is there a property of modular arithmetic that simplifies $fracabmod n$?
I attempted using the fact that $acdot bmod n equiv ((amod n)cdot(bmod n))mod n$ but found that $fracacdot nn mod n equiv a mod n$ does not hold.
Thank you. :)
modular-arithmetic
edited Jul 21 at 19:34
mrtaurho
700219
asked Jul 21 at 19:22
Tejas Rao
64
edited Jul 21 at 19:34
mrtaurho
700219
edited Jul 21 at 19:34
mrtaurho
700219
edited Jul 21 at 19:34
mrtaurho
700219
700219
asked Jul 21 at 19:22
Tejas Rao
64
asked Jul 21 at 19:22
Tejas Rao
64
asked Jul 21 at 19:22
Tejas Rao
64
64
closed as unclear what you're asking by John Ma, José Carlos Santos, Shailesh, Taroccoesbrocco, Parcly Taxel Jul 22 at 5:04
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
closed as unclear what you're asking by John Ma, José Carlos Santos, Shailesh, Taroccoesbrocco, Parcly Taxel Jul 22 at 5:04
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
2
Is the / intended to be interpreted as division? You'll run into problems then in most scenarios and even run into problems defining it properly if you want to be strict. You can avoid the issue by instead talking about $acdot b^-1pmodn$ but you'll find that $b^-1$ only exists if $gcd(b,n)=1$.
– JMoravitz
Jul 21 at 19:26
I often get very cautious and nervous when I see the divison symbol in contexts that only apply to $mathbbZ$ (or non-fields in general).
– JuliusL33t
Jul 21 at 19:32
I don't know. It's like a razor sharp chainsaw. $frac 35 equiv 11mod 26$ can be a very useful tool in the right hands. Just make sure they are the right hands.
– fleablood
Jul 21 at 20:14
This answer might be relevant to this question. Perhaps this question might even be a duplicate of Doing modular division when denominator and modulus not coprime
– robjohn♦
Jul 21 at 21:49
add a comment |Â
2
Is the / intended to be interpreted as division? You'll run into problems then in most scenarios and even run into problems defining it properly if you want to be strict. You can avoid the issue by instead talking about $acdot b^-1pmodn$ but you'll find that $b^-1$ only exists if $gcd(b,n)=1$.
– JMoravitz
Jul 21 at 19:26
I often get very cautious and nervous when I see the divison symbol in contexts that only apply to $mathbbZ$ (or non-fields in general).
– JuliusL33t
Jul 21 at 19:32
I don't know. It's like a razor sharp chainsaw. $frac 35 equiv 11mod 26$ can be a very useful tool in the right hands. Just make sure they are the right hands.
– fleablood
Jul 21 at 20:14
This answer might be relevant to this question. Perhaps this question might even be a duplicate of Doing modular division when denominator and modulus not coprime
– robjohn♦
Jul 21 at 21:49
2
2
Is the / intended to be interpreted as division? You'll run into problems then in most scenarios and even run into problems defining it properly if you want to be strict. You can avoid the issue by instead talking about $acdot b^-1pmodn$ but you'll find that $b^-1$ only exists if $gcd(b,n)=1$.
– JMoravitz
Jul 21 at 19:26
Is the / intended to be interpreted as division? You'll run into problems then in most scenarios and even run into problems defining it properly if you want to be strict. You can avoid the issue by instead talking about $acdot b^-1pmodn$ but you'll find that $b^-1$ only exists if $gcd(b,n)=1$.
– JMoravitz
Jul 21 at 19:26
I often get very cautious and nervous when I see the divison symbol in contexts that only apply to $mathbbZ$ (or non-fields in general).
– JuliusL33t
Jul 21 at 19:32
I often get very cautious and nervous when I see the divison symbol in contexts that only apply to $mathbbZ$ (or non-fields in general).
– JuliusL33t
Jul 21 at 19:32
I don't know. It's like a razor sharp chainsaw. $frac 35 equiv 11mod 26$ can be a very useful tool in the right hands. Just make sure they are the right hands.
– fleablood
Jul 21 at 20:14
I don't know. It's like a razor sharp chainsaw. $frac 35 equiv 11mod 26$ can be a very useful tool in the right hands. Just make sure they are the right hands.
– fleablood
Jul 21 at 20:14
This answer might be relevant to this question. Perhaps this question might even be a duplicate of Doing modular division when denominator and modulus not coprime
– robjohn♦
Jul 21 at 21:49
This answer might be relevant to this question. Perhaps this question might even be a duplicate of Doing modular division when denominator and modulus not coprime
– robjohn♦
Jul 21 at 21:49
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
It depends on what $frac ab mod n$ means.
Consider $frac 84 mod 6$. If you mean that to mean $q mod 6$ where $q = frac 84 = 2in mathbb Z$ then this is nothing more or less then $2 mod 6$. No issue.
But if $q = frac 13 not in mathbb Z$ then $qmod 6$... what do you mean?
You could, but probably don't, mean $[q]= q + k6$ in many analysis/calculus/geometry context this make sense. In particular $theta mod 2pi =theta + 2kpi$ has obvious practical applications.
But we almost never mean this in number theory. In number theory it is assume the we are working in the number system $mathbb Z/nmathbb Z = {$ the set of complete residue systems $mod n$. In which case $[x]$ when $x$ is not an integer simply makes no sense.
But In the case where $a*x equiv 1 mod n$ then $x$ acts practically as a multiplicative inverse to $a$ and we wish to say $x = a^-1mod n$ (which means, by definition, that $ax equiv 1 mod n$. And we do right that as $xequiv frac 1a mod n$.
Exampe $3*5 equiv 1 mod 14$ so $3 equiv frac 15 mod 14$. It's important to realize that $frac 15$ has NOTHING to do with the rational number $0.2$ but simply means ... the $x$ so that $x*5 equiv 1 mod 14$.
So in this case $frac ab mod n$ means the number $x$ so that $bx equiv a mod n$.....
.... if such a residue class exists
.... and if it is distinct.
There are two catches: 1) it might not exists; $frac 32 mod 6$ is is the integer $x$ so that $2x equiv 3 mod 6$. There is no solution to that. 2) there might be multiple solutions; $2*6equiv 8*6equiv 3 mod 9$ so $frac 36 mod 9$ would be ill-defined.
But $frac ab mod n$ will have a distinct solution if and only if $b$ and $n$ are relatively prime. Then there will be a solution to $bx = 1 + kn$ and it is unique $mod n$. And $frac ab equiv axmod n$ would be the unique value.
If $gcd(b,n)=dne 1$ and $a$ is not a multiple of $d$ then there is no solution to $bx = a + kn$ and $d|b$ and $d|n$ but $dnot mid a$. And if $a = md$ then $bx = a +kn$ will have a solution. But $b(x + frac nd) =bx + frac bd*n equiv bx equiv a mod n$ is also a solution.
tl;dr
In number theory $frac ab$ means the unique residue solution to $bx equiv a mod n$ which only exists if $gcd(b, n) =1$ and which is equal to $aymod n$ where $yequiv frac 1b mod n$ is the unique solution to $by equiv 1 mod n$.
answered Jul 21 at 20:11
fleablood
60.4k22575
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
It depends on what $frac ab mod n$ means.
Consider $frac 84 mod 6$. If you mean that to mean $q mod 6$ where $q = frac 84 = 2in mathbb Z$ then this is nothing more or less then $2 mod 6$. No issue.
But if $q = frac 13 not in mathbb Z$ then $qmod 6$... what do you mean?
You could, but probably don't, mean $[q]= q + k6$ in many analysis/calculus/geometry context this make sense. In particular $theta mod 2pi =theta + 2kpi$ has obvious practical applications.
But we almost never mean this in number theory. In number theory it is assume the we are working in the number system $mathbb Z/nmathbb Z = {$ the set of complete residue systems $mod n$. In which case $[x]$ when $x$ is not an integer simply makes no sense.
But In the case where $a*x equiv 1 mod n$ then $x$ acts practically as a multiplicative inverse to $a$ and we wish to say $x = a^-1mod n$ (which means, by definition, that $ax equiv 1 mod n$. And we do right that as $xequiv frac 1a mod n$.
Exampe $3*5 equiv 1 mod 14$ so $3 equiv frac 15 mod 14$. It's important to realize that $frac 15$ has NOTHING to do with the rational number $0.2$ but simply means ... the $x$ so that $x*5 equiv 1 mod 14$.
So in this case $frac ab mod n$ means the number $x$ so that $bx equiv a mod n$.....
.... if such a residue class exists
.... and if it is distinct.
There are two catches: 1) it might not exists; $frac 32 mod 6$ is is the integer $x$ so that $2x equiv 3 mod 6$. There is no solution to that. 2) there might be multiple solutions; $2*6equiv 8*6equiv 3 mod 9$ so $frac 36 mod 9$ would be ill-defined.
But $frac ab mod n$ will have a distinct solution if and only if $b$ and $n$ are relatively prime. Then there will be a solution to $bx = 1 + kn$ and it is unique $mod n$. And $frac ab equiv axmod n$ would be the unique value.
If $gcd(b,n)=dne 1$ and $a$ is not a multiple of $d$ then there is no solution to $bx = a + kn$ and $d|b$ and $d|n$ but $dnot mid a$. And if $a = md$ then $bx = a +kn$ will have a solution. But $b(x + frac nd) =bx + frac bd*n equiv bx equiv a mod n$ is also a solution.
tl;dr
In number theory $frac ab$ means the unique residue solution to $bx equiv a mod n$ which only exists if $gcd(b, n) =1$ and which is equal to $aymod n$ where $yequiv frac 1b mod n$ is the unique solution to $by equiv 1 mod n$.
answered Jul 21 at 20:11
fleablood
60.4k22575
add a comment |Â
up vote
1
down vote
It depends on what $frac ab mod n$ means.
Consider $frac 84 mod 6$. If you mean that to mean $q mod 6$ where $q = frac 84 = 2in mathbb Z$ then this is nothing more or less then $2 mod 6$. No issue.
But if $q = frac 13 not in mathbb Z$ then $qmod 6$... what do you mean?
You could, but probably don't, mean $[q]= q + k6$ in many analysis/calculus/geometry context this make sense. In particular $theta mod 2pi =theta + 2kpi$ has obvious practical applications.
But we almost never mean this in number theory. In number theory it is assume the we are working in the number system $mathbb Z/nmathbb Z = {$ the set of complete residue systems $mod n$. In which case $[x]$ when $x$ is not an integer simply makes no sense.
But In the case where $a*x equiv 1 mod n$ then $x$ acts practically as a multiplicative inverse to $a$ and we wish to say $x = a^-1mod n$ (which means, by definition, that $ax equiv 1 mod n$. And we do right that as $xequiv frac 1a mod n$.
Exampe $3*5 equiv 1 mod 14$ so $3 equiv frac 15 mod 14$. It's important to realize that $frac 15$ has NOTHING to do with the rational number $0.2$ but simply means ... the $x$ so that $x*5 equiv 1 mod 14$.
So in this case $frac ab mod n$ means the number $x$ so that $bx equiv a mod n$.....
.... if such a residue class exists
.... and if it is distinct.
There are two catches: 1) it might not exists; $frac 32 mod 6$ is is the integer $x$ so that $2x equiv 3 mod 6$. There is no solution to that. 2) there might be multiple solutions; $2*6equiv 8*6equiv 3 mod 9$ so $frac 36 mod 9$ would be ill-defined.
But $frac ab mod n$ will have a distinct solution if and only if $b$ and $n$ are relatively prime. Then there will be a solution to $bx = 1 + kn$ and it is unique $mod n$. And $frac ab equiv axmod n$ would be the unique value.
If $gcd(b,n)=dne 1$ and $a$ is not a multiple of $d$ then there is no solution to $bx = a + kn$ and $d|b$ and $d|n$ but $dnot mid a$. And if $a = md$ then $bx = a +kn$ will have a solution. But $b(x + frac nd) =bx + frac bd*n equiv bx equiv a mod n$ is also a solution.
tl;dr
In number theory $frac ab$ means the unique residue solution to $bx equiv a mod n$ which only exists if $gcd(b, n) =1$ and which is equal to $aymod n$ where $yequiv frac 1b mod n$ is the unique solution to $by equiv 1 mod n$.
answered Jul 21 at 20:11
fleablood
60.4k22575
add a comment |Â
up vote
1
down vote
up vote
1
down vote
It depends on what $frac ab mod n$ means.
Consider $frac 84 mod 6$. If you mean that to mean $q mod 6$ where $q = frac 84 = 2in mathbb Z$ then this is nothing more or less then $2 mod 6$. No issue.
But if $q = frac 13 not in mathbb Z$ then $qmod 6$... what do you mean?
You could, but probably don't, mean $[q]= q + k6$ in many analysis/calculus/geometry context this make sense. In particular $theta mod 2pi =theta + 2kpi$ has obvious practical applications.
But we almost never mean this in number theory. In number theory it is assume the we are working in the number system $mathbb Z/nmathbb Z = {$ the set of complete residue systems $mod n$. In which case $[x]$ when $x$ is not an integer simply makes no sense.
But In the case where $a*x equiv 1 mod n$ then $x$ acts practically as a multiplicative inverse to $a$ and we wish to say $x = a^-1mod n$ (which means, by definition, that $ax equiv 1 mod n$. And we do right that as $xequiv frac 1a mod n$.
Exampe $3*5 equiv 1 mod 14$ so $3 equiv frac 15 mod 14$. It's important to realize that $frac 15$ has NOTHING to do with the rational number $0.2$ but simply means ... the $x$ so that $x*5 equiv 1 mod 14$.
So in this case $frac ab mod n$ means the number $x$ so that $bx equiv a mod n$.....
.... if such a residue class exists
.... and if it is distinct.
There are two catches: 1) it might not exists; $frac 32 mod 6$ is is the integer $x$ so that $2x equiv 3 mod 6$. There is no solution to that. 2) there might be multiple solutions; $2*6equiv 8*6equiv 3 mod 9$ so $frac 36 mod 9$ would be ill-defined.
But $frac ab mod n$ will have a distinct solution if and only if $b$ and $n$ are relatively prime. Then there will be a solution to $bx = 1 + kn$ and it is unique $mod n$. And $frac ab equiv axmod n$ would be the unique value.
If $gcd(b,n)=dne 1$ and $a$ is not a multiple of $d$ then there is no solution to $bx = a + kn$ and $d|b$ and $d|n$ but $dnot mid a$. And if $a = md$ then $bx = a +kn$ will have a solution. But $b(x + frac nd) =bx + frac bd*n equiv bx equiv a mod n$ is also a solution.
tl;dr
In number theory $frac ab$ means the unique residue solution to $bx equiv a mod n$ which only exists if $gcd(b, n) =1$ and which is equal to $aymod n$ where $yequiv frac 1b mod n$ is the unique solution to $by equiv 1 mod n$.
answered Jul 21 at 20:11
fleablood
60.4k22575
It depends on what $frac ab mod n$ means.
Consider $frac 84 mod 6$. If you mean that to mean $q mod 6$ where $q = frac 84 = 2in mathbb Z$ then this is nothing more or less then $2 mod 6$. No issue.
But if $q = frac 13 not in mathbb Z$ then $qmod 6$... what do you mean?
You could, but probably don't, mean $[q]= q + k6$ in many analysis/calculus/geometry context this make sense. In particular $theta mod 2pi =theta + 2kpi$ has obvious practical applications.
But we almost never mean this in number theory. In number theory it is assume the we are working in the number system $mathbb Z/nmathbb Z = {$ the set of complete residue systems $mod n$. In which case $[x]$ when $x$ is not an integer simply makes no sense.
But In the case where $a*x equiv 1 mod n$ then $x$ acts practically as a multiplicative inverse to $a$ and we wish to say $x = a^-1mod n$ (which means, by definition, that $ax equiv 1 mod n$. And we do right that as $xequiv frac 1a mod n$.
Exampe $3*5 equiv 1 mod 14$ so $3 equiv frac 15 mod 14$. It's important to realize that $frac 15$ has NOTHING to do with the rational number $0.2$ but simply means ... the $x$ so that $x*5 equiv 1 mod 14$.
So in this case $frac ab mod n$ means the number $x$ so that $bx equiv a mod n$.....
.... if such a residue class exists
.... and if it is distinct.
There are two catches: 1) it might not exists; $frac 32 mod 6$ is is the integer $x$ so that $2x equiv 3 mod 6$. There is no solution to that. 2) there might be multiple solutions; $2*6equiv 8*6equiv 3 mod 9$ so $frac 36 mod 9$ would be ill-defined.
But $frac ab mod n$ will have a distinct solution if and only if $b$ and $n$ are relatively prime. Then there will be a solution to $bx = 1 + kn$ and it is unique $mod n$. And $frac ab equiv axmod n$ would be the unique value.
If $gcd(b,n)=dne 1$ and $a$ is not a multiple of $d$ then there is no solution to $bx = a + kn$ and $d|b$ and $d|n$ but $dnot mid a$. And if $a = md$ then $bx = a +kn$ will have a solution. But $b(x + frac nd) =bx + frac bd*n equiv bx equiv a mod n$ is also a solution.
tl;dr
In number theory $frac ab$ means the unique residue solution to $bx equiv a mod n$ which only exists if $gcd(b, n) =1$ and which is equal to $aymod n$ where $yequiv frac 1b mod n$ is the unique solution to $by equiv 1 mod n$.
answered Jul 21 at 20:11
fleablood
60.4k22575
answered Jul 21 at 20:11
fleablood
60.4k22575
answered Jul 21 at 20:11
fleablood
60.4k22575
answered Jul 21 at 20:11
fleablood
60.4k22575
60.4k22575
add a comment |Â
add a comment |Â
2
Is the / intended to be interpreted as division? You'll run into problems then in most scenarios and even run into problems defining it properly if you want to be strict. You can avoid the issue by instead talking about $acdot b^-1pmodn$ but you'll find that $b^-1$ only exists if $gcd(b,n)=1$.
– JMoravitz
Jul 21 at 19:26
I often get very cautious and nervous when I see the divison symbol in contexts that only apply to $mathbbZ$ (or non-fields in general).
– JuliusL33t
Jul 21 at 19:32
I don't know. It's like a razor sharp chainsaw. $frac 35 equiv 11mod 26$ can be a very useful tool in the right hands. Just make sure they are the right hands.
– fleablood
Jul 21 at 20:14
This answer might be relevant to this question. Perhaps this question might even be a duplicate of Doing modular division when denominator and modulus not coprime
– robjohn♦
Jul 21 at 21:49