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$.​
 
Thread 'Erroneously  finding discrepancy in transpose rule'
Obviously, there is something elementary I am missing here. To form the transpose of a matrix, one exchanges rows and columns, so the transpose of a scalar, considered as (or isomorphic to) a one-entry matrix, should stay the same, including if the scalar is a complex number. On the other hand, in the isomorphism between the complex plane and the real plane, a complex number a+bi corresponds to a matrix in the real plane; taking the transpose we get which then corresponds to a-bi...

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