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

  • Thread starter Thread starter caffeinemachine
  • Start date Start date
  • Tags Tags
    Integer Integers
Click For Summary
A non-constant polynomial with integer coefficients, denoted as $f(x)$, can produce composite values for infinitely many integers $n$. The discussion emphasizes that for such polynomials, there exist infinitely many integers where $f(n)$ is composite. This conclusion relies on the properties of polynomials and their behavior over the integers. The assumption of non-constancy is crucial, as constant polynomials do not yield varying outputs. Thus, the assertion stands that non-constant integer coefficient polynomials can generate infinitely many composite outputs.
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$.​
 
Here is a little puzzle from the book 100 Geometric Games by Pierre Berloquin. The side of a small square is one meter long and the side of a larger square one and a half meters long. One vertex of the large square is at the center of the small square. The side of the large square cuts two sides of the small square into one- third parts and two-thirds parts. What is the area where the squares overlap?

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
2K
  • · Replies 4 ·
Replies
4
Views
3K
Replies
2
Views
2K
  • · Replies 3 ·
Replies
3
Views
891
Replies
9
Views
2K
  • · Replies 4 ·
Replies
4
Views
2K