Mrthdrb

How can ping know if my host is down

Why should universal income be universal?

When were female captains banned from Starfleet?

Taxes on Dividends in a Roth IRA

Is there a RAID 0 Equivalent for RAM?

Quoting Keynes in a lecture

How do I tell my boss that I'm quitting soon, especially given that a colleague just left this week

Why can't the Brexit deadlock in the UK parliament be solved with a plurality vote?

A Trivial Diagnosis

Which Article Helped Get Rid of Technobabble in RPGs?

Can I cause damage to electrical appliances by unplugging them when they are turned on?

How does electrical safety system work on ISS?

Make a Bowl of Alphabet Soup

Why does Carol not get rid of the Kree symbol on her suit when she changes its colours?

Microchip documentation does not label CAN buss pins on micro controller pinout diagram

Are Captain Marvel's powers affected by Thanos breaking the Tesseract and claiming the stone?

What is the highest possible scrabble score for placing a single tile

What's the name of the logical fallacy where a debater extends a statement far beyond the original statement to make it true?

Is there a nicer/politer/more positive alternative for "negates"?

How could a planet have erratic days?

How to preserve electronics (computers, iPads and phones) for hundreds of years

Stack Interview Code methods made from class Node and Smart Pointers

What fields between the rationals and the reals allow a good notion of 2D distance?

Did the UK lift the requirement for registering SIM cards?

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 mathbbZ[X]$ with $f(0) = 1$, there exists a $n in mathbbZ$ 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 $mathbbZ$ 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 yesterday

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
  yesterday
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Perhaps the answer there will help you: math.stackexchange.com/questions/601526/…
  $endgroup$
  – B.Swan
  yesterday
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  yesterday
  

  
  
  
  

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 mathbbZ[X]$ with $f(0) = 1$, there exists a $n in mathbbZ$ 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 $mathbbZ$ 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 yesterday

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
  yesterday
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Perhaps the answer there will help you: math.stackexchange.com/questions/601526/…
  $endgroup$
  – B.Swan
  yesterday
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  yesterday
  

  
  
  
  

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 mathbbZ[X]$ with $f(0) = 1$, there exists a $n in mathbbZ$ 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 $mathbbZ$ 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 yesterday

Mee98Mee98

322110

$endgroup$

share|cite|improve this question

asked yesterday

Mee98Mee98

322110

share|cite|improve this question

asked yesterday

Mee98Mee98

322110

asked yesterday

Mee98Mee98

322110

asked yesterday

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 pmodp_m+1
$$

So you can find solution to
$$
f(r_i) equiv 0 pmodp_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 yesterday

Yong Hao NgYong Hao Ng

3,7091222

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  How exactly can you use the Chinese Remainder Theorem in the last step?
  $endgroup$
  – Mee98
  yesterday
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Mee98 The CRT system to solve is $$r equiv r_i pmodp_i,$$ since if $r_i$ is a root mod $p_i$, then any $r equiv r_i pmodp_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^-1pmod B$ to get $$f(r+kA)equiv 0 pmodAB$$, then repeat. (Adding one prime at a time to the product.)
  $endgroup$
  – Yong Hao Ng
  yesterday
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  which works since $$f(r+ kA)equiv f(r)equiv 0 pmod A$$ and $$f(r+kA) equiv f(r + (s-r)A^-1A) 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
  yesterday
  

  
  
  
  

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 pmodp_m+1
$$

So you can find solution to
$$
f(r_i) equiv 0 pmodp_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 yesterday

Yong Hao NgYong Hao Ng

3,7091222

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  How exactly can you use the Chinese Remainder Theorem in the last step?
  $endgroup$
  – Mee98
  yesterday
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Mee98 The CRT system to solve is $$r equiv r_i pmodp_i,$$ since if $r_i$ is a root mod $p_i$, then any $r equiv r_i pmodp_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^-1pmod B$ to get $$f(r+kA)equiv 0 pmodAB$$, then repeat. (Adding one prime at a time to the product.)
  $endgroup$
  – Yong Hao Ng
  yesterday
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  which works since $$f(r+ kA)equiv f(r)equiv 0 pmod A$$ and $$f(r+kA) equiv f(r + (s-r)A^-1A) 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
  yesterday
  

  
  
  
  

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 pmodp_m+1
$$

So you can find solution to
$$
f(r_i) equiv 0 pmodp_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 yesterday

Yong Hao NgYong Hao Ng

3,7091222

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  How exactly can you use the Chinese Remainder Theorem in the last step?
  $endgroup$
  – Mee98
  yesterday
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Mee98 The CRT system to solve is $$r equiv r_i pmodp_i,$$ since if $r_i$ is a root mod $p_i$, then any $r equiv r_i pmodp_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^-1pmod B$ to get $$f(r+kA)equiv 0 pmodAB$$, then repeat. (Adding one prime at a time to the product.)
  $endgroup$
  – Yong Hao Ng
  yesterday
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  which works since $$f(r+ kA)equiv f(r)equiv 0 pmod A$$ and $$f(r+kA) equiv f(r + (s-r)A^-1A) 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
  yesterday
  

  
  
  
  

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 pmodp_m+1
$$

So you can find solution to
$$
f(r_i) equiv 0 pmodp_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 yesterday

Yong Hao NgYong Hao Ng

3,7091222

$endgroup$

share|cite|improve this answer

answered yesterday

Yong Hao NgYong Hao Ng

3,7091222

answered yesterday

Yong Hao NgYong Hao Ng

3,7091222

answered yesterday

Yong Hao NgYong Hao Ng

3,7091222