3
$\begingroup$

I know that this may seem an easy/noob question. Sorry if you also think that.

As a math enthusiast, I have spent some hours looking for different proofs of the infinitude of prime numbers. Most of them (almost all) use the fact that every single integer has a unique prime factorization (Fundamental Theorem of Arithmetic) or, at least, that is a product of primes. However, I have not been able to find any proof that did not use that.

Then, this is what I am looking for. Let $f : \mathbb{N} \to \mathbb{N}$, such that $0 \le f(x) <x$. Also, let $p$ represent a prime number greater that $2$ and $m>0$ any arbitray integer.

Which ways are there to prove that there are infinitely many numbers that are not of the form $pm+f(p)$ for any prime $p>2$ without taking into account the fact that there are infinitely many primes?

I know that this "conjecture" would imply their infinitude. What I am asking for is a proof that does not contain the sentence "...and, as we already know that there are infinitely many prime numbers...". My problem when analyzing this problem is that we cannot "copy/paste" proofs of the infinitude of primes since here we cannot use the Fundamental Theorem of Arithmetic because of the addition.

Thank you.

Edit 1: we can make a basic heuristic to calculate the amount of these integer lower or equal than another given $x$.

$$ \# a \{a\not = pn+f(p); a \le x\} \sim x \prod_{p\le x} \frac{p-1}{p} =O \left ( \frac{x}{\log(x)} \right )$$

Edit 2: what is it known about the case $f(p)$ being a constant greater than $0$?

$\endgroup$
18
  • $\begingroup$ I can't think off-hand of any proofs of the infinitude of prime numbers which do rely on the FTA. $\endgroup$
    – Angina Seng
    Commented May 23, 2017 at 18:06
  • 2
    $\begingroup$ There's a proof using only that every integer but $\;-1,\,1\;$ is a multiple of primes, but it requires some basic knowledge of topology. $\endgroup$
    – DonAntonio
    Commented May 23, 2017 at 18:07
  • 2
    $\begingroup$ @user3141592 No, it doesn't. It only uses, as mentioned, only the fact that every integer but $\;\pm1\;$ is the product of primes (which, btw, can be proved by and argument of infinite descend), without uniqueness. $\endgroup$
    – DonAntonio
    Commented May 23, 2017 at 18:13
  • 2
    $\begingroup$ I second the comment of Lord Shark the Unknown. Euclid's proof doesn't rely on FTA, nor Euler's, nor the topological one already mentioned. All that is involved is really the definition of prime. A number is either itself prime or divisible by some prime. Wait -- I guess Euler's does use FTA! $\endgroup$
    – sharding4
    Commented May 23, 2017 at 18:21
  • 1
    $\begingroup$ Can $m$ be negative? $\endgroup$
    – AlgorithmsX
    Commented May 23, 2017 at 19:38

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .