MHB Poly. in integer coeff. takes infinitely many integers to composites.

  • Thread starter Thread starter caffeinemachine
  • Start date Start date
  • Tags Tags
    Integer Integers
caffeinemachine
Gold Member
MHB
Messages
799
Reaction score
15
Let $f(x)$ be a polynomial with integer coefficients. Show that $f(n)$ is composite for infinitely many integers $n$.

EDIT: As Bacterius has pointed out we need to assume that $f(x)$ is a non-constant polynomial.
 
Last edited:
Mathematics news on Phys.org
Refuted: $f(n) = 3$. But let's assume a non-constant polynomial :)



Lemma 1

If $f$ is an integer polynomial (of degree $s$) then for all $m$, $p$, $k$:
$$f(m) \equiv f(m + kp) \pmod{p}$$

Proof
$$f(m + kp) \equiv a_0 + a_1 (m + kp) + a_2 (m + kp)^2 + \cdots + a_s (m + kp)^s \equiv a_0 + a_1 m + a_2 m^2 + \cdots + a_s m^s \equiv f(m) \pmod{p}$$



Lemma 2

If an integer polynomial $f$ satisfies the property that $f(m) = f(m + kp)$ for all $k$, some $m$ and some $p > 0$, $f$ must be constant.

Proof

If such an $f$ was not constant, its graph would have to intersect the line $y = f(m)$ infinitely many times, which is clearly absurd as a polynomial must have finitely many roots.



Lemma 3

Any non-constant integer polynomial $f(n)$ must be composite for at least one $n$. In other words, $f(n)$ cannot be prime for all $n$.

Proof

Assume $f(n)$ generates only primes, that is, $f(n)$ is prime for all $n$. Then $f(1) = p$ for some prime $p$, so $f(1) \equiv 0 \pmod{p}$. Thus $f(1 + kp) \equiv 0 \pmod{p}$ for all integers $k$ by Lemma 1. But clearly this implies $f(1 + kp) = p$, otherwise $f(1 + kp)$ would be a multiple of $p$ (hence, a composite, contradicting the initial assumption). We are left with the implication that $f(1) = f(1 + kp)$ for all integers $k$, hence $f$ must be constant by Lemma 2, a contradiction.



Theorem

Let $f$ be a non-constant integer polynomial. Then $f(n)$ is composite for infinitely many $n$.

Proof

There exists at least one $m$ such that $f(m)$ is composite by Lemma 3, let $f(m) = c$. Then $f(m) \equiv 0 \pmod{c}$. This implies $f(m + kc) \equiv 0 \pmod{c}$ for all integers $k$ by Lemma 1. Hence $f$ generates infinitely many integers divisible by $c$. Those integers must be composite since $c$ is composite. $\blacksquare$



A less rigorous version of the argument is that if $f(m)$ is composite, then so is $f(m + k \cdot f(m))$ for all integers $k$.​
 
Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
Fermat's Last Theorem has long been one of the most famous mathematical problems, and is now one of the most famous theorems. It simply states that the equation $$ a^n+b^n=c^n $$ has no solutions with positive integers if ##n>2.## It was named after Pierre de Fermat (1607-1665). The problem itself stems from the book Arithmetica by Diophantus of Alexandria. It gained popularity because Fermat noted in his copy "Cubum autem in duos cubos, aut quadratoquadratum in duos quadratoquadratos, et...
Thread 'Imaginary Pythagorus'
I posted this in the Lame Math thread, but it's got me thinking. Is there any validity to this? Or is it really just a mathematical trick? Naively, I see that i2 + plus 12 does equal zero2. But does this have a meaning? I know one can treat the imaginary number line as just another axis like the reals, but does that mean this does represent a triangle in the complex plane with a hypotenuse of length zero? Ibix offered a rendering of the diagram using what I assume is matrix* notation...
Back
Top