Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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<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.
