Ggtkuk

After Sam didn't return home in the end, were he and Al still friends?

Found this skink in my tomato plant bucket. Is he trapped? Or could he leave if he wanted?

Is it dangerous to install hacking tools on my private linux machine?

Can an iPhone 7 be made to function as a NFC Tag?

Special flights

Resize vertical bars (absolute-value symbols)

Is there hard evidence that the grant peer review system performs significantly better than random?

Why not send Voyager 3 and 4 following up the paths taken by Voyager 1 and 2 to re-transmit signals of later as they fly away from Earth?

Why shouldn't this prove the Prime Number Theorem?

what is the log of the PDF for a Normal Distribution?

Why BitLocker does not use RSA

How were pictures turned from film to a big picture in a picture frame before digital scanning?

Trying to understand entropy as a novice in thermodynamics

Question about this thing for timpani

Can humans save crash-landed aliens?

Is it possible for SQL statements to execute concurrently within a single session in SQL Server?

Why weren't discrete x86 CPUs ever used in game hardware?

Why are vacuum tubes still used in amateur radios?

How much damage would a cupful of neutron star matter do to the Earth?

Caught masturbating at work

What does it mean that physics no longer uses mechanical models to describe phenomena?

A proverb that is used to imply that you have unexpectedly faced a big problem

Monty Hall Problem-Probability Paradox

What order were files/directories output in dir?

Polynomial and prime factors

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 Mar 20 at 13:36

Mee98Mee98

340110

$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 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 Mar 20 at 13:36

Mee98Mee98

340110

$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 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 Mar 20 at 13:36

Mee98Mee98

340110

$endgroup$

share|cite|improve this question

asked Mar 20 at 13:36

Mee98Mee98

340110

share|cite|improve this question

asked Mar 20 at 13:36

Mee98Mee98

340110

asked Mar 20 at 13:36

Mee98Mee98

340110

asked Mar 20 at 13:36

Mee98Mee98

340110

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 Mar 20 at 15:08

Yong Hao NgYong Hao Ng

3,7091222

$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 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
  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^-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
  Mar 20 at 16:50
  

  
  
  
  

add a comment | 

Your Answer

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 Mar 20 at 15:08

Yong Hao NgYong Hao Ng

3,7091222

$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 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
  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^-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
  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 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 Mar 20 at 15:08

Yong Hao NgYong Hao Ng

3,7091222

$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 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
  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^-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
  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 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 Mar 20 at 15:08

Yong Hao NgYong Hao Ng

3,7091222

$endgroup$

share|cite|improve this answer

answered Mar 20 at 15:08

Yong Hao NgYong Hao Ng

3,7091222

answered Mar 20 at 15:08

Yong Hao NgYong Hao Ng

3,7091222

answered Mar 20 at 15:08

Yong Hao NgYong Hao Ng

3,7091222