For a given non-constant polynomial $f(x)$ with integer coefficients, how many solutions are there to...
$begingroup$
For a given non-constant polynomial $f(x)$ with integer coefficients, how many solutions are there to $f(x)equiv 0 mod(n)$ where $n$ is composite?
Is there a general way to determine the number of incongruent solutions modulo $n$?
My first idea is that we can of course break $n$ into its prime power factorization and look at $f(x)equiv 0 mod(p_{i}^{e_{i}})$ where $(p_{i}^{e_{i}})$ appears as a prime power factor in $n$.
Here's where I start to become confused, if $f(x)=x$ then the Chinese remainder theorem tells us that the solution is unique modulo $n$, but if $f(x)$ is non-constant and non-linear then we need to use the lifting method to solve $f(x)equiv 0$ for each $mod(p_{i}^{e_{i}})$ - but so far the method tells us nothing about the number of solutions.
I presume I am not incorrect in saying that the number of incongruent solutions to $f(x)equiv mod(p_{i}^{e_{i}})$ is at most $min(deg(f), p_{i}^{e_{i}})$, but is there a general way to determine precisely how many solutions are there?
abstract-algebra number-theory elementary-number-theory congruences
asked May 5 '16 at 7:29
user162089user162089
211310
$endgroup$
add a comment |
$begingroup$
For a given non-constant polynomial $f(x)$ with integer coefficients, how many solutions are there to $f(x)equiv 0 mod(n)$ where $n$ is composite?
Is there a general way to determine the number of incongruent solutions modulo $n$?
My first idea is that we can of course break $n$ into its prime power factorization and look at $f(x)equiv 0 mod(p_{i}^{e_{i}})$ where $(p_{i}^{e_{i}})$ appears as a prime power factor in $n$.
Here's where I start to become confused, if $f(x)=x$ then the Chinese remainder theorem tells us that the solution is unique modulo $n$, but if $f(x)$ is non-constant and non-linear then we need to use the lifting method to solve $f(x)equiv 0$ for each $mod(p_{i}^{e_{i}})$ - but so far the method tells us nothing about the number of solutions.
I presume I am not incorrect in saying that the number of incongruent solutions to $f(x)equiv mod(p_{i}^{e_{i}})$ is at most $min(deg(f), p_{i}^{e_{i}})$, but is there a general way to determine precisely how many solutions are there?
abstract-algebra number-theory elementary-number-theory congruences
asked May 5 '16 at 7:29
user162089user162089
211310
$endgroup$
$begingroup$
If $f(n)equiv 0pmod4$ has two solutions, and $f(n)equiv 0pmod{25}$ has six solutions, then $f(n)equiv 0pmod{100}$ has twelve solutions. Is that what you're asking?
$endgroup$
– Arthur
May 5 '16 at 7:37
$begingroup$
Essentially yes, but why's that?
$endgroup$
– user162089
May 5 '16 at 7:42
1
$begingroup$
@user162089 because of the Chinese Remainder Theorem
$endgroup$
– Hagen von Eitzen
May 5 '16 at 7:48
$begingroup$
Because every pair $(a,b)$ with $a$ being modulo four and $b$ being modulo $25$ gives a unique residue class $c$ modulo $100$. Also, this pairing respects polynomials, so $(f(a),f(b))$ corresponds to $f(c)$. There are two $a$ for which the polynomial is zero, and six $b$, which makes twelve pairs of solutions.
$endgroup$
– Arthur
May 5 '16 at 7:55
add a comment |
$begingroup$
For a given non-constant polynomial $f(x)$ with integer coefficients, how many solutions are there to $f(x)equiv 0 mod(n)$ where $n$ is composite?
Is there a general way to determine the number of incongruent solutions modulo $n$?
My first idea is that we can of course break $n$ into its prime power factorization and look at $f(x)equiv 0 mod(p_{i}^{e_{i}})$ where $(p_{i}^{e_{i}})$ appears as a prime power factor in $n$.
Here's where I start to become confused, if $f(x)=x$ then the Chinese remainder theorem tells us that the solution is unique modulo $n$, but if $f(x)$ is non-constant and non-linear then we need to use the lifting method to solve $f(x)equiv 0$ for each $mod(p_{i}^{e_{i}})$ - but so far the method tells us nothing about the number of solutions.
I presume I am not incorrect in saying that the number of incongruent solutions to $f(x)equiv mod(p_{i}^{e_{i}})$ is at most $min(deg(f), p_{i}^{e_{i}})$, but is there a general way to determine precisely how many solutions are there?
abstract-algebra number-theory elementary-number-theory congruences
asked May 5 '16 at 7:29
user162089user162089
211310
$endgroup$
For a given non-constant polynomial $f(x)$ with integer coefficients, how many solutions are there to $f(x)equiv 0 mod(n)$ where $n$ is composite?
Is there a general way to determine the number of incongruent solutions modulo $n$?
My first idea is that we can of course break $n$ into its prime power factorization and look at $f(x)equiv 0 mod(p_{i}^{e_{i}})$ where $(p_{i}^{e_{i}})$ appears as a prime power factor in $n$.
Here's where I start to become confused, if $f(x)=x$ then the Chinese remainder theorem tells us that the solution is unique modulo $n$, but if $f(x)$ is non-constant and non-linear then we need to use the lifting method to solve $f(x)equiv 0$ for each $mod(p_{i}^{e_{i}})$ - but so far the method tells us nothing about the number of solutions.
I presume I am not incorrect in saying that the number of incongruent solutions to $f(x)equiv mod(p_{i}^{e_{i}})$ is at most $min(deg(f), p_{i}^{e_{i}})$, but is there a general way to determine precisely how many solutions are there?
abstract-algebra number-theory elementary-number-theory congruences
abstract-algebra number-theory elementary-number-theory congruences
asked May 5 '16 at 7:29
user162089user162089
211310
asked May 5 '16 at 7:29
user162089user162089
211310
asked May 5 '16 at 7:29
user162089user162089
211310
asked May 5 '16 at 7:29
user162089user162089
211310
asked May 5 '16 at 7:29
user162089user162089
211310
211310
$begingroup$
If $f(n)equiv 0pmod4$ has two solutions, and $f(n)equiv 0pmod{25}$ has six solutions, then $f(n)equiv 0pmod{100}$ has twelve solutions. Is that what you're asking?
$endgroup$
– Arthur
May 5 '16 at 7:37
$begingroup$
Essentially yes, but why's that?
$endgroup$
– user162089
May 5 '16 at 7:42
1
$begingroup$
@user162089 because of the Chinese Remainder Theorem
$endgroup$
– Hagen von Eitzen
May 5 '16 at 7:48
$begingroup$
Because every pair $(a,b)$ with $a$ being modulo four and $b$ being modulo $25$ gives a unique residue class $c$ modulo $100$. Also, this pairing respects polynomials, so $(f(a),f(b))$ corresponds to $f(c)$. There are two $a$ for which the polynomial is zero, and six $b$, which makes twelve pairs of solutions.
$endgroup$
– Arthur
May 5 '16 at 7:55
add a comment |
$begingroup$
If $f(n)equiv 0pmod4$ has two solutions, and $f(n)equiv 0pmod{25}$ has six solutions, then $f(n)equiv 0pmod{100}$ has twelve solutions. Is that what you're asking?
$endgroup$
– Arthur
May 5 '16 at 7:37
$begingroup$
Essentially yes, but why's that?
$endgroup$
– user162089
May 5 '16 at 7:42
1
$begingroup$
@user162089 because of the Chinese Remainder Theorem
$endgroup$
– Hagen von Eitzen
May 5 '16 at 7:48
$begingroup$
Because every pair $(a,b)$ with $a$ being modulo four and $b$ being modulo $25$ gives a unique residue class $c$ modulo $100$. Also, this pairing respects polynomials, so $(f(a),f(b))$ corresponds to $f(c)$. There are two $a$ for which the polynomial is zero, and six $b$, which makes twelve pairs of solutions.
$endgroup$
– Arthur
May 5 '16 at 7:55
$begingroup$
If $f(n)equiv 0pmod4$ has two solutions, and $f(n)equiv 0pmod{25}$ has six solutions, then $f(n)equiv 0pmod{100}$ has twelve solutions. Is that what you're asking?
$endgroup$
– Arthur
May 5 '16 at 7:37
$begingroup$
If $f(n)equiv 0pmod4$ has two solutions, and $f(n)equiv 0pmod{25}$ has six solutions, then $f(n)equiv 0pmod{100}$ has twelve solutions. Is that what you're asking?
$endgroup$
– Arthur
May 5 '16 at 7:37
$begingroup$
Essentially yes, but why's that?
$endgroup$
– user162089
May 5 '16 at 7:42
$begingroup$
Essentially yes, but why's that?
$endgroup$
– user162089
May 5 '16 at 7:42
1
1
$begingroup$
@user162089 because of the Chinese Remainder Theorem
$endgroup$
– Hagen von Eitzen
May 5 '16 at 7:48
$begingroup$
@user162089 because of the Chinese Remainder Theorem
$endgroup$
– Hagen von Eitzen
May 5 '16 at 7:48
$begingroup$
Because every pair $(a,b)$ with $a$ being modulo four and $b$ being modulo $25$ gives a unique residue class $c$ modulo $100$. Also, this pairing respects polynomials, so $(f(a),f(b))$ corresponds to $f(c)$. There are two $a$ for which the polynomial is zero, and six $b$, which makes twelve pairs of solutions.
$endgroup$
– Arthur
May 5 '16 at 7:55
$begingroup$
Because every pair $(a,b)$ with $a$ being modulo four and $b$ being modulo $25$ gives a unique residue class $c$ modulo $100$. Also, this pairing respects polynomials, so $(f(a),f(b))$ corresponds to $f(c)$. There are two $a$ for which the polynomial is zero, and six $b$, which makes twelve pairs of solutions.
$endgroup$
– Arthur
May 5 '16 at 7:55
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
First factor $m$ to powers of primes. $$N(m) = PI N(p^a)$$ $N$ is number of roots. This is by CRT.
Then for each prime factor p of m, a polynomial $P(x)$ can be reduced to $P'(x)$ with degree $<= p$. If $P'(x)$ is a factor of $(x^p - x) mod p$ (after dividing, the remainder is multiple of $p$), then it has exactly $n$ roots where $n$ is degree of $P'(x)$.
From $p$ to $p^a$, it's Hensel's Lemma.
edited Dec 6 '18 at 14:44
dantopa
6,44932142
answered Dec 6 '18 at 9:26
james0910james0910
111
$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%2f1772376%2ffor-a-given-non-constant-polynomial-fx-with-integer-coefficients-how-many-s%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$
First factor $m$ to powers of primes. $$N(m) = PI N(p^a)$$ $N$ is number of roots. This is by CRT.
Then for each prime factor p of m, a polynomial $P(x)$ can be reduced to $P'(x)$ with degree $<= p$. If $P'(x)$ is a factor of $(x^p - x) mod p$ (after dividing, the remainder is multiple of $p$), then it has exactly $n$ roots where $n$ is degree of $P'(x)$.
From $p$ to $p^a$, it's Hensel's Lemma.
edited Dec 6 '18 at 14:44
dantopa
6,44932142
answered Dec 6 '18 at 9:26
james0910james0910
111
$endgroup$
add a comment |
$begingroup$
First factor $m$ to powers of primes. $$N(m) = PI N(p^a)$$ $N$ is number of roots. This is by CRT.
Then for each prime factor p of m, a polynomial $P(x)$ can be reduced to $P'(x)$ with degree $<= p$. If $P'(x)$ is a factor of $(x^p - x) mod p$ (after dividing, the remainder is multiple of $p$), then it has exactly $n$ roots where $n$ is degree of $P'(x)$.
From $p$ to $p^a$, it's Hensel's Lemma.
edited Dec 6 '18 at 14:44
dantopa
6,44932142
answered Dec 6 '18 at 9:26
james0910james0910
111
$endgroup$
add a comment |
$begingroup$
First factor $m$ to powers of primes. $$N(m) = PI N(p^a)$$ $N$ is number of roots. This is by CRT.
Then for each prime factor p of m, a polynomial $P(x)$ can be reduced to $P'(x)$ with degree $<= p$. If $P'(x)$ is a factor of $(x^p - x) mod p$ (after dividing, the remainder is multiple of $p$), then it has exactly $n$ roots where $n$ is degree of $P'(x)$.
From $p$ to $p^a$, it's Hensel's Lemma.
edited Dec 6 '18 at 14:44
dantopa
6,44932142
answered Dec 6 '18 at 9:26
james0910james0910
111
$endgroup$
First factor $m$ to powers of primes. $$N(m) = PI N(p^a)$$ $N$ is number of roots. This is by CRT.
Then for each prime factor p of m, a polynomial $P(x)$ can be reduced to $P'(x)$ with degree $<= p$. If $P'(x)$ is a factor of $(x^p - x) mod p$ (after dividing, the remainder is multiple of $p$), then it has exactly $n$ roots where $n$ is degree of $P'(x)$.
From $p$ to $p^a$, it's Hensel's Lemma.
edited Dec 6 '18 at 14:44
dantopa
6,44932142
answered Dec 6 '18 at 9:26
james0910james0910
111
edited Dec 6 '18 at 14:44
dantopa
6,44932142
edited Dec 6 '18 at 14:44
dantopa
6,44932142
edited Dec 6 '18 at 14:44
dantopa
6,44932142
6,44932142
answered Dec 6 '18 at 9:26
james0910james0910
111
answered Dec 6 '18 at 9:26
james0910james0910
111
answered Dec 6 '18 at 9:26
james0910james0910
111
111
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%2f1772376%2ffor-a-given-non-constant-polynomial-fx-with-integer-coefficients-how-many-s%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
$begingroup$
If $f(n)equiv 0pmod4$ has two solutions, and $f(n)equiv 0pmod{25}$ has six solutions, then $f(n)equiv 0pmod{100}$ has twelve solutions. Is that what you're asking?
$endgroup$
– Arthur
May 5 '16 at 7:37
$begingroup$
Essentially yes, but why's that?
$endgroup$
– user162089
May 5 '16 at 7:42
1
$begingroup$
@user162089 because of the Chinese Remainder Theorem
$endgroup$
– Hagen von Eitzen
May 5 '16 at 7:48
$begingroup$
Because every pair $(a,b)$ with $a$ being modulo four and $b$ being modulo $25$ gives a unique residue class $c$ modulo $100$. Also, this pairing respects polynomials, so $(f(a),f(b))$ corresponds to $f(c)$. There are two $a$ for which the polynomial is zero, and six $b$, which makes twelve pairs of solutions.
$endgroup$
– Arthur
May 5 '16 at 7:55