Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Seems unlikely, given the extreme cases of Fermat and Mersenne primes. –  Tim Duff Jul 20 '12 at 4:50
1  
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$. –  Mark Bennet Jul 20 '12 at 4:53
2  
$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)$. –  Arturo Magidin Jul 20 '12 at 5:18
add comment

3 Answers

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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].$$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.