MathDB

Prove that there exist infinitely many primes q

Source: Iran Pre-Preparation Course Examination 1997, E3, P4

March 29, 2011

functionmodular arithmeticnumber theory proposednumber theoryalgebra

Problem Statement

Let

f : \mathbb N \to \mathbb N

be an injective function such that there exists a positive integer

k

for which

f(n) \leq n^k

. Prove that there exist infinitely many primes

q

such that the equation

f(x) \equiv 0 \pmod q

has a solution in prime numbers.