Lecture 4

May 8

Recall the definition of a prime number from lecture 1. A prime number is is positive integer that has exactly two positive integer divisors.

Prime factorization theorem

If n is an integer and n>1 , then n can be written as a product of primes.

Proof: If n is prime we are done, since we consider a prime to be a product of one prime. Otherwise n must be composite and n must have a factor d, other than 1 and n. Let the quotient q=n/d , then n=d*q. We have 1<d and d<n. Multiply the first inequality by q to find q<d*q , which is q<n. Divide the second inequality by d to find d/d<n/d and this becomes 1<q. We also have 1<q<n .We now apply the same argument to d and q, as we did to n. This procedure must terminate since the factors grow smaller at each step. It can only stop we each factor has only 1 and itself as positive divisors. This means that each factor is prime.

Examples:

2=2

3=3

4=2*2

5=5

6=2*3

7=7

8=2*2*2

9=3*3

10=2*5

11=11

12=2*2*3

In Maple use ifactor or ifactors

> ifactor(96);

> ifactors(96);

Theorem: If a prime p divides a product of two numbers a*b then it must divide of of them . In symbols if p | (a*b) then p | a or p | b .

Proof: We will consider 2 cases, p divdes a and p does not divide a. Case 1. p | a . Since p divides a and a is one of the factors, we are done. Case 2: p does not divide a. Consider d=gcd(a,p) . d is a common divisor of a and p . The only positive divisors of p arr 1 and p, since p is prime. If p is also a divisor of a, then we would be in case 1, but we are in case 2, p does not divide a. This leaves 1 as the only possible positive common divisor of a and p. So 1 must also be the greatest common divisor of a and p. By the extended Euclidean algorithm, we can find integers s and t such that s*a+t*p=1. Now multiply this equation by b. This gives s*a*b+t*b*p=b . Rewrite the left hand side as s*(a*b)+(t*b)*p . Recall our assumption that p | (a*b) and p | p, so by our linear combination of divisors theorem p | ( s*(a*b) + (t*b)*p ) . This simplifys to p | b . Therefore in both cases we have shown that p divides one of the factors in the product of two factors.

Theorem: If p divides a product a[1]*a[2]*a[3]*...*a[r] then p divides on of the factors a[1] or a[2] or ... or a[r].

Proof: Case 1. p | a[1] . This is one of the factors so we are done. Case 2: p does not divide a[1]. Let b=a[2]*a[3]*...*a[r], and apply our previous theorem. Therefore p | b. This expands to p | (a[2]*a[3]*...*a[r]) . Now keep applying our previous theorem until we reach p | (a[r-1]*a[r]) .

Finally we will find that p divides one of the factors.

Fundamental Theorem of Arithmetic

Every integer n>=2 can be factored into a product of primes n=p[1]*p[2]*p[3]*...*p[r] in exactly one way ignoring the order of the primes p[1],p[2],p[3],...,p[r]. Note: The primes may not be distinct.

Examples: 3=3, 12=2*2*3=2*3*2=3*2*2, and we consider these 3 factorizations as the same, since we are ignoring the order of the factors.

Proof: If n is a prime p then we just write n=p and consider this as a product with only one factor. Note: this theorem is really 2 theorems, the first is that n can be factored into primes in some way, and the second is that the factorization is unique , up to the order of the primes. The first theorem is just our prime factorization theorem. The uniqueness theorem is prooved as follows: Suppose n as two distinct factorizations into a product of primes. Then n=p[1]*p[2]*...*p[r] and also n=q[1]*q[2]*...*q[s] , where p[i] and q[j] are primes. First observe that p[1] divides n from the first factorization, so p[1] | (q[1]*q[2]*...*q[s]) . Now apply our prime divides a product theorem to conclude that p[1] divides one of q[1] or q[2] or ... q[s] . Let it be q[i], since we are not concerned with the order swap q[1] and q[i] . Now p[1] | q[1] , but q[1] was also a prime. The only choice is that p[1]=q[1]. Now divide n by p[1] to obtain p[2]*p[3]*...*p[r]= (q[1]*q[2]*...q[s])/p[1] . Recall p[1]=q[1] so this becomes p[2]*p[3]*...p[r]=q[2]*q[3]*...*q[s]. Now repeat the above argument using p[2] instead of p[1]. Then we find p[2] divides the left hand side p[2]*p[3]*...*p[r] so it must also divide the right hand side q[2]*q[3]*...*q[s]. Again we rearrange the q[i]'s so that p[2] | q[2] . We now divide by p[2] to find that p[3]*p[4]*...*p[r] =q[3]*...q[s] . We continue to repeat the above argument until either all the p[i]'s are used up or until all the q[i]'s are used up. If all the p[i]'s are used up first then the left hand side is 1 and this equal to the right hand side a product of some primes q[i] . But 1 does not have any prime factors so the q[i] must also be used up . Similarly in the case that the q[i]'s are used up first, we find that the p[i]'s must also be used up . Therefore we can reorder the q[i]'s so that p[1]=q[1], p[2]=q[2], ... , p[r]=q[r] . This completes the proof.

Is it even possible that a set of numbers would not have unique factorization?

Aswer: Yes. Your text book considers several sets of numbers that do not have the unique factorization property.

Example 1: The set of positive even integers . E={2*n : n is a natural number}. We redefine prime in this set to be:

prime: k is prime if it cannot be written as the product of 2 other elements of E, and k is in E.

examples: 2 is prime. 4=2*2, 4 is not prime, 6=2*3, but 3 is not in E so 6=6 and 6 is prime. 8=2*2*2, is not prime, 10=2*5, but 5 is not in E so 10=10 and 10 is prime. Now consider 60=2*2*3*5, but 3 and 5 are not in E so regroup as follows: 60=2*30=6*10. We have already seen that 2,6,10 are primes in E. Now 30=2*3*5, but 3 and 5 are not in E so 30=30 and 30 is a prime in E. We now have shown that 60 has 2 distint prime factorizations in the set E.

Example 2: T = {1+3*k : k is a non-negative integer} , T={1,4,7,10,13,....} . We use the same definition of prime as in Example 1. Some primes in T are 4,7,10,13,19,22,25,...,55,... Now look at 220=4*55=10*22. Once again 220 is an example of a number in T with 2 distinct factorizations.

Example 3: S= Z [ ]={a+b*(-6)^(1/2) : a and b are integers} .

Note: Z [x] means the set of all polynomials in x with integer coefficients. So when x=(-6)^(1/2) this reduces to S , since all even powers reduce to an ordinary integer and all odd powers simplify to an integer times (-6)^(1/2) .

Let x=a+b*(-6)^(1/2). Then (x-a)^2=-6*b^2. This is x^2-2*a*x+a^2+6*b^2=0.

Thus x satisfys a polynomial equation of degree 2, with integer coefficints. So x is an algebraic number. The polynomial is also monic so x is an algebraic integer. Therefore every element in S is an algebraic integer. We say p in S is a prime if we cannot write p=a*b where a and b are in S and they are not units of S. Note the units of S are just 1 and -1 . Define the norm N on S by N(a+b*(-6)^(1/2))=a^2+6*b^2. Then N(0)=0,

N(1)=1, N(-1)=1 and these are the only 2 elements of S with norm 1. N(A*B)=N(A)*N(B). Now consider 10=2*5=(2+(-6)^(1/2))*(2-(-6)^(1/2)). Once agian we see that 10 has 2 distinct factorizations in S.

We have just seen 3 sets of numbers without the unique factorization property.

Gaussian integers

Recall Z [i]={a+b*i : a and b are integers, i=(-1)^(1/2)}

Do the Gaussian integers have the unique factorization property?

Example: 5 is a prime in the rational integers but 5=(2+i)*(2-i). Check (2+i)*(2-i)=2*2+2*(-i)+i*2+i*(-i)=4-2*i+2*i-(-1)=4+1=5.

Can we define a Euclidean algorithm for the Gaussian integers?

Can we define a quotient and remainder for Gaussian integers?

What are the units in the set of Gaussian integers?

Example: 1/i=1/i*(-i/(-i))=-i/(i*(-i))=-i/(-(-1))=-i/1=-i and this is a Gaussian integer, so i is a unit.

1/(2+3*i)=1/(2+3*i)*((2-3*i)/(2-3*i))=(2-3*i)/(2^2+3^2)=(2-3*i)/(13)=2/13-3/13*i. So 2+3*i is not a unit.

Diophantine equations:

A system of diophantine equations is a finite set of multivariate, integer coefficient, polynomial equations. To solve a system of diophantine equations, we must find all possible integer or rational solutions. Unlike the classical case, which usually has as many equations as unknows, where we find all real or complex number solutions, a system of diophanite equations usually has more variables than equations. The simplest non-trivial case is one linear equation in two variables, such as 3*x+5*y=8, which we have already learned how to find all integer solutions by using the extended Euclidean algorithm. The case of all rational solutions is trivial to do for the general linear equation in {x,y} , a*x+b*y=c, just solve for y if b is not 0, to find y=-a/b*x+c/b, where x is any rational number. If b=0, then solve x to obtain, x=c/a and y is any rational number. A simple non-linear example is the equation for the side lengths in a right-angled triangle: x^2+y^2=z^2, Find all integer solutions of this equation:

Fermat's last theorem

Fermat in about 1630 generalized the above equation to x^n+y^n=z^n, for n an integer greater than 2. He said that it was impossible to find positive integer solutions to this equation. Many mathematians claimed to have a proof of this famous theorem. Some of their false proofs involing completely factoring the left hand side over the algebraic integers, into lineat factors. Then assuming the unique factoriation theorem holds for algebraic integers. But we have already seen that Z [(-6)^(1/2)] does not have the unique factorization propery. Finally Andrew Wiles prooved Fermat's last theorem from 1993-1995. See web page :

http://www-groups.dcs.st-and.ac.uk/~history/HistTopics/Fermat's_last_theorem.html

Prime power factorization

If a and b are positive integers . Let the distinct primes divisors of a or b or both be p[1],p[2],....,p[n] Suppose:

a=p[1]^j[1]*p[2]^j[2]*...*p[n]^j[n] , and

b=p[1]^k[1]*p[2]^k[2]*...*p[n]^k[n] .

We allow some of the j[i]'s and some of the k[i]'s to be zero. Let m[i] be the smallest of j[i] and k[i]. Let M[i] be the largest of j[i] and k[i], for each i from 1 to n. Then

(a) a | b if and only if j[i]<=k[i] for i from 1 to n.

(b) gcd(a,b) =p[1]^m[1]*p[2]^m[2]*...p[n]^m[n] .

(c) lcm(a,b) =p[1]^M[1]*p[2]^M[2]*...*p[n]^M[n] .

Proof:

(a) => . if a | b then b=a*c for some integer c. Apply the unique factorization theorem to b and a, gathering up all repeated primes into a unique prime power factorization. We were given that a=p[1]*j[1]*p[2]^j[2]*...*p[n]^j[n]. Consider the i'th factor p[i]*j[i] . This divides a since a/p[i]^j[i] is the integer p[1]^j[1]*...p[i-1]^j[i-1]*p[i+1]^j[i+1]*...*p[n]^j[n] . By our product theorem p[i]^j[i] also divides a*c , this means that p[i]^j[i] divides b. Therefore b/p[i]^j[i] must be an integer. b was also contains the factor p[i]^k[i] . and p[i]^k[i]/p[i]^j[i]=p[i]^(k[i]-j[i]) , and this an integer if the exponent k[i]-j[i] >=0 . This condition can be rearranged into j[i]<=k[i]. Since i was arbitrary, this must be true for each i from 1 to n.

<= . Now we assume that j[i]<=k[i] for i from 1 to n. So we just divide b by a to find b/a=p[1]^k[1]*...p[n]^k[n]/(p[1]^j[1]*...*p[n]^j[n]) . This simplies to p[1]^(k[1]-j[1])*...*p[n]^(k[n]-j[n]). This rational number will be an integer if each exponent is non-negative. This gives us k[1]-j[1]>=0, k[2]-j[2]>=0, ...., k[n]-j[n]>=0. This can be simplified to j[i]<=k[i] for each i from 1 to n.