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

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$?

• Seems unlikely, given the extreme cases of Fermat and Mersenne primes. – user17794 Jul 20 '12 at 4:50
• In general I think not (though the experts will confirm this), but if $n$ has two factors (not necessarily prime) which differ by 2 so that $n=r(r+2)$ then $n+1=(r+1)^2$. – Mark Bennet Jul 20 '12 at 4:53
• $n$ and $n+1$ are relatively prime, so no prime factor of one can be a prime factor of the other. But beyond that, there is no regularity; if $n$ is prime and different from $2$, then $n+1$ is certainly not prime; and conversely for $n+1\neq 3$. There is no known regularity in the functions $\omega(n)$, $\Omega(n)$. – Arturo Magidin Jul 20 '12 at 5:18

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 factorizaion 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

• You attribute the last results to Erdős, but the paper you cite is by Erdős and Pomerance. I suggest that you either attribute the results to "Erdős and Pomerance" in your answer or find a reference authored by Erdős alone. – Malcolm Dec 7 '17 at 12:47
• @Malcolm Noted! – Klangen Feb 6 '18 at 7:31
• Does the Erdos-Pomerance paper actually show that $P(n)>P(n+1)>P(n+2)$ does not occur infinitely often? My impression is that they're saying that they personally could not find a proof that $P(n)>P(n+1)>P(n+2)$ occurs infinitely often, but perhaps it does in fact occur infinitely often. – idmercer Jun 13 '18 at 15:29

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

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.

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

• Would it really? – Lord Shark the Unknown May 29 '17 at 20:52
• I already heard that. Can you give details? – DaBler Nov 2 '18 at 19:35
• DaBler. dividing by 2 or multiplying by 3 only plays with two of the potential prime factors. adding 1 is what makes it interesting – Collag3n Dec 5 '18 at 19:01

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_{1}(60)=\sum_{t}^{r} \{[\frac {60}{5^{t}}]-[\frac {59}{5^{t}}]\}=1$$

Finally:

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