# Factoring into Prime Factors

The number 160451 is obtained by multiplying two prime numbers. Find these prime numbers.

© BrainMass Inc. brainmass.com October 10, 2019, 5:58 am ad1c9bdddfhttps://brainmass.com/math/number-theory/factoring-into-prime-factors-523251

#### Solution Preview

We can easily check that the number n = 160451 isn't divisible by small prime numbers like 2, 3, 5, 7, etc. So, we need a method that find large prime divisors without us having to try all the previous ones. One such method is "Pollard's p-1 method" which we'll use here. This is based on Fermat's little theorem:

x^(p-1) mod p = 1

for p a prime number and x not equal to 0 mod p.

Pollard's p-1 method works by computing large powers of 2 modulo n. If p is a (unknown) prime divisor of n, then the computation modulo n is consistent with the same computation modulo p, the only difference is that we're not simplifying things as much ...

#### Solution Summary

We explain how Pollard's p-1 method can be used to factor the number.