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

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.

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  

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].$$