# If we know the prime factors of an integer, how much do we know about the prime factors of its successor?

Given an integer $$n$$, how much do we know and how much can we know about the prime factors of $$n+1$$ without actually factoring it?

An example from the comments: If $$n = 3^{4k+2}$$, then $$n+1$$ is divisible by 5. Is there a general theory describing all we can know about the factors of $$n+1$$ without factoring it? Or theories describing this behavior for a nontrivial subset of the integers?

• In the example you gave, we know that $n + 1$ has no chance of being divisible by 3 or 7. In general, $n$ and $n + 1$ have no prime factors in common. I don't think much more is known but I am not expert in this area. Sep 20 at 13:46
• Wait a moment... "has a 1/2 chance of being divisible by 3"? Why do you say that $n+1$ is not even but you think there is still a chance of it being or not being divisible by $3$? Perhaps you mean to talk about "has a chance of being divisible by $p$" where $p$ is not a factor of your number. Sep 20 at 13:46
• Now... another nitpick, "given a random integer $n$" This is ambiguous and imprecise, and the naive interpretation here is impossible. You can not have a uniform random distribution over a countably infinite set. So then, what distribution do we have since it can not be uniformly random? If it is a distribution such that we only ever pick numbers that are $1$ less than a multiple of $5$, then I can say with 100% certainty that the successor is a multiple of $5$... Sep 20 at 13:49
• Your inferences only require knowing which prime $p$ divide $n$; their orders as factors are unnecessary. What you're saying is, for $p\in\Bbb P$, the probability that $p|n+1$ is $0$ given $p|n$, or $1/(p-1)$ given $p\nmid n$. This formulation lets us sidestep the question of what random means.
– J.G.
Sep 20 at 13:53
• In general, the only thing we could say about the prime factors of $n+1$ is that none of them are also prime factors of $n$. Given any two disjoint sets of primes $P$ and $Q$, there is always a number $n$ for which $n$ is divisible by the primes in $P$ (and possibly more) and $n+1$ is divisible by the primes in $Q$ (and possibly more) by the Chinese Remainder Theorem. Sep 20 at 14:41

There is not much known in general.

Aside from the obvious - the prime factors of $$n$$ are distinct from the prime factors of $$n+1$$ - we cannot say much.

We can exclude other prime factors of $$n+1$$ only in a few cases.

If $$p_1,\dots,p_k,q$$ are distinct primes, and $$r=\nu_2(q-1)$$ is the highest integer such that $$2^r\mid q-1,$$ then we have the result:

There does not exist $$n$$ with the unique prime factors $$p_1,\dots,p_k$$ with $$n+1$$ divisible by $$q$$
iff,
for each $$i,$$ we can solve the congruence $$x_i^{2^r}\equiv p_i\pmod q.$$

If, for example, there is no $$x_1,$$ then $$p_1$$ has an even multiplicative order, $$2m,$$ modulo $$q,$$ and $$n=p_1^mp_2^{q-1}p_3^{q-1}\cdots p_k^{q-1}$$ has $$n+1$$ divisible by $$q.$$

On the other hand, if there is an $$x_i$$ for each $$i,$$ then $$n$$ will always be a $$2^r$$th power modulo $$q,$$ and $$-1$$ is never a $$2^r$$th power modulo $$q.$$

For example, if $$q=13,$$ $$r=2,$$ and we find the fourth powers modulo $$13$$ are $$1,3,9.$$ So if all the prime factors of $$n$$ are $$\equiv1,3,9\pmod{13},$$ then $$13$$ cannot be a factor of $$n+1.$$ But if any prime factor is not one of these, then we can find an $$n.$$

The abc Conjecture would say that, for any $$\alpha<1,$$ there are at most finitely many $$n$$ such that the product of the distinct prime factors of $$n(n+1)$$ is less than $$(n+1)^\alpha.$$ But that is still only a conjecture.

This obviously is not true for $$\alpha=1.$$ For example, $$n=2^{6k}-1$$ is divisible by $$9,$$ so the product of the prime factors of $$n$$ and $$n+1$$ is at most $$\frac23n

One special case is when $$n+1$$ is prime, and then knowing the prime factorization of $$n$$ can be helpful in proving that $$n+1$$ is prime.

Suppose for each prime factor $$p_i$$ of $$n$$ we can find $$b_i$$ such that:

\begin{align*} b_i^n &\equiv 1 \bmod (n+1), \text{ but } \\b_i^{n/p_i} &\not\equiv 1 \bmod (n+1) \end{align*}

Then $$n+1$$ is prime, because it follows that $$\varphi(n+1) = n$$, i.e. all positive integers less than $$n+1$$ are relatively prime to $$n+1$$.

An important improvement on this when only a partial factorization of $$n$$ is known is due to H.C. Pocklington (1914). Bressoud's Factorization and Primality Testing, Chapter 9 (Primitive Roots and a Test for Primality) gives details and references.