Mixing
Find all solutions to $x^2equiv 1pmod {91}$
$begingroup$
I split this into $x^2equiv 1pmod {7}$ and $x^2equiv 1pmod {13}$.
For $x^2equiv 1pmod {7}$, i did:
$$ (pm1 )^2equiv 1pmod{7}$$ $$(pm2 )^2equiv 4pmod{7}$$ $$(pm3 )^2equiv 2pmod{7}$$ Which shows that the solutions to $x^2equiv 1pmod {7}$ are $pm1$.
For $x^2equiv 1pmod {13}$, i did:
$$ (pm1 )^2equiv 1pmod{13}$$ $$(pm2 )^2equiv 4pmod{13}$$ $$(pm3 )^2equiv 9pmod{13}$$ $$ (pm4 )^2equiv 3pmod{13}$$ $$(pm5 )^2equiv {-1}pmod{13}$$ $$(pm6 )^2equiv 10pmod{13}$$Which shows that the solutions to $x^2equiv 1pmod {13}$ are $pm1$.
Thus, I concluded that the solutions to $x^2equiv 1pmod {91}$ must be $pm1$. I thought that $pm1$ were the only solutions, but apparently I am incorrect! How do I go about finding the other solutions to this congruence?
number-theory modular-arithmetic congruences
asked Dec 3 '16 at 2:33
J. DoeJ. Doe
10210
$endgroup$
add a comment |
$begingroup$
I split this into $x^2equiv 1pmod {7}$ and $x^2equiv 1pmod {13}$.
For $x^2equiv 1pmod {7}$, i did:
$$ (pm1 )^2equiv 1pmod{7}$$ $$(pm2 )^2equiv 4pmod{7}$$ $$(pm3 )^2equiv 2pmod{7}$$ Which shows that the solutions to $x^2equiv 1pmod {7}$ are $pm1$.
For $x^2equiv 1pmod {13}$, i did:
$$ (pm1 )^2equiv 1pmod{13}$$ $$(pm2 )^2equiv 4pmod{13}$$ $$(pm3 )^2equiv 9pmod{13}$$ $$ (pm4 )^2equiv 3pmod{13}$$ $$(pm5 )^2equiv {-1}pmod{13}$$ $$(pm6 )^2equiv 10pmod{13}$$Which shows that the solutions to $x^2equiv 1pmod {13}$ are $pm1$.
Thus, I concluded that the solutions to $x^2equiv 1pmod {91}$ must be $pm1$. I thought that $pm1$ were the only solutions, but apparently I am incorrect! How do I go about finding the other solutions to this congruence?
number-theory modular-arithmetic congruences
asked Dec 3 '16 at 2:33
J. DoeJ. Doe
10210
$endgroup$
1
$begingroup$
Hint: CRT. See link
$endgroup$
– user160069
Dec 3 '16 at 2:38
add a comment |
$begingroup$
I split this into $x^2equiv 1pmod {7}$ and $x^2equiv 1pmod {13}$.
For $x^2equiv 1pmod {7}$, i did:
$$ (pm1 )^2equiv 1pmod{7}$$ $$(pm2 )^2equiv 4pmod{7}$$ $$(pm3 )^2equiv 2pmod{7}$$ Which shows that the solutions to $x^2equiv 1pmod {7}$ are $pm1$.
For $x^2equiv 1pmod {13}$, i did:
$$ (pm1 )^2equiv 1pmod{13}$$ $$(pm2 )^2equiv 4pmod{13}$$ $$(pm3 )^2equiv 9pmod{13}$$ $$ (pm4 )^2equiv 3pmod{13}$$ $$(pm5 )^2equiv {-1}pmod{13}$$ $$(pm6 )^2equiv 10pmod{13}$$Which shows that the solutions to $x^2equiv 1pmod {13}$ are $pm1$.
Thus, I concluded that the solutions to $x^2equiv 1pmod {91}$ must be $pm1$. I thought that $pm1$ were the only solutions, but apparently I am incorrect! How do I go about finding the other solutions to this congruence?
number-theory modular-arithmetic congruences
asked Dec 3 '16 at 2:33
J. DoeJ. Doe
10210
$endgroup$
I split this into $x^2equiv 1pmod {7}$ and $x^2equiv 1pmod {13}$.
For $x^2equiv 1pmod {7}$, i did:
$$ (pm1 )^2equiv 1pmod{7}$$ $$(pm2 )^2equiv 4pmod{7}$$ $$(pm3 )^2equiv 2pmod{7}$$ Which shows that the solutions to $x^2equiv 1pmod {7}$ are $pm1$.
For $x^2equiv 1pmod {13}$, i did:
$$ (pm1 )^2equiv 1pmod{13}$$ $$(pm2 )^2equiv 4pmod{13}$$ $$(pm3 )^2equiv 9pmod{13}$$ $$ (pm4 )^2equiv 3pmod{13}$$ $$(pm5 )^2equiv {-1}pmod{13}$$ $$(pm6 )^2equiv 10pmod{13}$$Which shows that the solutions to $x^2equiv 1pmod {13}$ are $pm1$.
Thus, I concluded that the solutions to $x^2equiv 1pmod {91}$ must be $pm1$. I thought that $pm1$ were the only solutions, but apparently I am incorrect! How do I go about finding the other solutions to this congruence?
number-theory modular-arithmetic congruences
number-theory modular-arithmetic congruences
asked Dec 3 '16 at 2:33
J. DoeJ. Doe
10210
asked Dec 3 '16 at 2:33
J. DoeJ. Doe
10210
asked Dec 3 '16 at 2:33
J. DoeJ. Doe
10210
asked Dec 3 '16 at 2:33
J. DoeJ. Doe
10210
asked Dec 3 '16 at 2:33
J. DoeJ. Doe
10210
10210
1
$begingroup$
Hint: CRT. See link
$endgroup$
– user160069
Dec 3 '16 at 2:38
add a comment |
1
$begingroup$
Hint: CRT. See link
$endgroup$
– user160069
Dec 3 '16 at 2:38
1
1
$begingroup$
Hint: CRT. See link
$endgroup$
– user160069
Dec 3 '16 at 2:38
$begingroup$
Hint: CRT. See link
$endgroup$
– user160069
Dec 3 '16 at 2:38
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
You have $xequivpm1mod7$ and $xequivpm1mod13$. For all the solutions, you have to consider the systems:
$$xequiv1mod7$$
$$xequiv1mod13$$
and
$$xequiv-1mod7$$
$$xequiv1mod13$$
and
$$xequiv1mod7$$
$$xequiv-1mod13$$
and
$$xequiv-1mod7$$
$$xequiv-1mod13$$
as each system will get you a valid answer. I think you only had the first and the last systems and that you only considered the cases where the signs were similar.
answered Dec 3 '16 at 2:41
AlgorithmsXAlgorithmsX
4,1071828
$endgroup$
$begingroup$
Thank you! I figured out the other solutions to be $pm 27$.
$endgroup$
– J. Doe
Dec 3 '16 at 3:40
add a comment |
$begingroup$
Hint: Consider the possibility that $x equiv 1 pmod 7$ but $x equiv -1 pmod {13}$, and so on. (In other words, your mistake was to assume that the $pm1$ modulo $7$ was the same sign as $pm1$ modulo $13$.)
Also note that for any prime $p$, if $x^2 equiv 1 pmod p$, then we can rewrite this as $$x^2 - 1 equiv (x+1)(x-1) equiv 0 pmod p.$$
Thus we get $x equiv pm 1 pmod p$, showing that it isn't necessary to run through all the values of $x^2$ to find the solution.
answered Dec 3 '16 at 2:38
ThéophileThéophile
19.8k12946
$endgroup$
add a comment |
$begingroup$
By CRT the solutions $,xequiv pm1pmod 7, xequiv pm1pmod{13}$ combine to $,4,$ solutions mod $91,,$ viz $,xequiv (color{#c00}{{bf 1,1}}),,(color{#0a0}{-1,-1}),,(1,-1),,(-1,1),$ mod $(7,13),$ cf. Remark below. The first $2$ have obvious solutions $,color{#c00}{bf 1},$ and $,color{#0a0}{-1},$ so you need only solve the $(1,-1)$ case, then note $(-1,1)equiv -(1,-1)$ is its negative, i.e. $,xequiv 1pmod{!7},,xequiv -1pmod{!13},Rightarrow,-xequiv -1pmod{!7}, {-}xequiv 1pmod{!13}$
Remark $ $ For more complex examples it is usually easier to solve the CRT system first for generic (symbolic) roots, then plug in the specific root values for all combinations, e.g. see here and here.
If $,m,n,$ are coprime then, by CRT, solving a polynomial $,f(x)equiv 0pmod{!mn},$ is equivalent to solving $,f(x)equiv 0,$ mod $,m,$ and mod $,n.,$ By CRT, each combination of a root $,r_ibmod m,$ and a root $,s_jbmod n,$ corresponds to a unique root $,t_{ij}bmod mn,,$ i.e.
$$begin{eqnarray} f(x)equiv 0!!!pmod{!mn}&overset{,,rm CRT}iff& begin{array}{}f(x)equiv 0pmod{! m}\f(x)equiv 0pmod{! n}end{array} \
&,,iff& begin{array}{}xequiv r_1,ldots,r_kpmod{! m}phantom{I^{I^{I^I}}}\xequiv s_1,ldots,s_ellpmod{! n}end{array}\
&,,iff& left{ begin{array}{}xequiv r_ipmod{! m}\xequiv s_jpmod {! n}end{array} right}_{begin{array}{}1le ile k\ 1le jleellend{array}}^{phantom{I^{I^{I^I}}}}\
&overset{,,rm CRT}iff& left{ xequiv t_{i j}!!pmod{!mn} right}_{begin{array}{}1le ile k\ 1le jleellend{array}}\
end{eqnarray}qquadqquad$$
answered Dec 3 '16 at 3:59
Bill DubuqueBill Dubuque
211k29193646
$endgroup$
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%2f2041254%2ffind-all-solutions-to-x2-equiv-1-pmod-91%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
You have $xequivpm1mod7$ and $xequivpm1mod13$. For all the solutions, you have to consider the systems:
$$xequiv1mod7$$
$$xequiv1mod13$$
and
$$xequiv-1mod7$$
$$xequiv1mod13$$
and
$$xequiv1mod7$$
$$xequiv-1mod13$$
and
$$xequiv-1mod7$$
$$xequiv-1mod13$$
as each system will get you a valid answer. I think you only had the first and the last systems and that you only considered the cases where the signs were similar.
answered Dec 3 '16 at 2:41
AlgorithmsXAlgorithmsX
4,1071828
$endgroup$
$begingroup$
Thank you! I figured out the other solutions to be $pm 27$.
$endgroup$
– J. Doe
Dec 3 '16 at 3:40
add a comment |
$begingroup$
You have $xequivpm1mod7$ and $xequivpm1mod13$. For all the solutions, you have to consider the systems:
$$xequiv1mod7$$
$$xequiv1mod13$$
and
$$xequiv-1mod7$$
$$xequiv1mod13$$
and
$$xequiv1mod7$$
$$xequiv-1mod13$$
and
$$xequiv-1mod7$$
$$xequiv-1mod13$$
as each system will get you a valid answer. I think you only had the first and the last systems and that you only considered the cases where the signs were similar.
answered Dec 3 '16 at 2:41
AlgorithmsXAlgorithmsX
4,1071828
$endgroup$
$begingroup$
Thank you! I figured out the other solutions to be $pm 27$.
$endgroup$
– J. Doe
Dec 3 '16 at 3:40
add a comment |
$begingroup$
You have $xequivpm1mod7$ and $xequivpm1mod13$. For all the solutions, you have to consider the systems:
$$xequiv1mod7$$
$$xequiv1mod13$$
and
$$xequiv-1mod7$$
$$xequiv1mod13$$
and
$$xequiv1mod7$$
$$xequiv-1mod13$$
and
$$xequiv-1mod7$$
$$xequiv-1mod13$$
as each system will get you a valid answer. I think you only had the first and the last systems and that you only considered the cases where the signs were similar.
answered Dec 3 '16 at 2:41
AlgorithmsXAlgorithmsX
4,1071828
$endgroup$
You have $xequivpm1mod7$ and $xequivpm1mod13$. For all the solutions, you have to consider the systems:
$$xequiv1mod7$$
$$xequiv1mod13$$
and
$$xequiv-1mod7$$
$$xequiv1mod13$$
and
$$xequiv1mod7$$
$$xequiv-1mod13$$
and
$$xequiv-1mod7$$
$$xequiv-1mod13$$
as each system will get you a valid answer. I think you only had the first and the last systems and that you only considered the cases where the signs were similar.
answered Dec 3 '16 at 2:41
AlgorithmsXAlgorithmsX
4,1071828
answered Dec 3 '16 at 2:41
AlgorithmsXAlgorithmsX
4,1071828
answered Dec 3 '16 at 2:41
AlgorithmsXAlgorithmsX
4,1071828
answered Dec 3 '16 at 2:41
AlgorithmsXAlgorithmsX
4,1071828
4,1071828
$begingroup$
Thank you! I figured out the other solutions to be $pm 27$.
$endgroup$
– J. Doe
Dec 3 '16 at 3:40
add a comment |
$begingroup$
Thank you! I figured out the other solutions to be $pm 27$.
$endgroup$
– J. Doe
Dec 3 '16 at 3:40
$begingroup$
Thank you! I figured out the other solutions to be $pm 27$.
$endgroup$
– J. Doe
Dec 3 '16 at 3:40
$begingroup$
Thank you! I figured out the other solutions to be $pm 27$.
$endgroup$
– J. Doe
Dec 3 '16 at 3:40
add a comment |
$begingroup$
Hint: Consider the possibility that $x equiv 1 pmod 7$ but $x equiv -1 pmod {13}$, and so on. (In other words, your mistake was to assume that the $pm1$ modulo $7$ was the same sign as $pm1$ modulo $13$.)
Also note that for any prime $p$, if $x^2 equiv 1 pmod p$, then we can rewrite this as $$x^2 - 1 equiv (x+1)(x-1) equiv 0 pmod p.$$
Thus we get $x equiv pm 1 pmod p$, showing that it isn't necessary to run through all the values of $x^2$ to find the solution.
answered Dec 3 '16 at 2:38
ThéophileThéophile
19.8k12946
$endgroup$
add a comment |
$begingroup$
Hint: Consider the possibility that $x equiv 1 pmod 7$ but $x equiv -1 pmod {13}$, and so on. (In other words, your mistake was to assume that the $pm1$ modulo $7$ was the same sign as $pm1$ modulo $13$.)
Also note that for any prime $p$, if $x^2 equiv 1 pmod p$, then we can rewrite this as $$x^2 - 1 equiv (x+1)(x-1) equiv 0 pmod p.$$
Thus we get $x equiv pm 1 pmod p$, showing that it isn't necessary to run through all the values of $x^2$ to find the solution.
answered Dec 3 '16 at 2:38
ThéophileThéophile
19.8k12946
$endgroup$
add a comment |
$begingroup$
Hint: Consider the possibility that $x equiv 1 pmod 7$ but $x equiv -1 pmod {13}$, and so on. (In other words, your mistake was to assume that the $pm1$ modulo $7$ was the same sign as $pm1$ modulo $13$.)
Also note that for any prime $p$, if $x^2 equiv 1 pmod p$, then we can rewrite this as $$x^2 - 1 equiv (x+1)(x-1) equiv 0 pmod p.$$
Thus we get $x equiv pm 1 pmod p$, showing that it isn't necessary to run through all the values of $x^2$ to find the solution.
answered Dec 3 '16 at 2:38
ThéophileThéophile
19.8k12946
$endgroup$
Hint: Consider the possibility that $x equiv 1 pmod 7$ but $x equiv -1 pmod {13}$, and so on. (In other words, your mistake was to assume that the $pm1$ modulo $7$ was the same sign as $pm1$ modulo $13$.)
Also note that for any prime $p$, if $x^2 equiv 1 pmod p$, then we can rewrite this as $$x^2 - 1 equiv (x+1)(x-1) equiv 0 pmod p.$$
Thus we get $x equiv pm 1 pmod p$, showing that it isn't necessary to run through all the values of $x^2$ to find the solution.
answered Dec 3 '16 at 2:38
ThéophileThéophile
19.8k12946
answered Dec 3 '16 at 2:38
ThéophileThéophile
19.8k12946
answered Dec 3 '16 at 2:38
ThéophileThéophile
19.8k12946
answered Dec 3 '16 at 2:38
ThéophileThéophile
19.8k12946
19.8k12946
add a comment |
add a comment |
$begingroup$
By CRT the solutions $,xequiv pm1pmod 7, xequiv pm1pmod{13}$ combine to $,4,$ solutions mod $91,,$ viz $,xequiv (color{#c00}{{bf 1,1}}),,(color{#0a0}{-1,-1}),,(1,-1),,(-1,1),$ mod $(7,13),$ cf. Remark below. The first $2$ have obvious solutions $,color{#c00}{bf 1},$ and $,color{#0a0}{-1},$ so you need only solve the $(1,-1)$ case, then note $(-1,1)equiv -(1,-1)$ is its negative, i.e. $,xequiv 1pmod{!7},,xequiv -1pmod{!13},Rightarrow,-xequiv -1pmod{!7}, {-}xequiv 1pmod{!13}$
Remark $ $ For more complex examples it is usually easier to solve the CRT system first for generic (symbolic) roots, then plug in the specific root values for all combinations, e.g. see here and here.
If $,m,n,$ are coprime then, by CRT, solving a polynomial $,f(x)equiv 0pmod{!mn},$ is equivalent to solving $,f(x)equiv 0,$ mod $,m,$ and mod $,n.,$ By CRT, each combination of a root $,r_ibmod m,$ and a root $,s_jbmod n,$ corresponds to a unique root $,t_{ij}bmod mn,,$ i.e.
$$begin{eqnarray} f(x)equiv 0!!!pmod{!mn}&overset{,,rm CRT}iff& begin{array}{}f(x)equiv 0pmod{! m}\f(x)equiv 0pmod{! n}end{array} \
&,,iff& begin{array}{}xequiv r_1,ldots,r_kpmod{! m}phantom{I^{I^{I^I}}}\xequiv s_1,ldots,s_ellpmod{! n}end{array}\
&,,iff& left{ begin{array}{}xequiv r_ipmod{! m}\xequiv s_jpmod {! n}end{array} right}_{begin{array}{}1le ile k\ 1le jleellend{array}}^{phantom{I^{I^{I^I}}}}\
&overset{,,rm CRT}iff& left{ xequiv t_{i j}!!pmod{!mn} right}_{begin{array}{}1le ile k\ 1le jleellend{array}}\
end{eqnarray}qquadqquad$$
answered Dec 3 '16 at 3:59
Bill DubuqueBill Dubuque
211k29193646
$endgroup$
add a comment |
$begingroup$
By CRT the solutions $,xequiv pm1pmod 7, xequiv pm1pmod{13}$ combine to $,4,$ solutions mod $91,,$ viz $,xequiv (color{#c00}{{bf 1,1}}),,(color{#0a0}{-1,-1}),,(1,-1),,(-1,1),$ mod $(7,13),$ cf. Remark below. The first $2$ have obvious solutions $,color{#c00}{bf 1},$ and $,color{#0a0}{-1},$ so you need only solve the $(1,-1)$ case, then note $(-1,1)equiv -(1,-1)$ is its negative, i.e. $,xequiv 1pmod{!7},,xequiv -1pmod{!13},Rightarrow,-xequiv -1pmod{!7}, {-}xequiv 1pmod{!13}$
Remark $ $ For more complex examples it is usually easier to solve the CRT system first for generic (symbolic) roots, then plug in the specific root values for all combinations, e.g. see here and here.
If $,m,n,$ are coprime then, by CRT, solving a polynomial $,f(x)equiv 0pmod{!mn},$ is equivalent to solving $,f(x)equiv 0,$ mod $,m,$ and mod $,n.,$ By CRT, each combination of a root $,r_ibmod m,$ and a root $,s_jbmod n,$ corresponds to a unique root $,t_{ij}bmod mn,,$ i.e.
$$begin{eqnarray} f(x)equiv 0!!!pmod{!mn}&overset{,,rm CRT}iff& begin{array}{}f(x)equiv 0pmod{! m}\f(x)equiv 0pmod{! n}end{array} \
&,,iff& begin{array}{}xequiv r_1,ldots,r_kpmod{! m}phantom{I^{I^{I^I}}}\xequiv s_1,ldots,s_ellpmod{! n}end{array}\
&,,iff& left{ begin{array}{}xequiv r_ipmod{! m}\xequiv s_jpmod {! n}end{array} right}_{begin{array}{}1le ile k\ 1le jleellend{array}}^{phantom{I^{I^{I^I}}}}\
&overset{,,rm CRT}iff& left{ xequiv t_{i j}!!pmod{!mn} right}_{begin{array}{}1le ile k\ 1le jleellend{array}}\
end{eqnarray}qquadqquad$$
answered Dec 3 '16 at 3:59
Bill DubuqueBill Dubuque
211k29193646
$endgroup$
add a comment |
$begingroup$
By CRT the solutions $,xequiv pm1pmod 7, xequiv pm1pmod{13}$ combine to $,4,$ solutions mod $91,,$ viz $,xequiv (color{#c00}{{bf 1,1}}),,(color{#0a0}{-1,-1}),,(1,-1),,(-1,1),$ mod $(7,13),$ cf. Remark below. The first $2$ have obvious solutions $,color{#c00}{bf 1},$ and $,color{#0a0}{-1},$ so you need only solve the $(1,-1)$ case, then note $(-1,1)equiv -(1,-1)$ is its negative, i.e. $,xequiv 1pmod{!7},,xequiv -1pmod{!13},Rightarrow,-xequiv -1pmod{!7}, {-}xequiv 1pmod{!13}$
Remark $ $ For more complex examples it is usually easier to solve the CRT system first for generic (symbolic) roots, then plug in the specific root values for all combinations, e.g. see here and here.
If $,m,n,$ are coprime then, by CRT, solving a polynomial $,f(x)equiv 0pmod{!mn},$ is equivalent to solving $,f(x)equiv 0,$ mod $,m,$ and mod $,n.,$ By CRT, each combination of a root $,r_ibmod m,$ and a root $,s_jbmod n,$ corresponds to a unique root $,t_{ij}bmod mn,,$ i.e.
$$begin{eqnarray} f(x)equiv 0!!!pmod{!mn}&overset{,,rm CRT}iff& begin{array}{}f(x)equiv 0pmod{! m}\f(x)equiv 0pmod{! n}end{array} \
&,,iff& begin{array}{}xequiv r_1,ldots,r_kpmod{! m}phantom{I^{I^{I^I}}}\xequiv s_1,ldots,s_ellpmod{! n}end{array}\
&,,iff& left{ begin{array}{}xequiv r_ipmod{! m}\xequiv s_jpmod {! n}end{array} right}_{begin{array}{}1le ile k\ 1le jleellend{array}}^{phantom{I^{I^{I^I}}}}\
&overset{,,rm CRT}iff& left{ xequiv t_{i j}!!pmod{!mn} right}_{begin{array}{}1le ile k\ 1le jleellend{array}}\
end{eqnarray}qquadqquad$$
answered Dec 3 '16 at 3:59
Bill DubuqueBill Dubuque
211k29193646
$endgroup$
By CRT the solutions $,xequiv pm1pmod 7, xequiv pm1pmod{13}$ combine to $,4,$ solutions mod $91,,$ viz $,xequiv (color{#c00}{{bf 1,1}}),,(color{#0a0}{-1,-1}),,(1,-1),,(-1,1),$ mod $(7,13),$ cf. Remark below. The first $2$ have obvious solutions $,color{#c00}{bf 1},$ and $,color{#0a0}{-1},$ so you need only solve the $(1,-1)$ case, then note $(-1,1)equiv -(1,-1)$ is its negative, i.e. $,xequiv 1pmod{!7},,xequiv -1pmod{!13},Rightarrow,-xequiv -1pmod{!7}, {-}xequiv 1pmod{!13}$
Remark $ $ For more complex examples it is usually easier to solve the CRT system first for generic (symbolic) roots, then plug in the specific root values for all combinations, e.g. see here and here.
If $,m,n,$ are coprime then, by CRT, solving a polynomial $,f(x)equiv 0pmod{!mn},$ is equivalent to solving $,f(x)equiv 0,$ mod $,m,$ and mod $,n.,$ By CRT, each combination of a root $,r_ibmod m,$ and a root $,s_jbmod n,$ corresponds to a unique root $,t_{ij}bmod mn,,$ i.e.
$$begin{eqnarray} f(x)equiv 0!!!pmod{!mn}&overset{,,rm CRT}iff& begin{array}{}f(x)equiv 0pmod{! m}\f(x)equiv 0pmod{! n}end{array} \
&,,iff& begin{array}{}xequiv r_1,ldots,r_kpmod{! m}phantom{I^{I^{I^I}}}\xequiv s_1,ldots,s_ellpmod{! n}end{array}\
&,,iff& left{ begin{array}{}xequiv r_ipmod{! m}\xequiv s_jpmod {! n}end{array} right}_{begin{array}{}1le ile k\ 1le jleellend{array}}^{phantom{I^{I^{I^I}}}}\
&overset{,,rm CRT}iff& left{ xequiv t_{i j}!!pmod{!mn} right}_{begin{array}{}1le ile k\ 1le jleellend{array}}\
end{eqnarray}qquadqquad$$
answered Dec 3 '16 at 3:59
Bill DubuqueBill Dubuque
211k29193646
edited Jan 25 at 15:29
answered Dec 3 '16 at 3:59
Bill DubuqueBill Dubuque
211k29193646
answered Dec 3 '16 at 3:59
Bill DubuqueBill Dubuque
211k29193646
answered Dec 3 '16 at 3:59
Bill DubuqueBill Dubuque
211k29193646
211k29193646
add a comment |
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%2f2041254%2ffind-all-solutions-to-x2-equiv-1-pmod-91%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
$begingroup$
Hint: CRT. See link
$endgroup$
– user160069
Dec 3 '16 at 2:38