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

  • Context: MHB 
  • Thread starter Thread starter caffeinemachine
  • Start date Start date
  • Tags Tags
    Integer Integers
Click For Summary
SUMMARY

The discussion focuses on proving that for a non-constant polynomial function \( f(x) \) with integer coefficients, the output \( f(n) \) yields composite numbers for infinitely many integer inputs \( n \). This conclusion is established through the properties of polynomials and their behavior over the integers. The necessity of the polynomial being non-constant is emphasized, as constant polynomials do not satisfy the condition of producing infinitely many composite outputs.

PREREQUISITES
  • Understanding of polynomial functions and their properties
  • Familiarity with integer coefficients in mathematics
  • Knowledge of composite numbers and their definitions
  • Basic principles of mathematical proof techniques
NEXT STEPS
  • Study the properties of non-constant polynomials in number theory
  • Explore examples of polynomials that produce composite numbers
  • Investigate the implications of polynomial growth rates on integer outputs
  • Learn about the role of integer coefficients in polynomial behavior
USEFUL FOR

Mathematicians, educators, and students interested in number theory, particularly those studying polynomial functions and their implications in generating composite 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$.​
 

Similar threads

  • · Replies 8 ·
Replies
8
Views
3K
Replies
7
Views
2K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 16 ·
Replies
16
Views
3K
  • · Replies 4 ·
Replies
4
Views
3K
Replies
2
Views
2K
  • · Replies 3 ·
Replies
3
Views
1K
Replies
9
Views
2K
  • · Replies 4 ·
Replies
4
Views
2K