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...
Suppose ,instead of the usual x,y coordinate system with an I basis vector along the x -axis and a corresponding j basis vector along the y-axis we instead have a different pair of basis vectors ,call them e and f along their respective axes. I have seen that this is an important subject in maths My question is what physical applications does such a model apply to? I am asking here because I have devoted quite a lot of time in the past to understanding convectors and the dual...
Thread 'Imaginary Pythagoras'
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