p+1 = 140 = 22 × 5 × 7. The number 7! is the lowest factorial which is multiple of 140, so the proper factor 139 is found in this step. Using another initial value, say A = 9, we get: V1 of seq(9) = V1! of seq(9) = 9 V2 of seq(9) = V2! of seq(9) = 79 V3 of seq(79) = V3! of seq(9) = 41886 V4 of seq(41886) = V4! of seq(9) = 79378 V5 of seq(79378) = V5! of seq(9) = 1934 V6 of seq(1934) = V6! of seq(9) = 10582 V7 of seq(10582) = V7! of seq(9) = 84241 V8 of seq(84241) = V8! of seq(9) = 93973 V9 of seq(93973) = V9! of seq(9) = 91645. At this point gcd(91645-2,112729) = 811, so 811 is a non-trivial factor of 112729. Notice that p−1 = 810 = 2 × 5 × 34. The number 9! is the lowest factorial which is multiple of 810, so the proper factor 811 is found in this step. The factor 139 is not found this time because p−1 = 138 = 2 × 3 × 23 which is not a divisor of 9! As can be seen in these examples we do not know in advance whether the prime that will be found has a smooth p+1 or p−1. Generalization Based on Pollard's p − 1 and Williams's p+1 factoring algorithms, Eric Bach and Jeffrey Shallit developed techniques to factor n efficiently provided that it has a prime factor p such that any kth cyclotomic polynomial Φk(p) is smooth. The first few cyclotomic polynomials are given by the sequence Φ1(p) = p−1, Φ2(p) = p+1, Φ3(p) = p2+p+1, and Φ4(p) = p2+1. References External links P + 1 factorization method at Prime Wiki Integer factorization algorithms