Problem 8RQ

a) Describe a procedure for finding the prime factorization of an integer,

b) Use this procedure to find the prime factorization of 80,707.

Solution:

Step 1:

a)In this problem we need to describe a procedure for finding the prime factorization of an integer.

We know that every integer has a prime factorization.

Let us consider , n is an integer and p is aprime number.

If n has no prime factors not exceeding is found, then n is a prime number.

If n has a prime factor , then a prime factor p not exceeding will be found , then continue by factoring . Note that has no prime factors less than p.

Again if has no prime factor not exceeding is found, then is a prime number.Otherwise if it has a prime factor q not exceeding will be found, then continue by factoring . Note that has no prime factors less than q.This procedure will continued until the factorization has been reduced to a prime number.