Number Theory 2

Number Theory 2 Whenever the division theorem is available, we can examine the important propertyof divisibility. If the remainder r is 0 when a is divided by b, we say that a is divisibleby b. Therefore, a is divisible by b if and only if there exists an integer q, so is it a =bq? For instance, the number 45 is divisible by 9 but 44 is not divisible by 9. Thenotation for divisibility is a slash between two numbers, denoting that the first number(a) is evenly divisible by the second (b). It is important to note that the statement "bdivides into a, or a is divisible by b" is not equivalent to "b divided by a." Arelationship between two quantities, a and b, can be described by dividing b by a inthe rational numbers. This property relationship is either true or false. The notation we use to denote rational numbers is quite distinct from the concept ofa rational number. The notation, which consists of two integers in the form of a ratio,is used to express a ratio of integers. However, many beginners confuse the notationwith the concept itself. Both mean division. However, in this case, the divisionproperty refers to a specific rational number—not a fraction. If you have a basic understanding of the discussion, there should be no problems.However, when you're first learning this material, it is important to note that there isan important distinction. Once we've established the concept of divisibility, we canmove on to the definition of prime numbers. A prime number is a whole number (p)greater than 1 that cannot be evenly divided by any other whole number except itself(p) and 1. It is a common practice to exclude 1 from the list of prime numbers. So wemust exclude 1 from the set of prime numbers, so the first prime number is 2. Thenext one is 3, followed by 5, 7, 11 and so on.

We need to check if b divides a. This is true if and only if there exists a q such thata=bq. Look at the quiz. The correct answers are b, d, f, g, and h. Why not a? Youshould remember that the whole definition of divisibility was based on theassumption that b was nonzero—we can't consider divisibility by a number of 0. Sovariant a doesn't work. Likewise, variant b doesn't work because 7 cannot be dividedby 44. Warning: the division of any number by zero is problematic, and so we rule itout. In this case, it was ruled out in the very statements of the divisibility theorem. Look at the second quiz. We must check that b divides a if and only if there is a qsuch that a = bq. This is true under the assumption that b is not equal to zero.Everything here is an integer. The correct answers are l, m and o. Variant i is false

because that number simply doesn't divide another number. However, if you hadactually taken the time to calculate the answer by calculator, then you would haveseen that the problem was impossible. Since we cannot divide an odd number by aneven number, the answer is a contradiction. Another one is false, because it simplydoes not follow that 2n divides n squared. The rest are false for various reasons. 2ncannot divide nˆ2 for various reasons. The problem with this statement is that if n canvary over Z, then that would include n = 0. So we cannot have this statement,because we will be able to derive a 0 coming in. Likewise, this fails because 0 wasincluded. If I excluded 0, it would be fine. Only one difference exists between thesetwo sets: this is the positive integers, 1, 2, and 3 and so on. This one because of allof the integers, including 0. We will now prove a theorem that gives the basic properties of divisibility. Theorem: ifa, b, c and d are integers with a non-zero, then the following all hold. (i) a divides 0and a also divides a. (ii) if a is +1 or -1 then a divides 1; otherwise, it does not. (iii) Ifc and d are integers with c non-zero, because we can't have divisibility by 0, then acdivides bd. The division theorem itself excludes the case of dividing a number byzero. (iv), if a divides b and b divides c, then a divides c. And this is assuming anon-zero b value. It is important to avoid division by 0. (v), a divides b, and b dividesa. The following holds true if and only if a equals + and -b. (vi), if a divides b, and if bis non-zero, then the absolute value of a is less than or equal to the absolute value ofb. It is impossible to divide a number by something that is bigger than it in absolutevalue. (vii), if a divides b, and a divides c, then a divides (bx + cy) for any integers x,y. To prove these, return to the definition of divisibility. Let's prove (iv), for example. All the proofs are essentially similar, in that they rely ona single idea. If the integer a divides the integer b, and if the integer b divides theinteger c, then this means there are integers d and e such that b = da and c = eb.

This is called divisibility, in which case c = d times e times a, which again bydefinition is a division of c. Let's do another one, (vi). Since a divides b and b is not zero we know that thereexists some d, such that b = da. Taking the absolute values of both sides of theequation, we see that the absolute value of b will be greater or equal to 1. Therefore,since b is non-zero, the absolute value of d must also be greater than or equal to 1.Since d cannot be 0, this means that a has to be less than or equal to b. The remaining statements of the theorem may be proved in a similar way. You simplyreturn to the definition of divisibility and when you know it, remembering that bdivides a if and only if there is a q such that b = qa. This takes just a couple of linesto prove. That summarizes the basic properties of divisibility. We will now prove the fundamental theorem of arithmetic. Theorem: Every naturalnumber greater than 1 can be expressed as a product of primes in a way that'sunique except for the order in which they are written. For example, 4 = 2 x 2, or 2ˆ2.6 = 2 x 3. 8 = 2ˆ3. 9 = 3ˆ2. 10 = 2 x 5. 12 = 2ˆ3 x 3, and so on and so on. 3,366 = 2 x3ˆ3 x 11 x 17 and so on. The number 2 is prime, as is the number 3. The number 4 isa product of primes (2×2). The number 5 is prime. The number 6 is a product ofprimes (2×3), 7 is prime. The number 8 is a product of primes, 9 is a product ofprimes. 10 is a product of primes, 11 is a prime. 12 is a product of primes, and so on.The product of a number and all of its prime factors is called that number's primedecomposition. The prime decomposition of a number is a useful factorization that

can reveal a lot of information about the number and its behavior. The second step is to prove uniqueness. In the uniqueness proof, we will rely onEuclid's Lemma. This states that if a prime number p divides a product ab, then pdivides at least one of the factors a, b. Let me now give you an additional proof of existence, which is the statement of thetheorem. Any natural number greater than 1 can be expressed as a product ofprimes in a way that's unique except for their order. We will prove existence bycontradiction. Suppose there is a composite number that cannot be expressed as theproduct of primes. Then there must exist a smallest such number. Let it be called n.If n is not prime, it must have a prime decomposition: n=ab. If a and b are primes,then n =ab is a prime decomposition of n; however, we can see that this contradictsthe assumption that n was chosen so as not to have a prime decomposition. It wasthe smallest number that didn't have a prime decomposition. If a and b are not prime,then one of them is composite. When either a or b is composite, then because it isless than n, it must be prime. By replacing a or b with its prime decomposition in n =ab, we get a prime decomposition of n. Thus, we have another contradiction thatproves the existence.

That was the first fragment of the proof of the fundamental theorem of arithmetic.Next we prove uniqueness. Thus, what we need to show is that the primedecomposition of any natural number n>1 is unique to the ordering of the primes.And we will prove this by contradiction. Suppose there is a number n greater than 1that has two or more prime decompositions. Let n be the smallest such number. Letn=p1*p2*d times da, da, da times p r =q1*q2*d times da, da, da, qs be two differentprime decompositions of n. So n is a product of r primes and s primes, some ofwhich are different. Now p1 is a prime factor of n. So p1 divides n. So p1 divides thisproduct. Since p1 divides q1 times q2 through qs, it follows that p1 divides q1q2…qs.Euclid's Lemma states that either p1 divides q1 or p1 divides the product of all of thefactors from q2 to qs. As Euclid's lemma states, if a prime number p divides theproduct of two numbers a and b, then p must divide at least one of those numbers. InEuclid's Lemma, if p divides the product of two numbers, ab, it also divides at leastone of those two numbers. Thus, p1 divided the original product into two numbers.To prove that p1 is a divisor of n1, we apply Euclid's lemma, which states that if p1divides one of the numbers, it must divide at least one of them. If p1 divides q1, theneither p1 divides the other part, or it divides both. If p1 does not divide q1, then eitherp1 = qi for some i between 2 and s or else p1 divides this product of primes. In thefirst case, p1 is one of these primes. In the second case, p1 divides this product ofprimes. So if p1 does not divide q1, then p1 actually is one of these primes. In thefirst case, we can see that p1 = q1. In the second case, one of p1 and q1 must bebetween 2 and s. However, if we delete the primes p1 and qi from the twodecompositions in the star, we get a number that is smaller than n but with twodifferent prime decompositions. Having proved that pi is equal to one of the qs, wedo not know which one it is, but it is one of them. We can delete the p1 term in thatcase. Similarly, we can remove an appropriate q from there. And once we havedeleted both p1 and q from there, we still have equality.

In the prime decomposition of a number, we can delete the largest prime factor andstill get another prime decomposition. But if we delete the largest prime factor of n,then the number that we get is smaller than n. The number smaller than n will be p2times d (a constant), d times a variable, and then pr. Furthermore, the result will be anumber less than n. We have deleted one number from here and what remains is theprime decomposition. The proof is simply the observation that when you have thesame prime on both sides of an equation, you can use Euclid's lemma to prove itsvalidity. The uniqueness of the decomposition follows from the fact that you candelete it and obtain two different decompositions of a smaller number. This is how weproved the fundamental theorem of arithmetic.