#### 4.5.4. Factoring into Primes

Several of the computational methods we have encountered in this book rest on the fact that every positive integer *n* can be expressed in a unique way in the form

where each *p*_{k} is prime. (When *n* = 1, this equation holds for *t* = 0.) It is unfortunately not a simple matter to find this prime factorization of *n*, or to determine whether or not *n* is prime. So far as anyone knows, it is a great deal harder to factor a large number *n* than to compute the greatest common divisor of two large numbers *m* and *n*; therefore we should avoid factoring large numbers whenever possible. But several ingenious ways to speed up the factoring ...