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?

  • 2
    $\begingroup$ 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. $\endgroup$ Sep 20 at 13:46
  • 2
    $\begingroup$ 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. $\endgroup$
    – JMoravitz
    Sep 20 at 13:46
  • 2
    $\begingroup$ 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$... $\endgroup$
    – JMoravitz
    Sep 20 at 13:49
  • 1
    $\begingroup$ 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. $\endgroup$
    – J.G.
    Sep 20 at 13:53
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 20 at 14:41

2 Answers 2


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$
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<n+1.$


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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .