Divisibility Number Theory

 1 Divisibility Number Theory concerns itself mostly with the study of the natural numbers (N) and the integers (Z). As a consequence, it deals a lot with prime numbers and sometimes with rational numbers (Q). Recall: Definition. The natural numbers are the numbers N = {1, 2, 3, . . . }. The integers are the numbers Z = {. . . , −2, −1, 0, 1, 2, . . . }. The rational numbers are Q = { a b | a, b ∈ Z, b 6= 0}. There is significant debate about whether the naturals include 0 or not. It’s probably easier to consider the naturals to be just the positive integers. If you want to specify the non-negative integers you may write N0 or Z≥0. Notation. If an integer a divides an integer b we write a|b. Definition. A prime number is a positive integer p 6= 1 such that if p divides ab then p divides a or p divides b. Mathematically, we write this as p|ab =⇒ p|a or p|b Remark. Note, when you get to university and learn about more advanced number theory, negatives of primes will also be included as primes, but we do not worry about that here. Also, note, that this is a different definition than you may have expected! What about the definition that says "p only has two factors: 1 and p"? That is the definition for a number that is irreducible. As you can imagine, this ends up being the same thing as prime numbers when you work with integers. Feel free to use that definition, if it suits you better. Take a step back for a moment and think about the definition of a prime number that I used. Can we include rational numbers? Are there any rational primes? The answer to both questions is an emphatic no. The answer at first may be a bit disappointing and baffling, but it all follows from the fact that only certain groups of numbers have a concept of divisibility. We have divisibility in the integers, because of an amazing result called the Fundamental Theorem of Arithmetic. 1.1 Fundamental Theorem of Arithmetic The fundamental theorem of arithmetic allows us to factorise integers. There are other systems of numbers and objects that have this property, but you only learn about them at university. For positive integers, the statement is: Fundamental Theorem of Arithmetic. Every positive integer n 6= 1 can be written uniquely as a product of powers of primes. Mathematically, n = p α1 1 p α2 2 · · · p αk k where the pi are primes and αi ∈ N. So, how does this give us divisibility? Well, if a integer m can be written as a product of the same primes with the same or smaller powers, then it is called a factor of n and we write m|n. As an example, the integer 20 = 2 2 × 5, where the power on the five is a one of course. Then any of the following are factors: 1, 21 = 2, 22 = 4, 5, 2 × 5 = 10, 22 × 5 = 20. In fact these six positive integers are all the positive factors of 20 as you can easily check for yourself. Remark. Our discussion, is not complete if we do not mention negative integers. If 4 is a factor of 20, then −4 is a factor of 20 too. The minus does not change whether a number is a factor or not. Moreover, 1 and −1 divide every integer. 0 does not divide any integer, but every non-zero integer divides 0. 1.2 Euclidean Algorithm One concept you may already be familiar with is the greatest common divisor. Definition. The greatest common divisor of two integers a and b, denoted as gcd(a, b) (or sometimes just (a, b)), is the largest factor of a that is also a factor of b. 1 There is a method that allows you to calculate the gcd of two integers very quickly if you do not know their prime factorisation. It is called the Euclidean Algorithm and it works as follows: Euclidean Algorithm. Take two integers: let’s say 45 and 159. Take the larger and calculate how many multiples of the smaller fit into it and write the remainder as follows: 159 = 3 × 45 + 24. Now, repeat the same with the last two integers (the smaller integer and remainder). 45 = 1 × 24 + 21 Continue until you get a zero as the remainder. 24 = 1 × 21 + 3 21 = 7 × 3 + 0 The last remainder above the zero is the gcd! So, gcd(45, 159) = 3. Corollary 1.1. The gcd of two integers can be written as a linear combination of the two integers. This corollary is really important. You may never use the Euclidean algorithm unless you are coding an algorithm on a computer. However, what it does for us, mathematicians, is it tells us that the gcd can actually be written in terms of the original two integers. I shall do this using the result of the algorithm above. gcd(45, 159) = 3 = 24 − 1 × 21 = 24 − 1 × (45 − 1 × 24) = 2 × 24 − 1 × 45 = 2 × (159 − 3 × 45) − 1 × 45 = 2 × 159 − 7 × 45 Each of the above lines comes from rearranging one of the lines in the Euclidean algorithm. Definition. Two integers a and b are relatively prime (or coprime) if their gcd is 1. Corollary 1.2. For any two integers a and b whose gcd is 1, there exist integers s and t such that as + bt = 1. 1.3 Properties of Divisibility There are two types of divisibility properties that are interesting. The first is divisibility by certain numbers such as 2, 3, 4, 5, 9 and others. I include some of these here: Theorem 1.3. A number is divisible by 2 if its last digit is divisible by 2. A number is divisible by 3 if the sum of its digits is divisible by 3. A number is divisible by 4 if its last two digits as a number are divisible by 4. A number is divisible by 5 if its last digit is 0 or 5. A number is divisible by 9 if the sum of its digits is divisible by 9. There are many others, that you should feel free to come up with yourselves. I now give you some rules about what you can do with divisibility between general numbers. Theorem 1.4. 1. If a|b and a|c, then • a|b + c • a|b − c • a|kb where k is any integer. 2 2. If d| f and e| f , then • lcm(d,e)| f where lcm is the least common multiple. 3. If g|h and i|j, then • gi|hj. 4. And recall from the definition, if p is prime and p|kl, then • p|k or p|l. This is incredible powerful and this can be seen in the following problem. Problem 1. For what integer n is 2n−1 n+7 an integer? Proof. If 2n−1 n+7 is an integer, then n + 7|2n − 1. Using Theorem 1.4, we have that n + 7|2(n + 7). Employing the same theorem again, this time with subtraction we have n + 7|2(n + 7) − (2n − 1) which after simplifying means n + 7|15. All the factors of 15 are −15, −5, −3, −1, 1, 3, 5, 15 and these are all the values that n + 7 can take, so the solutions are: n = −22, −12, −10, −8, −6, −4, −2, 8. Notice, that negative solutions are of course allowed if the question does not specify otherwise!