Dtjytyk

How can I fix this gap between bookcases I made?

Draw simple lines in Inkscape

"which" command doesn't work / path of Safari?

Is there a minimum number of transactions in a block?

Simulate Bitwise Cyclic Tag

What is the offset in a seaplane's hull?

I see my dog run

Email Account under attack (really) - anything I can do?

If Manufacturer spice model and Datasheet give different values which should I use?

Can town administrative "code" overule state laws like those forbidding trespassing?

What is the white spray-pattern residue inside these Falcon Heavy nozzles?

How can the DM most effectively choose 1 out of an odd number of players to be targeted by an attack or effect?

Non-Jewish family in an Orthodox Jewish Wedding

How to make payment on the internet without leaving a money trail?

How is the claim "I am in New York only if I am in America" the same as "If I am in New York, then I am in America?

A function which translates a sentence to title-case

Why did the Germans forbid the possession of pet pigeons in Rostov-on-Don in 1941?

Download, install and reboot computer at night if needed

What are these boxed doors outside store fronts in New York?

Why is this code 6.5x slower with optimizations enabled?

Showing the closure of a compact subset need not be compact

How to determine if window is maximised or minimised from bash script

least quadratic residue under GRH: an EXPLICIT bound

How do we improve the relationship with a client software team that performs poorly and is becoming less collaborative?

Polynomial and prime factors

Proof polynomial is always divisible by numberIf $m^4+4^n$ is prime, then $m=n=1$ or $m$ is odd and $n$ evenSolving $p_1^{e_1} p_2^{e_2}…p_k^{e_k}=e_1^{p_1} e_2^{p_2}…e_k^{p_k}$Product of two primitive roots $bmod p$ cannot be a primitive root.How to show that for $n$ sufficiently large, relative to $k$, $(n+1)(n+2) ldots (n+k)$ is divisible by at least $k$ distinct primesI've searched and cannot find this pattern anywhere concerning integers and their factorsFactorization of polynomial with prime coefficientsThe same number of prime factors and decimal digits.distributions of prime numbers - theorem of ChebyshevPrime sequence.Criteria for Leyland Numbers to be Prime

6

2

$begingroup$

So I've been thinking about this questions for ages but I haven't made any progress on it.

I need to prove that for every $f(X) in mathbb{Z}[X]$ with $f(0) = 1$, there exists a $n in mathbb{Z}$ such that $f(n)$ is divisible by at least 2019 distinct primes.

The only thing that I've seen is that this is easy to show when $f(X)$ has a root in $mathbb{Z}$ but for the rest I haven't made any progress?

Does anyone know how I can solve this?

number-theory polynomials prime-numbers

share|cite|improve this question

asked Mar 20 at 13:36

Mee98Mee98

322110

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Perhaps induction on the degree of the polynomial? You'd need to assume that the degree is at least one, of course.
  $endgroup$
  – Gary Moon
  Mar 20 at 13:42
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Perhaps the answer there will help you: math.stackexchange.com/questions/601526/…
  $endgroup$
  – B.Swan
  Mar 20 at 14:37
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I don't really see how that answer can help me? Like, I don't know which primes divide my function divides and they also don't need to be the same for every value?
  $endgroup$
  – Mee98
  Mar 20 at 14:46
  

  
  
  
  

add a comment | 

6

2

$begingroup$

So I've been thinking about this questions for ages but I haven't made any progress on it.

I need to prove that for every $f(X) in mathbb{Z}[X]$ with $f(0) = 1$, there exists a $n in mathbb{Z}$ such that $f(n)$ is divisible by at least 2019 distinct primes.

The only thing that I've seen is that this is easy to show when $f(X)$ has a root in $mathbb{Z}$ but for the rest I haven't made any progress?

Does anyone know how I can solve this?

number-theory polynomials prime-numbers

share|cite|improve this question

asked Mar 20 at 13:36

Mee98Mee98

322110

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Perhaps induction on the degree of the polynomial? You'd need to assume that the degree is at least one, of course.
  $endgroup$
  – Gary Moon
  Mar 20 at 13:42
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Perhaps the answer there will help you: math.stackexchange.com/questions/601526/…
  $endgroup$
  – B.Swan
  Mar 20 at 14:37
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I don't really see how that answer can help me? Like, I don't know which primes divide my function divides and they also don't need to be the same for every value?
  $endgroup$
  – Mee98
  Mar 20 at 14:46
  

  
  
  
  

add a comment | 

$begingroup$

So I've been thinking about this questions for ages but I haven't made any progress on it.

I need to prove that for every $f(X) in mathbb{Z}[X]$ with $f(0) = 1$, there exists a $n in mathbb{Z}$ such that $f(n)$ is divisible by at least 2019 distinct primes.

The only thing that I've seen is that this is easy to show when $f(X)$ has a root in $mathbb{Z}$ but for the rest I haven't made any progress?

Does anyone know how I can solve this?

number-theory polynomials prime-numbers

share|cite|improve this question

asked Mar 20 at 13:36

Mee98Mee98

322110

$endgroup$

share|cite|improve this question

asked Mar 20 at 13:36

Mee98Mee98

322110

share|cite|improve this question

asked Mar 20 at 13:36

Mee98Mee98

322110

asked Mar 20 at 13:36

Mee98Mee98

322110

asked Mar 20 at 13:36

Mee98Mee98

322110

1 Answer
1

active

oldest

votes

7

$begingroup$

Suppose you know $f(x)$ has a root $r_i$ modulo a prime $p_i$, for $m$ different such primes.

Let $P_m$ be the product of the $m$ primes.

Then since $f(0) = 1$, this tells you that
$$
f(kP_m) equiv 1notequiv 0 pmod{ p_i}
$$
for any integer $k$. So none of the existing $m$ primes divide this.

By choosing $k$ large enough, this is not zero (since a polynomial only have finitely many roots) and therefore it must have a prime factor $p_{m+1}$ not the same as the current $m$ you have found. Thus you get a new root $kP_m$ and prime $p_{m+1}$. i.e.
$$
f(kP_m) equiv 0 pmod{p_{m+1}}
$$

So you can find solution to
$$
f(r_i) equiv 0 pmod{p_i}
$$
for arbitrarily many primes $p_i$.

Finally, you can use Chinese Remainder Theorem to find a common root $r$ for all these primes. So that $f(r)$ will be divisible by each of the $p_i$.

share|cite|improve this answer

answered Mar 20 at 15:08

Yong Hao NgYong Hao Ng

3,7191222

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  How exactly can you use the Chinese Remainder Theorem in the last step?
  $endgroup$
  – Mee98
  Mar 20 at 16:29
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Mee98 The CRT system to solve is $$r equiv r_i pmod{p_i},$$ since if $r_i$ is a root mod $p_i$, then any $r equiv r_i pmod{p_i}$ is also a root. Alternatively, if we have $f(r) equiv 0pmod A, f(s) equiv 0pmod B$ then we can set $k equiv (s-r)A^{-1}pmod B$ to get $$f(r+kA)equiv 0 pmod{AB}$$, then repeat. (Adding one prime at a time to the product.)
  $endgroup$
  – Yong Hao Ng
  Mar 20 at 16:45
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  which works since $$f(r+ kA)equiv f(r)equiv 0 pmod A$$ and $$f(r+kA) equiv f(r + (s-r)A^{-1}A) equiv f(r +(s-r))equiv f(s) equiv 0pmod B$$So divisible by $A$ and $B$ means divisible by $AB$.
  $endgroup$
  – Yong Hao Ng
  Mar 20 at 16:50
  

  
  
  
  

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
});


}
});

draft saved

draft discarded

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

Name

Email

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3155458%2fpolynomial-and-prime-factors%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

7

$begingroup$

Suppose you know $f(x)$ has a root $r_i$ modulo a prime $p_i$, for $m$ different such primes.

Let $P_m$ be the product of the $m$ primes.

Then since $f(0) = 1$, this tells you that
$$
f(kP_m) equiv 1notequiv 0 pmod{ p_i}
$$
for any integer $k$. So none of the existing $m$ primes divide this.

By choosing $k$ large enough, this is not zero (since a polynomial only have finitely many roots) and therefore it must have a prime factor $p_{m+1}$ not the same as the current $m$ you have found. Thus you get a new root $kP_m$ and prime $p_{m+1}$. i.e.
$$
f(kP_m) equiv 0 pmod{p_{m+1}}
$$

So you can find solution to
$$
f(r_i) equiv 0 pmod{p_i}
$$
for arbitrarily many primes $p_i$.

Finally, you can use Chinese Remainder Theorem to find a common root $r$ for all these primes. So that $f(r)$ will be divisible by each of the $p_i$.

share|cite|improve this answer

answered Mar 20 at 15:08

Yong Hao NgYong Hao Ng

3,7191222

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  How exactly can you use the Chinese Remainder Theorem in the last step?
  $endgroup$
  – Mee98
  Mar 20 at 16:29
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Mee98 The CRT system to solve is $$r equiv r_i pmod{p_i},$$ since if $r_i$ is a root mod $p_i$, then any $r equiv r_i pmod{p_i}$ is also a root. Alternatively, if we have $f(r) equiv 0pmod A, f(s) equiv 0pmod B$ then we can set $k equiv (s-r)A^{-1}pmod B$ to get $$f(r+kA)equiv 0 pmod{AB}$$, then repeat. (Adding one prime at a time to the product.)
  $endgroup$
  – Yong Hao Ng
  Mar 20 at 16:45
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  which works since $$f(r+ kA)equiv f(r)equiv 0 pmod A$$ and $$f(r+kA) equiv f(r + (s-r)A^{-1}A) equiv f(r +(s-r))equiv f(s) equiv 0pmod B$$So divisible by $A$ and $B$ means divisible by $AB$.
  $endgroup$
  – Yong Hao Ng
  Mar 20 at 16:50
  

  
  
  
  

add a comment | 

7

$begingroup$

Suppose you know $f(x)$ has a root $r_i$ modulo a prime $p_i$, for $m$ different such primes.

Let $P_m$ be the product of the $m$ primes.

Then since $f(0) = 1$, this tells you that
$$
f(kP_m) equiv 1notequiv 0 pmod{ p_i}
$$
for any integer $k$. So none of the existing $m$ primes divide this.

By choosing $k$ large enough, this is not zero (since a polynomial only have finitely many roots) and therefore it must have a prime factor $p_{m+1}$ not the same as the current $m$ you have found. Thus you get a new root $kP_m$ and prime $p_{m+1}$. i.e.
$$
f(kP_m) equiv 0 pmod{p_{m+1}}
$$

So you can find solution to
$$
f(r_i) equiv 0 pmod{p_i}
$$
for arbitrarily many primes $p_i$.

Finally, you can use Chinese Remainder Theorem to find a common root $r$ for all these primes. So that $f(r)$ will be divisible by each of the $p_i$.

share|cite|improve this answer

answered Mar 20 at 15:08

Yong Hao NgYong Hao Ng

3,7191222

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  How exactly can you use the Chinese Remainder Theorem in the last step?
  $endgroup$
  – Mee98
  Mar 20 at 16:29
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Mee98 The CRT system to solve is $$r equiv r_i pmod{p_i},$$ since if $r_i$ is a root mod $p_i$, then any $r equiv r_i pmod{p_i}$ is also a root. Alternatively, if we have $f(r) equiv 0pmod A, f(s) equiv 0pmod B$ then we can set $k equiv (s-r)A^{-1}pmod B$ to get $$f(r+kA)equiv 0 pmod{AB}$$, then repeat. (Adding one prime at a time to the product.)
  $endgroup$
  – Yong Hao Ng
  Mar 20 at 16:45
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  which works since $$f(r+ kA)equiv f(r)equiv 0 pmod A$$ and $$f(r+kA) equiv f(r + (s-r)A^{-1}A) equiv f(r +(s-r))equiv f(s) equiv 0pmod B$$So divisible by $A$ and $B$ means divisible by $AB$.
  $endgroup$
  – Yong Hao Ng
  Mar 20 at 16:50
  

  
  
  
  

add a comment | 

$begingroup$

Suppose you know $f(x)$ has a root $r_i$ modulo a prime $p_i$, for $m$ different such primes.

Let $P_m$ be the product of the $m$ primes.

Then since $f(0) = 1$, this tells you that
$$
f(kP_m) equiv 1notequiv 0 pmod{ p_i}
$$
for any integer $k$. So none of the existing $m$ primes divide this.

By choosing $k$ large enough, this is not zero (since a polynomial only have finitely many roots) and therefore it must have a prime factor $p_{m+1}$ not the same as the current $m$ you have found. Thus you get a new root $kP_m$ and prime $p_{m+1}$. i.e.
$$
f(kP_m) equiv 0 pmod{p_{m+1}}
$$

So you can find solution to
$$
f(r_i) equiv 0 pmod{p_i}
$$
for arbitrarily many primes $p_i$.

Finally, you can use Chinese Remainder Theorem to find a common root $r$ for all these primes. So that $f(r)$ will be divisible by each of the $p_i$.

share|cite|improve this answer

answered Mar 20 at 15:08

Yong Hao NgYong Hao Ng

3,7191222

$endgroup$

share|cite|improve this answer

answered Mar 20 at 15:08

Yong Hao NgYong Hao Ng

3,7191222

answered Mar 20 at 15:08

Yong Hao NgYong Hao Ng

3,7191222

answered Mar 20 at 15:08

Yong Hao NgYong Hao Ng

3,7191222