
In previous sections we have pointed out if the factored portion of n1 or of n+1 is larger than the cube root of n, then we can prove n is prime. In this section we discuss the case that the product of these two factored portions is greater than the cube root of n, then we can prove n prime using a combined test. (If we can not find enough factors to prove n prime this way, then we must use the generalized tests of the following chapter.)
Let n > 1 be an odd integer. Let n1 = F_{1}R_{1} and n+1 = F_{2}R_{2} where F_{1} and F_{2} are completely factored, and gcd(F_{1},R_{1}) = gcd(F_{2},R_{2}) = 1. The two types of tests we have applied to n in the previous sections are as follows.
Condition I. For each prime p dividing F_{1} there is an integer a such thatCondition II. Let (dn) = 1. For each prime p dividing F_{2} there is a Lucas sequence with discriminant d such that
 a^{n}^{1} ≡ 1 (mod n), but
 gcd(a^{(n1)/p}1, n) = 1.
 U(n+1) ≡ 0 (mod n), and
 gcd(U((n+1)/p), n) = 1.
Pocklington's theorem tells us that if (I) is true, then each prime factor q of n has the form k·F_{1}+1. About 60 years later Morrison proved that if (II) held, then each prime factor q of n has the form k·F_{2}±1 [Morrison75]. Together these give us the following:
Combined Theorem 1: Suppose n, F_{1}, F_{2}, R_{1}, R_{2} are as above and conditions (I) and (II) are satisfied. If n < max(F_{1}^{2}F_{2}/2 , F_{1}F_{2}^{2}/2), then n is prime.Proof. Let q be a prime factor of n and let n = mq. From Condition I we have that q ≡ 1 (mod F_{1}), so since n is 1 (mod F_{1}), so is m. From Condition (II) we know q = ±1 (mod F_{2}), so since n is 1 (mod F_{2}), either q or m is 1 (mod F_{2}). We may assume that m = 1 (mod F_{2}), because if every prime factor q of n was 1 (mod F_{2}), we'd have the contradiction that n ≡ 1 (mod F_{2}). Finally gcd(F_{1},F_{2})=2, so we can combine these to get that m ≡ 1 (mod F_{1}F_{2}/2). So for n to be composite we must have both
 n = qm > ( 1 + F_{1})(1 + F_{1}F_{2}/2) > F_{1}^{2}F_{2}/2, and
 n = qm > (1 + F_{2})(1 + F_{1}F_{2}/2) > F_{1}F_{2}^{2}/2.
This completes the proof of the theorem.
Sometimes, if n is small enough that we have almost enough factors to use the above (or similar) results, it can be helpful to bring in information about how far we have tried to factor n±1. Suppose, for example, that all of the prime factors of R_{1} and R_{2} are greater than B. Next apply the conditions above to R_{1} and R_{2}
Condition III. There is an integer a such thatCondition IV. Let (dn) = 1. There is a Lucas sequence with discriminant d (same d as used in condition II) such that
 a^{n}^{1} ≡ 1 (mod n), but
 gcd(a^{(n1)/R1} 1, n) = 1.
 U(n+1) ≡ 0 (mod n), and
 gcd(U((n+1)/R_{2}), n) = 1.
These two conditions inform us respectively that every prime factor q of n has the form k·u+1 where u is a prime factor of R_{1}; and every prime factor q also has the form k·v±1 where v is a prime factor of R_{2}. (Note that the factors u and v are dependent on q.) Of course u and v must each be larger than the factoring bound B. With the above notation we can now state our final classical theorems. (For the first the proof is virtually identical to the proof above.)
Combined Theorem 2: Suppose n, F_{1}, F_{2}, R_{1}, R_{2}, B are as above and conditions (I) through (IV) are satisfied. Define integers r and s by R_{1} = sF_{2}/2 + r with 0 < r < F_{2}/2. Ifn < max(B·F_{1} + 1, B·F_{2}^{ }^{ }1) (B^{2}F_{1}F_{2}/2 + 1)then n is prime.
Combined Theorem 3: Suppose n, F_{1}, F_{2}, R_{1}, R_{2}, B are as above and conditions (I) through (IV) are satisfied. Again define integers r and s by R_{1} = sF_{2}/2 + r with 0 < r < F_{2}/2. If for some integer mn < (m·F_{1}F_{2} + r·F_{1 }+ 1) (B^{2}F_{1}F_{2}/2 + 1)then either n is prime or kF_{1}F_{2} + rF_{1 }+ 1 divides n for some nonnegative integer k < m.
Both of these results (and more) can be found in "the" paper on the classical results: [BLS75]. Another excellent source on these theorems and their extensions is the excellent text H. Williams "Édouard Lucas and Primality testing" [Williams98]
How much further can we go? It is possible to consider higher powers such as the factors of
n^{6} 1 = (n  1)(n^{2 }+ n + 1)(n + 1)(n^{2 } n + 1).
(See [Williams78] for the theory and examples of these techniques). But the cost in terms of mathematical complication is very high. So in practice adding a few terms such as n^{2}+n+1 or n^{2}n+1 is rarely worth the effort. Rather it makes sense to just move on to the general primality proving methods of the next chapter.
