# 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, 2012 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$. Jul 20, 2012 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)$. Jul 20, 2012 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 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) and $$P(n+1) 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}

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. Dec 7, 2017 at 12:47
• @Malcolm Noted! Feb 6, 2018 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. Jun 13, 2018 at 15:29
• @Klangen $P(n)>P(n+1)>P(n+2)$ occur infinitely often. This is proved first by Balog. akjournals.com/view/journals/012/38/1-4/article-p45.xml Jun 5, 2020 at 8:45
• @SungjinKim Thank you for the reference Jun 5, 2020 at 17: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? May 29, 2017 at 20:52
• I already heard that. Can you give details? Nov 2, 2018 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 Dec 5, 2018 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_{3}(60)=\sum_{t}^{r} \{[\frac {60}{5^{t}}]-[\frac {59}{5^{t}}]\}=1$$

Finally:

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

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?