Relationship between prime factorizations of $n$ and $n+1$?

Question

Are there any theorems that give us any information about the prime factorization of some integer $n+1$, if we already know the factorization of $n$?

Recalling Euclid's famous proof for the infinity of the set of prime numbers, I guess we know that if $n = p_1 p_2 p_3$, then $n+1$ cannot have $p_1$, $p_2$, or $p_3$ as factors. But is there any way we could use the information about $n$'s factorization to determine something more precise about the factorization of $n+1$?

Answer 1

There is no known explicit relation between the prime factors of $n+1$ given the prime factorization of $n$.

In fact, this is considered one of the hardest problems in our current understanding of number theory. Paul Erdős once famously quoted, albeit within the context of the Collatz conjecture - closely linked to the prime factorization of consecutive integers - that:

"Mathematics is not yet ready for such problems".

We can however deduce some basic properties for $n+1$ in the following way. If we denote by $\omega(n)$ the number of distinct prime factors of $n$ and by $\alpha_i$ the multiplicity of the $i^{th}$ prime in its decomposition, we have:

$$ n = \prod_{i=1}^{\omega(n)} p_i^{\alpha_i}. $$

From this we get:

• $n+1$ is not divisible by any of the $p_i$, otherwise $p_i$ would divide $(n+1)-n$, which is clearly impossible because no prime number divides $1$,
• If $n$ is even, $n+1$ is odd and vice-versa, which can trivially be extended to congruence modulo $p_i$,
• There is no obvious relation between $\omega(n)$ and $\omega(n+1)$.

One less obvious "observation" is Wilson's theorem. It states that if $p$ is a prime number, we have the following congruence relation:

$$ (p-1)!\ \equiv\ -1 \pmod p $$

This connects the prime $p$ with its immediate integer predecessor $p-1$.

There are also some non-trivial observations made by Erdős and Pomerance$^1$, which are the following. Define $P(n)$ as the largest prime factor of $n$. Then:

• $P(n)>P(n+1), P(n+1)>P(n+2), P(n)<P(n+1)$ and $P(n+1)<P(n+2)$ occur infinitely often,
• $P(n)>P(n+1)>P(n+2)$ does not occur infinitely often,
• $P(n)$ and $P(n+1)$ are usually not close, i.e., for each $\epsilon>0$, there is a $\delta>0$ such that for sufficiently large $x$, the number of $n\leq x$ with

$$ x^{-\delta}<P(n)/P(n+1)<x^{\delta} $$

is less than $\epsilon x$.

• Any integer $n\leq x$ is divisible by at most $\log(x)/\log(2)$ primes.

---

$^1$ Erdős and Pomerance, "On the largest prime factors of $n$ and $n+1$", Aequationes Mathematicae 17 (1978), available at: https://www.math.dartmouth.edu/~carlp/PDF/paper17.pdf  

Answer 2

Currently very little is known about this problem and it appears intractable by known methods, though it is of great interest. More generally, additive number theory takes upon the challenge of studying the additive structure of prime numbers, which is bound to be difficult due to their inherent multiplicative nature.

Some problems that would greatly benefit from knowing how addition effects prime factorizations include: The Twin Prime Conjecture and The Collatz Conjecture.

Answer 3

While the factorisation of $N$ might not help much with the factorisation of $N+1$, in special circumstances, it can help with determining primality of $N$.

Famous examples of this include Pépin's Test for primality of numbers of the form $2^{2^n}+1$, and Proth's Theorem for primality of numbers of the form $k \times 2^n+1$ where $k<2^n$ (Proth primes feature on the top 20 known primes).

There are more general primality tests for $N+1$ based on (partial) knowledge of the factorisation of $N$, but they tend to be less elegant. For example, this was snipped from "Factorizations of $b^n \pm 1$, b = 2, 3, 5, 6, 7, 10, 11, 12 Up to High Powers" by Brillhart, Lehmer, Selfridge, Tuckerman, and Wagstaff, Jr.:

Theorem 11. Let $N-1=FR$, where $F$ is completely factored and $(F,R)=1$. Suppose there exists an $a$ for which $a^{N-1} \equiv 1 \pmod N$ and $(a^{(N-1)/q}-1,N)=1$ for each prime factor $q$ of $F$. Let $R=rF+s$, $1 \leq s < F$, and suppose $N<2F^3+2F$, $F>2$. If $r$ is odd, or if $r$ is even and $s^2-4r=t^2$, then $N$ is prime. Otherwise, $s^2-4r=t^2$ and $$N = [\frac{1}{2}(s-t)F+1][\frac{1}{2}(s+t)F+1].$$

Answer 4

As I wrote when this question was raised at MathOverflow, if knowing the factorization of $n$ told you much about the factorization of $n+1$, the Fermat numbers $2^{2^n}+1$ would be easy --- but, they aren't.

Answer 5

Finding the connection of the prime factorization of n and n+1 would go hand in hand with proving Collatz Conjecture.

Answer 6

I found a relation, here a proff:

We know that:

$n!=\prod_{P_{i} \leq n}p_{i}^{ \alpha_{i}(n)}$; where:

$\alpha_{i}(n)=\sum_{t=1}^{r}[\frac{n}{p_{i}^{t}}]$ and $p^{r} \leq n < p^{r+1}$.

Then:

$n=\frac {n!}{(n-1)!}=\prod_{P_{i} \leq n}p_{i}^{ \beta_{i}(n)}$ (Eq. 1)

Where:

$\beta_{i}(n)= \alpha_{i}(n)-\alpha_{i}(n-1)$

In other words:

$n+1=\prod_{P_{i} \leq n+1}p_{i}^{ \beta_{i}(n+1)}$; where:

$\beta_{i}(n+1)= \alpha_{i}(n+1)-\alpha_{i}(n)$.

Finally, this is the relation:

$\beta_{i}(n+1)= \alpha_{i}(n+1)-\alpha_{i}(n-1)-\beta_{i}(n)$.

In summary, Eq.1 can be used as a method for decomposition in prime factors, let's see an example:

$n=60$

$\beta_{i}(60)=\sum_{t}^{r} \{[\frac {60}{p_{i}^{t}}]-[\frac {59}{p_{i}^{t}}]\}$

Then:

$\beta_{1}(60)=\sum_{t}^{r} \{[\frac {60}{2^{t}}]-[\frac {59}{2^{t}}]\}=2$

$\beta_{2}(60)=\sum_{t}^{r} \{[\frac {60}{3^{t}}]-[\frac {59}{3^{t}}]\}=1$

$\beta_{3}(60)=\sum_{t}^{r} \{[\frac {60}{5^{t}}]-[\frac {59}{5^{t}}]\}=1$

Finally:

$60=2^{2}3^{1}5^{1}$

Answer 7

Let's begin with some natural number $n \in \mathbb{N}$, and see how we can use algorithms for generating the set of all fractions in lowest form up to denominator $N$, the so-called Farey Fractions, $\mathbb{F}_N$.

Let $p,q \in \mathbb{F}_N$ be two consecutive elements of $\mathbb{F}_N$. By the definition of Farey Fractions, this means we can find 4 natural numbers $a,b,c,d \in \mathbb{N}$ with the following properties

• $p = \frac{a}{b}$
• $q = \frac{c}{d}$
• $gcd(a,b)=1$
• $gcd(c,d)=1$
• $bc - ad = 1$

The final property is an easy consequence of $p,q$ being consecutive fractions in $\mathbb{F}_N$

It's clear that we can find distinct prime number $p_1,p_2, \cdots, p_N$ such that $$bc = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_{k-1}^{\alpha_{k-1}}$$ $$ad = p_k^{\alpha_k}p_{k+1}^{\alpha_{k+1}}\cdots p_N^{\alpha_{k+N}}$$

The equation $bc - ad = 1$ takes the following form

$$1 + p_k^{\alpha_k}p_{k+1}^{\alpha_{k+1}}\cdots p_N^{\alpha_N} = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_{k-1}^{\alpha_{k-1}} $$

Although this does not provide any direct answer to the question as posed, I think it's very cute how the property $bc - ad = 1$, which plays such an important role in many parts of mathematics, leads to an equation of the form $1 + p_k^{\alpha_k}p_{k+1}^{\alpha_{k+1}}\cdots p_N^{\alpha_N} = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_{k-1}^{\alpha_{k-1}} $. Perhaps there is something to this kind of approach?