## 10.1 Number Theory Review We review some basic elements of number theory. ### 10.1.1 Composite and Prime Numbers The set  is called the set of ***integers***. For any two integers *n, h* ∊ *Z*, we say *h* ***divides*** *n* denoted *h*|*n*, if there is some integer *k* such that *n* = *kh*. If *h*|*n*, we also say *n* is ***divisible*** by *h, n* is a ***multiple*** of *h*, and *n* is a ***divisor*** or ***factor*** of *n*. Example 10.1****We have that 4|20 since 20 = (5) (4). The interger 3 does not divide 20 since there is no integer *k* such that 20 = (*k*) (3). **** Example 10.2****The divisors of 12 are  **** An integer *n* < 1 whose only positive divisors are 1 and *n* is a called a ***prime number*** or simple a ***prime***. A prime number has no factors. An integer *n* > 1 that is not prime is called a ***composite number***. A composite number has at least one factor. Example 10.3****The first 10 primes are  **** Example 10.4****The integer 12 is composite because it has the divisors 2, 3, 4, and 6. The integer 4 is composite because it has the divisor 2. **** ### 10.1.2 Greatest Common Divisor If *h|n* and *h|m*, then *h* is called a ***common divisor*** of *n* and *m*. If *n* and *m* are not both zero, the ***greatest common divisor*** of *n* and *m*, denoted gcd(*n, m*), is the largest integer that divides both of them. Example 10.5****The positive divisors of 24 are ****  and the positive divisors of 30 are  So the common positive divisors of 24 and 30 are  and the value of gcd(24, 30) is 6. We have the following theorems concerning common divisors: Theorem 10.1****If *h|n* and *h|m*, then for any integers *i* and *j* ****  Proof: Since *h|n* and *h|m*, there exist integers *k* and *l* such that *n* = *kh* and *m* = *lh*. Therefore,  which means *h*| (*in* + *jm*). Before proceeding, we need more definitions. For any two integers *n* and *m*, where *m* ≠ 0, the ***quotient*** *q* of *n* divided by *m* is given by  and the ***remainder*** *r* of dividing *n* by *m* is given by  The remainder is denoted *n* mod *m*. It is not hard to see that if *m* > 0 then 0 ≤ *r* < *m*, and if *m* < 0 then *m* < *r* ≤ 0. So we have  The **division algorithm** says not only that the integers *q* and *r* in Equality 10.1 exist but also that they are unique. Example 10.6****The following table shows some quotients and remainders: **** n m q=∟n/m⌟ r=n–qm 23 5 ∟23/5⌟=4 23–(4)(5)=3 –23 5 ∟–23/5⌟=–5 –23–(–5)(5)=2 23 –5 ∟23/–5⌟=–5 23–(–5)(–5)=–2 –23 –5 ∟23/–5⌟=4 –23–(4)(–5)=–3 20 5 ∟20/5⌟=4 20–(4)(5)=3 Theorem 10.2****Let *n* and *m* be integers, not both 0, and let ****  That is, *d* is the smallest positive linear combination of *n* and *m*. Then  Proof: Let *i* and *j* be the integers that yield the minimal value *d*. That is, *d* = *in* + *jm*. Furthermore, let *q* and *r* be the quotient and remainder respectively, of dividing *n* by *d*. Then owing to Equality 10.1 and the fact that *d* is positive,  We therefore have  which means that *r* is a linear combination of *n* and *m*. Since *d* is the smallest positive linear combination of *n* and *m* and *r* < *d*, we conclude *r* = 0, whichmeans *d|n*. Similarly, *d|m*. Therefore, *d* is a common divisor of *m* and *n*, which means  Since the gcd(*n, m*) divides both *n* and *m*, and *d* = *in* + *jm*, [Theorem 10.1](LiB0088.html#1213) implies gcd(*n, m*)|*d*. We conclude  Combining these last two inequalities, we have *d* = gcd(*n, m*). Example 10.7****We have that gcd(12, 8) = 4, and ****  Corollary 10.1****Suppose *n* and *m* are integers, not both 0. Then every common divisor of *n* and *m* is a divisor of gcd(*n, m*). That is, if *h|n* and *h|m*, then ****  Proof: By the preceding theorem, gcd(*n, m*) is a linear combination of *n* and *m*. The proof now follows from [Theorem 10.1](LiB0088.html#1213). Example 10.8****As shown in [Example 10.5](LiB0088.html#1219), the common positive divisors of 24 and 30 are ****  and the value of gcd(24, 30) is 6. As the previous corollary implies, 1, 2, 3, and 6 all divide 6. Theorem 10.3****Suppose we have integers *n* ≥ 0 and *m* > 0. If we let *r* = *n*mod*m*, then ****  If *n* = 0, *r* = *m* and the equality obviously holds. Otherwise, we will show that gcd(*n, m*) and gcd(*m, r*) each divide each other. It is left as an exercise to show that two positive integers divide each other if and only if they are equal, whichwill complete the proof of the theorem. First we show gcd(*n, m*)| gcd(*m, r*). If we let *d*′ = gcd(*n,m*) then *d*′ |*n* and *d*′|*m*. Furthermore,  where *q* is the quotient of *n* divided by *m*, which means *r* is a linear combination of *n* and *m*. [Theorem 10.1](#ch10ex06) therefore implies *d*’|*r*. Since *d*’|*m* and *d*’|*r*, [Corollary 10.1](#ch10ex10) implies  which completes the proof of this direction. Next show gcd(*m, r*)| gcd(*n, m*). If we let *d*″ = gcd(*m, r*), then *d*″|*m* and *d*″*r*. Furthermore,  where *q* is the quotient of *n* divided by *m*, which means *n* is a linear combination of *m* and *r*. [Theorem 10.1](#ch10ex06) therefore implies *d*″|*n*. Since *d*″|*m* and *d*″|*n*, [Corollary 10.1](#ch10ex10) implies  which completes the proof of this direction. Example 10.9****According to the previous theorem, ****  because 16 = 64 mod 24. We can continue in this manner to determine gcd(64, 24). That is,  ### 10.1.3 Prime Factorization Every integer greater than one can be written as a unique product of primes. We next develop theory that proves this assertion. Two integers *n* and *h*, not both zero, are called ***relatively prime*** if gcd(*n,h*) = 1. Example 10.10****The integers 12 and 25 are relatively prime because gcd(12, 25) = 1. The integers 12 and 15 are not relatively prime because gcd(12, 15) = 3. **** Theorem 10.4****If *h* and *m* are relatively prime, and *h* divides *nm*, then *h* divides *n*. That is, *gcd*(*h,m*) = 1 and *h|nm* implies *h|n*. **** Proof: [Theorem 10.2](#ch10ex08) implies there are integers *i* and *j* such that  Multiplying this equality by *n* yields  Clearly, *h* divides the first term on the left-hand side of this equality, and, since *h|nm*, *h* also divides the second term. Therefore, *h* divides the left-hand side, which means *h* divides *n*. Example 10.11****The integers 9 and 4 are relatively prime, 9|72, and 72 = 18 × 4. As the previous theorem implies, 9|18. **** Corollary 10.2****Given integers *n, m*, and prime integer *p*, if *p|nm*, then *p|n* or *p|m* (inclusive). **** Proof: The proof follows easily from [Theorem 10.4](#ch10ex15). The theorem that follows is called the ***unique factorization theorem*** and the ***fundamental theorem of arithmetic***. Theorem 10.5****Every integer *n* ≥ 1 has a unique factorization as a product of prime numbers. That is, ****  where *p*1 < *p*2 < … < *pj* are primes, and this representation of *n* is unique. The integer *ki* is called the ***order*** of *pi* in *n*. Proof: We use induction to prove such a representation exists. Induction base: We have 2 = 21. Induction hypothesis: Suppose all integers *m* such that 2 ≤ *m* < *n* can be written as a product of prime numbers. Induction step: If *n* is prime, then *n* = *n*1 is our representation. Otherwise, *n* is composite, which means there exists integers *m, h* > 1 such that  Clearly *m, h* < *n*. Therefore, by the induction hypothesis, *m* and *h* can each be written as a product of primes. That is,  Since *n* = *mh*,  We obtain our desired representation by grouping primes that are equal and arranging the terms according to increasing values of the primes. This completes the induction proof. The fact that the product is unique follows from [Corollary 10.2](#ch10ex17) and is left as an exercise. Example 10.12****We have that ****  The previous theorem says the representation on the right-hand side of this equality is unique. Theorem 10.6****The gcd(*n, m*) is a product of the primes that are common to *n* and *m*, where the power of each prime in the product is the smaller of its orders in *n* and *m*. **** Proof: The proof is left as an exercise. Example 10.13****We have 300 = 22 × 31 × 52 and 1,125 = 32 × 53. So gcd (300, 1,125) = 20 × 31 × 52 75. **** ### 10.1.4 Least Common Multiple A concept similar to that of the greatest common divisor is that of the least common multiple. If *n* and *m* are both nonzero, the ***least common multiple*** of *n* and *m*, denoted lcm(*n, m*), is the smallest positive integer that they both divide. Example 10.14****The lcm(6,9) = 18 because 6|18, 9|18, and there is no smaller positive integer that they both divide. **** Theorem 10.7****The lcm(*n, m*) is a product of the primes that are common to *n* and *m*, where the power of each prime in the product is the larger of its orders in *n* and *m*. **** Proof: The proof is left as an exercise. Example 10.15****We have 12 = 22 × 31 and 45 = 32 × 51. So lcm(12, 45) = 22 × 32 × 51 = 180. ****