15
$\begingroup$

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

  • 0
    Seems unlikely, given the extreme cases of Fermat and Mersenne primes.2012-07-20
  • 2
    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$.2012-07-20
  • 4
    $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)$.2012-07-20

6 Answers 6