ECE103 Study Guide - Midterm Guide: Prime Factor

• School: University of Waterloo
• Department: Electrical and Computer Engineering
• Course: ECE103
• Professor: Martin Pei

Document Summary

Definition 2. 5. 1 an integer n 2 is prime if its only positive divisors are 1 and n itself. If n 2 is not prime, we say it is composite. Every integer greater than one can be expressed as a product of primes (with perhaps only one factor). Example: every composite integer n has a prime divisor p n. If n a composite integer is the product of a and b such that n. = ab and a and b cannot both exceed n. Therefore the smaller of a and b has a prime factor smaller than n. Example: prove that if p is a prime and p|ab, then p|a or p|b. Case 1: if p|a, the statement is true. Case 2: if p |a, then the gcd(p,a) = 1 since p is a prime. Example: prove that if p is a prime, then gcd(p, (p 1)!)