Mixing
Congruent solution implies an integer solution.
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Let us consider a polynomial $pin mathbbQ[x]$ with $p(mathbbZ)subseteq mathbbZ$, such that for each $ain mathbbN,,p(n)equiv 0 ,(text mod a,) $ has a solution for some $nin mathbbZ.$
Does this imply $p(n)=0$ for some $nin mathbbZ$ ?
Thanks in advance for any help.
number-theory modular-arithmetic polynomial-congruences
asked Jul 26 at 21:01
Tomath
1306
add a comment |Â
up vote
1
down vote
favorite
Let us consider a polynomial $pin mathbbQ[x]$ with $p(mathbbZ)subseteq mathbbZ$, such that for each $ain mathbbN,,p(n)equiv 0 ,(text mod a,) $ has a solution for some $nin mathbbZ.$
Does this imply $p(n)=0$ for some $nin mathbbZ$ ?
Thanks in advance for any help.
number-theory modular-arithmetic polynomial-congruences
asked Jul 26 at 21:01
Tomath
1306
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Let us consider a polynomial $pin mathbbQ[x]$ with $p(mathbbZ)subseteq mathbbZ$, such that for each $ain mathbbN,,p(n)equiv 0 ,(text mod a,) $ has a solution for some $nin mathbbZ.$
Does this imply $p(n)=0$ for some $nin mathbbZ$ ?
Thanks in advance for any help.
number-theory modular-arithmetic polynomial-congruences
asked Jul 26 at 21:01
Tomath
1306
Let us consider a polynomial $pin mathbbQ[x]$ with $p(mathbbZ)subseteq mathbbZ$, such that for each $ain mathbbN,,p(n)equiv 0 ,(text mod a,) $ has a solution for some $nin mathbbZ.$
Does this imply $p(n)=0$ for some $nin mathbbZ$ ?
Thanks in advance for any help.
number-theory modular-arithmetic polynomial-congruences
asked Jul 26 at 21:01
Tomath
1306
asked Jul 26 at 21:01
Tomath
1306
asked Jul 26 at 21:01
Tomath
1306
asked Jul 26 at 21:01
Tomath
1306
1306
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
accepted
I claim that $f(x) = (x^3-3)(x^2-2)(x^2+2)(x^2+1)$ is a counterexample: for any nonzero integer $a$, we have $a mid f(n)$ for some $n in mathbbZ$. However, it is clear that $f(n) ne 0$ for all $n in mathbbZ$.
First, by the Chinese Remainder Theorem, it suffices to prove this in cases where $a$ is a prime power. Now, if $a = p$ is an odd prime, then at least one of $-1, 2, -2$ must be a quadratic residue $pmodp$ since $-2 = (-1) cdot 2$. Then, for example, if $n^2 equiv -2 pmodp$, then $p mid n^2+2$ so $p mid f(n)$; and similarly for the other cases. Now for example if $n^2 + 2 equiv 0 pmodp$, then in particular since $p$ is odd we have $2n notequiv 0 pmodp$; therefore, by Hensel's lemma, for each $m > 0$ that implies that there exists $n' equiv n pmodp$ such that $(n')^2 + 2 equiv 0 pmodp^m$. This proves what we wanted in cases where $a$ is an odd prime power.
All that remains is to show the case $a = 2^m$. However, here the $x^3-3$ factor comes into play: set $g(x) = x^3 - 3$. Then since $g(1) = -2 equiv 0 pmod2$ and $g'(1) = 3 notequiv 0 pmod2$, again by Hensel's lemma we get that for each $m$, there exists $n' equiv 1 pmod2$ such that $g(n') equiv 0 pmod2^m$, finishing the proof.
answered Jul 26 at 21:33
Daniel Schepler
6,6681513
1
Come to think of it, $(2x-1)(3x-1)$ should also work: if $a$ is a prime power, then at least one of 2 or 3 has a multiplicative inverse $pmoda$. The initial example has the advantages of being monic and of not even having any rational roots, though.
– Daniel Schepler
Jul 27 at 17:01
Hi, Daniel. Sorry to be late. Thanks for yours answer. But, I didn't get one part, i,e; how does it suffices to prove the result in case where $a$ is a prime power. Please allow me to explain. If $a in mathbbN$, then by UFT, $a=a_1 a_2 ...a_m$ for some $m in mathbbN$, where each $a_i$'s are prime power and coprime to each other. Now by CRT, if we have $f(n) equiv 0 (text mod a_i)$ has solution for some $n in mathbbN$, then there exists some integer $x$ such that $x equiv 0 (text mod a)$. But my confusion is that how can we say that $x$ is of the form $f(n)$?
– Tomath
Aug 1 at 19:06
1
Choose $n_1$ such that $f(n_1) equiv 0 pmoda_1$, and choose $n_2$ such that $f(n_2) equiv 0 pmoda_2$, etc. Now, choose $n$ such that $n equiv n_1 pmoda_1$, $n equiv n_2 pmoda_2$, etc. Then $f(n) equiv f(n_1) equiv 0 pmoda_1$, $f(n) equiv f(n_2) equiv 0 pmoda_2$, etc.
– Daniel Schepler
Aug 1 at 19:13
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
I claim that $f(x) = (x^3-3)(x^2-2)(x^2+2)(x^2+1)$ is a counterexample: for any nonzero integer $a$, we have $a mid f(n)$ for some $n in mathbbZ$. However, it is clear that $f(n) ne 0$ for all $n in mathbbZ$.
First, by the Chinese Remainder Theorem, it suffices to prove this in cases where $a$ is a prime power. Now, if $a = p$ is an odd prime, then at least one of $-1, 2, -2$ must be a quadratic residue $pmodp$ since $-2 = (-1) cdot 2$. Then, for example, if $n^2 equiv -2 pmodp$, then $p mid n^2+2$ so $p mid f(n)$; and similarly for the other cases. Now for example if $n^2 + 2 equiv 0 pmodp$, then in particular since $p$ is odd we have $2n notequiv 0 pmodp$; therefore, by Hensel's lemma, for each $m > 0$ that implies that there exists $n' equiv n pmodp$ such that $(n')^2 + 2 equiv 0 pmodp^m$. This proves what we wanted in cases where $a$ is an odd prime power.
All that remains is to show the case $a = 2^m$. However, here the $x^3-3$ factor comes into play: set $g(x) = x^3 - 3$. Then since $g(1) = -2 equiv 0 pmod2$ and $g'(1) = 3 notequiv 0 pmod2$, again by Hensel's lemma we get that for each $m$, there exists $n' equiv 1 pmod2$ such that $g(n') equiv 0 pmod2^m$, finishing the proof.
answered Jul 26 at 21:33
Daniel Schepler
6,6681513
1
Come to think of it, $(2x-1)(3x-1)$ should also work: if $a$ is a prime power, then at least one of 2 or 3 has a multiplicative inverse $pmoda$. The initial example has the advantages of being monic and of not even having any rational roots, though.
– Daniel Schepler
Jul 27 at 17:01
Hi, Daniel. Sorry to be late. Thanks for yours answer. But, I didn't get one part, i,e; how does it suffices to prove the result in case where $a$ is a prime power. Please allow me to explain. If $a in mathbbN$, then by UFT, $a=a_1 a_2 ...a_m$ for some $m in mathbbN$, where each $a_i$'s are prime power and coprime to each other. Now by CRT, if we have $f(n) equiv 0 (text mod a_i)$ has solution for some $n in mathbbN$, then there exists some integer $x$ such that $x equiv 0 (text mod a)$. But my confusion is that how can we say that $x$ is of the form $f(n)$?
– Tomath
Aug 1 at 19:06
1
Choose $n_1$ such that $f(n_1) equiv 0 pmoda_1$, and choose $n_2$ such that $f(n_2) equiv 0 pmoda_2$, etc. Now, choose $n$ such that $n equiv n_1 pmoda_1$, $n equiv n_2 pmoda_2$, etc. Then $f(n) equiv f(n_1) equiv 0 pmoda_1$, $f(n) equiv f(n_2) equiv 0 pmoda_2$, etc.
– Daniel Schepler
Aug 1 at 19:13
add a comment |Â
up vote
2
down vote
accepted
I claim that $f(x) = (x^3-3)(x^2-2)(x^2+2)(x^2+1)$ is a counterexample: for any nonzero integer $a$, we have $a mid f(n)$ for some $n in mathbbZ$. However, it is clear that $f(n) ne 0$ for all $n in mathbbZ$.
First, by the Chinese Remainder Theorem, it suffices to prove this in cases where $a$ is a prime power. Now, if $a = p$ is an odd prime, then at least one of $-1, 2, -2$ must be a quadratic residue $pmodp$ since $-2 = (-1) cdot 2$. Then, for example, if $n^2 equiv -2 pmodp$, then $p mid n^2+2$ so $p mid f(n)$; and similarly for the other cases. Now for example if $n^2 + 2 equiv 0 pmodp$, then in particular since $p$ is odd we have $2n notequiv 0 pmodp$; therefore, by Hensel's lemma, for each $m > 0$ that implies that there exists $n' equiv n pmodp$ such that $(n')^2 + 2 equiv 0 pmodp^m$. This proves what we wanted in cases where $a$ is an odd prime power.
All that remains is to show the case $a = 2^m$. However, here the $x^3-3$ factor comes into play: set $g(x) = x^3 - 3$. Then since $g(1) = -2 equiv 0 pmod2$ and $g'(1) = 3 notequiv 0 pmod2$, again by Hensel's lemma we get that for each $m$, there exists $n' equiv 1 pmod2$ such that $g(n') equiv 0 pmod2^m$, finishing the proof.
answered Jul 26 at 21:33
Daniel Schepler
6,6681513
1
Come to think of it, $(2x-1)(3x-1)$ should also work: if $a$ is a prime power, then at least one of 2 or 3 has a multiplicative inverse $pmoda$. The initial example has the advantages of being monic and of not even having any rational roots, though.
– Daniel Schepler
Jul 27 at 17:01
Hi, Daniel. Sorry to be late. Thanks for yours answer. But, I didn't get one part, i,e; how does it suffices to prove the result in case where $a$ is a prime power. Please allow me to explain. If $a in mathbbN$, then by UFT, $a=a_1 a_2 ...a_m$ for some $m in mathbbN$, where each $a_i$'s are prime power and coprime to each other. Now by CRT, if we have $f(n) equiv 0 (text mod a_i)$ has solution for some $n in mathbbN$, then there exists some integer $x$ such that $x equiv 0 (text mod a)$. But my confusion is that how can we say that $x$ is of the form $f(n)$?
– Tomath
Aug 1 at 19:06
1
Choose $n_1$ such that $f(n_1) equiv 0 pmoda_1$, and choose $n_2$ such that $f(n_2) equiv 0 pmoda_2$, etc. Now, choose $n$ such that $n equiv n_1 pmoda_1$, $n equiv n_2 pmoda_2$, etc. Then $f(n) equiv f(n_1) equiv 0 pmoda_1$, $f(n) equiv f(n_2) equiv 0 pmoda_2$, etc.
– Daniel Schepler
Aug 1 at 19:13
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
I claim that $f(x) = (x^3-3)(x^2-2)(x^2+2)(x^2+1)$ is a counterexample: for any nonzero integer $a$, we have $a mid f(n)$ for some $n in mathbbZ$. However, it is clear that $f(n) ne 0$ for all $n in mathbbZ$.
First, by the Chinese Remainder Theorem, it suffices to prove this in cases where $a$ is a prime power. Now, if $a = p$ is an odd prime, then at least one of $-1, 2, -2$ must be a quadratic residue $pmodp$ since $-2 = (-1) cdot 2$. Then, for example, if $n^2 equiv -2 pmodp$, then $p mid n^2+2$ so $p mid f(n)$; and similarly for the other cases. Now for example if $n^2 + 2 equiv 0 pmodp$, then in particular since $p$ is odd we have $2n notequiv 0 pmodp$; therefore, by Hensel's lemma, for each $m > 0$ that implies that there exists $n' equiv n pmodp$ such that $(n')^2 + 2 equiv 0 pmodp^m$. This proves what we wanted in cases where $a$ is an odd prime power.
All that remains is to show the case $a = 2^m$. However, here the $x^3-3$ factor comes into play: set $g(x) = x^3 - 3$. Then since $g(1) = -2 equiv 0 pmod2$ and $g'(1) = 3 notequiv 0 pmod2$, again by Hensel's lemma we get that for each $m$, there exists $n' equiv 1 pmod2$ such that $g(n') equiv 0 pmod2^m$, finishing the proof.
answered Jul 26 at 21:33
Daniel Schepler
6,6681513
I claim that $f(x) = (x^3-3)(x^2-2)(x^2+2)(x^2+1)$ is a counterexample: for any nonzero integer $a$, we have $a mid f(n)$ for some $n in mathbbZ$. However, it is clear that $f(n) ne 0$ for all $n in mathbbZ$.
First, by the Chinese Remainder Theorem, it suffices to prove this in cases where $a$ is a prime power. Now, if $a = p$ is an odd prime, then at least one of $-1, 2, -2$ must be a quadratic residue $pmodp$ since $-2 = (-1) cdot 2$. Then, for example, if $n^2 equiv -2 pmodp$, then $p mid n^2+2$ so $p mid f(n)$; and similarly for the other cases. Now for example if $n^2 + 2 equiv 0 pmodp$, then in particular since $p$ is odd we have $2n notequiv 0 pmodp$; therefore, by Hensel's lemma, for each $m > 0$ that implies that there exists $n' equiv n pmodp$ such that $(n')^2 + 2 equiv 0 pmodp^m$. This proves what we wanted in cases where $a$ is an odd prime power.
All that remains is to show the case $a = 2^m$. However, here the $x^3-3$ factor comes into play: set $g(x) = x^3 - 3$. Then since $g(1) = -2 equiv 0 pmod2$ and $g'(1) = 3 notequiv 0 pmod2$, again by Hensel's lemma we get that for each $m$, there exists $n' equiv 1 pmod2$ such that $g(n') equiv 0 pmod2^m$, finishing the proof.
answered Jul 26 at 21:33
Daniel Schepler
6,6681513
answered Jul 26 at 21:33
Daniel Schepler
6,6681513
answered Jul 26 at 21:33
Daniel Schepler
6,6681513
answered Jul 26 at 21:33
Daniel Schepler
6,6681513
6,6681513
1
Come to think of it, $(2x-1)(3x-1)$ should also work: if $a$ is a prime power, then at least one of 2 or 3 has a multiplicative inverse $pmoda$. The initial example has the advantages of being monic and of not even having any rational roots, though.
– Daniel Schepler
Jul 27 at 17:01
Hi, Daniel. Sorry to be late. Thanks for yours answer. But, I didn't get one part, i,e; how does it suffices to prove the result in case where $a$ is a prime power. Please allow me to explain. If $a in mathbbN$, then by UFT, $a=a_1 a_2 ...a_m$ for some $m in mathbbN$, where each $a_i$'s are prime power and coprime to each other. Now by CRT, if we have $f(n) equiv 0 (text mod a_i)$ has solution for some $n in mathbbN$, then there exists some integer $x$ such that $x equiv 0 (text mod a)$. But my confusion is that how can we say that $x$ is of the form $f(n)$?
– Tomath
Aug 1 at 19:06
1
Choose $n_1$ such that $f(n_1) equiv 0 pmoda_1$, and choose $n_2$ such that $f(n_2) equiv 0 pmoda_2$, etc. Now, choose $n$ such that $n equiv n_1 pmoda_1$, $n equiv n_2 pmoda_2$, etc. Then $f(n) equiv f(n_1) equiv 0 pmoda_1$, $f(n) equiv f(n_2) equiv 0 pmoda_2$, etc.
– Daniel Schepler
Aug 1 at 19:13
add a comment |Â
1
Come to think of it, $(2x-1)(3x-1)$ should also work: if $a$ is a prime power, then at least one of 2 or 3 has a multiplicative inverse $pmoda$. The initial example has the advantages of being monic and of not even having any rational roots, though.
– Daniel Schepler
Jul 27 at 17:01
Hi, Daniel. Sorry to be late. Thanks for yours answer. But, I didn't get one part, i,e; how does it suffices to prove the result in case where $a$ is a prime power. Please allow me to explain. If $a in mathbbN$, then by UFT, $a=a_1 a_2 ...a_m$ for some $m in mathbbN$, where each $a_i$'s are prime power and coprime to each other. Now by CRT, if we have $f(n) equiv 0 (text mod a_i)$ has solution for some $n in mathbbN$, then there exists some integer $x$ such that $x equiv 0 (text mod a)$. But my confusion is that how can we say that $x$ is of the form $f(n)$?
– Tomath
Aug 1 at 19:06
1
Choose $n_1$ such that $f(n_1) equiv 0 pmoda_1$, and choose $n_2$ such that $f(n_2) equiv 0 pmoda_2$, etc. Now, choose $n$ such that $n equiv n_1 pmoda_1$, $n equiv n_2 pmoda_2$, etc. Then $f(n) equiv f(n_1) equiv 0 pmoda_1$, $f(n) equiv f(n_2) equiv 0 pmoda_2$, etc.
– Daniel Schepler
Aug 1 at 19:13
1
1
Come to think of it, $(2x-1)(3x-1)$ should also work: if $a$ is a prime power, then at least one of 2 or 3 has a multiplicative inverse $pmoda$. The initial example has the advantages of being monic and of not even having any rational roots, though.
– Daniel Schepler
Jul 27 at 17:01
Come to think of it, $(2x-1)(3x-1)$ should also work: if $a$ is a prime power, then at least one of 2 or 3 has a multiplicative inverse $pmoda$. The initial example has the advantages of being monic and of not even having any rational roots, though.
– Daniel Schepler
Jul 27 at 17:01
Hi, Daniel. Sorry to be late. Thanks for yours answer. But, I didn't get one part, i,e; how does it suffices to prove the result in case where $a$ is a prime power. Please allow me to explain. If $a in mathbbN$, then by UFT, $a=a_1 a_2 ...a_m$ for some $m in mathbbN$, where each $a_i$'s are prime power and coprime to each other. Now by CRT, if we have $f(n) equiv 0 (text mod a_i)$ has solution for some $n in mathbbN$, then there exists some integer $x$ such that $x equiv 0 (text mod a)$. But my confusion is that how can we say that $x$ is of the form $f(n)$?
– Tomath
Aug 1 at 19:06
Hi, Daniel. Sorry to be late. Thanks for yours answer. But, I didn't get one part, i,e; how does it suffices to prove the result in case where $a$ is a prime power. Please allow me to explain. If $a in mathbbN$, then by UFT, $a=a_1 a_2 ...a_m$ for some $m in mathbbN$, where each $a_i$'s are prime power and coprime to each other. Now by CRT, if we have $f(n) equiv 0 (text mod a_i)$ has solution for some $n in mathbbN$, then there exists some integer $x$ such that $x equiv 0 (text mod a)$. But my confusion is that how can we say that $x$ is of the form $f(n)$?
– Tomath
Aug 1 at 19:06
1
1
Choose $n_1$ such that $f(n_1) equiv 0 pmoda_1$, and choose $n_2$ such that $f(n_2) equiv 0 pmoda_2$, etc. Now, choose $n$ such that $n equiv n_1 pmoda_1$, $n equiv n_2 pmoda_2$, etc. Then $f(n) equiv f(n_1) equiv 0 pmoda_1$, $f(n) equiv f(n_2) equiv 0 pmoda_2$, etc.
– Daniel Schepler
Aug 1 at 19:13
Choose $n_1$ such that $f(n_1) equiv 0 pmoda_1$, and choose $n_2$ such that $f(n_2) equiv 0 pmoda_2$, etc. Now, choose $n$ such that $n equiv n_1 pmoda_1$, $n equiv n_2 pmoda_2$, etc. Then $f(n) equiv f(n_1) equiv 0 pmoda_1$, $f(n) equiv f(n_2) equiv 0 pmoda_2$, etc.
– Daniel Schepler
Aug 1 at 19:13
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2863816%2fcongruent-solution-implies-an-integer-solution%23new-answer', 'question_page');
);
Post as a guest
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
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
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