20 CHAPTER 1. SOME PREREQUISITE TOPICS

Now suppose q divides both m and n. Then m = qx and n = qy for integers, x and y.Therefore,

p = mx0 +ny0 = x0qx+ y0qy = q(x0x+ y0y)

showing q|p. Therefore, p = (m,n) . ■This amazing theorem will now be used to prove a fundamental property of prime

numbers which leads to the fundamental theorem of arithmetic, the major theorem whichsays every integer can be factored as a product of primes.

Theorem 1.12.6 If p is a prime and p|ab then either p|a or p|b.

Proof: Suppose p does not divide a. Then since p is prime, the only factors of p are 1and p so follows (p,a)= 1 and therefore, there exists integers, x and y such that 1= ax+yp.Multiplying this equation by b yields b = abx+ ybp.Since p|ab, ab = pz for some integerz. Therefore,

b = abx+ ybp = pzx+ ybp = p(xz+ yb)

and this shows p divides b. ■The following is the fundamental theorem of arithmetic.

Theorem 1.12.7 (Fundamental theorem of arithmetic) Let a ∈ N\{1}. Then a = ∏ni=1 pi

where pi are all prime numbers. Furthermore, this prime factorization is unique except forthe order of the factors.

Proof: If a equals a prime number, the prime factorization clearly exists. In particularthe prime factorization exists for the prime number 2. Assume this theorem is true for alla ≤ n− 1. If n is a prime, then it has a prime factorization. On the other hand, if n is nota prime, then there exist two integers k and m such that n = km where each of k and m areless than n. Therefore, each of these is no larger than n− 1 and consequently, each has aprime factorization. Thus so does n. It remains to argue the prime factorization is uniqueexcept for order of the factors.

Suppose ∏ni=1 pi = ∏

mj=1 q j where the pi and q j are all prime, there is no way to reorder

the qk such that m = n and pi = qi for all i, and n +m is the smallest positive integersuch that this happens. Then by Theorem 1.12.6, p1|q j for some j. Since these are primenumbers this requires p1 = q j. Reordering if necessary it can be assumed that q j = q1.

Then dividing both sides by p1 = q1,∏n−1i=1 pi+1 = ∏

m−1j=1 q j+1. Since n+m was as small

as possible for the theorem to fail, it follows that n− 1 = m− 1 and the prime numbers,q2, · · · ,qm can be reordered such that pk = qk for all k = 2, · · · ,n. Hence pi = qi for all ibecause it was already argued that p1 = q1, and this results in a contradiction. ■

1.13 PolynomialsIt will be very important to be able to work with polynomials in certain parts of linearalgebra to be presented later. Polynomials are a lot like integers. The notion of division isimportant for polynomials in the same way that it is for integers.

Definition 1.13.1 A polynomial is an expression of the form anλn+an−1λ

n−1+· · ·+a1λ +a0, an ̸= 0 where the ai come from a field of scalars. Two polynomials are equal means thatthe coefficients match for each power of λ . The degree of a polynomial is the largest powerof λ . Thus the degree of the above polynomial is n. Addition of polynomials is defined in