Number Theory is considered one of the hardest sections in Mathematics. It is the study of the very fundamentals of numbers, yet can be very complicated. Information on this chapter for such a level of study is very rare, so I hope you will appreciate everything that I have for you over here.
We have been learning division since standard 2. But today, we will look at it at a different manner. If a and b are integers with a ≠ 0, then we say that a divides b if there is an integer c such that b = ac. When a divides b we say that a is a factor of b and that b is a multiple of a. The notation a | b denotes that a divides b (which means, there is no remainder). We write a ł b when a doesn’t divide b. For example, 2 | 4, but 4 ł 2. Take note that the notation 2 | 4 and 2/4 are 2 different things. The former is the notation for divisibility, while the latter is simply a fraction.
There are certain rules of divisibility that you should know. These are:
1. If a | b, b | c, then a | c.
You should know how to prove this. As above, the term a | b can be written as ak = b, bl = c, and therefore akl = bl = c. Here, k and l are integers.
2. If a | b, a | c, then a | (b + c) and a | (mb + nc).
3. If a | b, then a | bc.
The above 2 can also be proven with the similar notation as 1.
Not every 2 numbers can divide each other. For example, 2 does not divide 7, as it leaves a remainder of 1. Here we represent the above in an equation, which is
7 = 2•3 + 1
Here, 3 is the quotient, we denote the quotient as a div b, which in this case, 2 div 7 = 3. 1 is the remainder, which we denote as a mod b, and here we have 2 mod 7 = 1. Note that a remainder has to be positive. For example, –7 = 2• –3 – 1 is wrong, because it then gives us 2 div –7 = –3 and 2 mod –7 = –1, a negative remainder. It should be –7 = 2• –4 + 1, which in turns give 2 div –7 = –4 and 2 mod –7 = 1. Try doing –2 mod 7 and –2 div 7, and see whether the answers are different.
A prime number is a number that is only divisible by 1 and by the number itself. A number which is not prime, is called as a composite number. The smallest prime number is 2, and it goes on as 3, 5, 7, 11, 13, 17, 19… and so on. The interesting thing about prime numbers is that, you are unable to write a formula to determine the sequence or series of prime numbers. So therefore, if we want to find a very huge prime number, we need to slowly divide the number by almost every possible number before we say that it is prime. One very famous example used in the past is the sieve of Eratosthenes, which is used to find all the primes below 100. It is done by first listing down all the numbers from 1 to 100. Then, slowly cross out the multiples of 2, 3, 4 and so on, until you have nothing to cross out. The rest of the numbers, are primes! Another one is The Prime Number Theorem. You might wanna google about it.
So how do you know whether a number is prime, for a relatively small number? There is a way to find out, at least a little faster than trying to divide the number by any number smaller than itself. It is found that if a number is not divisible by primes less than its square root, then it is a prime number. This can be proven. If we have a composite number n such that ab = n, then if a > √n and b > √n, then we have ab > √n • √n > n, which is a contradiction. Although it does speed up the process of finding primes, it is still quite a slow method.
Prime numbers are the building blocks of all numbers. the Fundamental Theorem of Arithmetic states that:
Every positive integer > 1 can be written uniquely as a prime or as the product of 2 or more primes where the prime factors are written in order of non-decreasing size.
This is what we called as prime factorisation. For example, 4 = 22, 100 = 2252, 641 = 641 and so on. We can write down any number in terms of products of primes, a = 2x3y5z7w… and so on.
There’s a lot to talk about prime numbers. One famous argument was to prove that there are infinitely many primes. Suppose you label every prime number as p1, p2, p3 and so on. You found the greatest prime number in the world, called as pn. So if we write a particular number a such that a = p1p2p3…pn + 1, it must have been a prime, since it couldn’t be represented as the product of any primes smaller than pn. This contradicts with what we said earlier on about finding the greatest prime number, and therefore proves that there are indeed infinitely many primes.
Another 2 interesting stuff on prime numbers are the Goldbach’s Conjecture and the Twin Prime Conjecture. Go look up on it if you are free.
Now, let’s move on to the gcd and lcm. Try recalling whether this sounds familiar to your Form 1 Mathematics. gcd is the greatest common divisor (you are probably more familiar to the name highest common factor, or HCF), while lcm is the lowest common multiple. Here we denote k = gcd (a, b) to have the meaning of “k is the greatest common divisor of the integers a and b”. Similarly, k = lcm (a, b) means “k is the lowest common multiple of the integers a and b”. For example, gcd (4, 6) = 2 and lcm (5, 6) = 30.
Relating this back to prime numbers, for any 2 integers a and b, if gcd (a, b) = 1, we say that they are relatively prime. For example, 5 and 6 are relatively prime.
Do you still remember the method to find your lcm and gcd in Form 1? You had to draw out something like a ladder or so. But here, we will use another method, which has something to do with the prime factorization. For example,
Find gcd (120, 500) and lcm (120, 500).
We first start by representing the numbers 120 and 500 in terms of primes.
120 = 23 • 3 • 5
500 = 22 • 53
Now, the formulas to find the gcd and lcm are easy, it is just
gcd (a, b) = p1min(a1,b1)p2min(a2,b2)p3min(a3,b3)…pnmin(an,bn)
lcm (a, b) = p1max(a1,b1)p2max(a2,b2)p3max(a3,b3)…pnmax(an,bn)
You first compare the primes present among the 2 numbers 120 and 500. p1max(a1,b1) means the maximum of the powers of that particular prime p1 of the 2 numbers a and b, while p1min(a,b) means the minimum. So plugging in the numbers, we have
gcd (120, 500) = 2min(3,2) • 3min(1,0) • 5min(1,3) = 223051 = 20
lcm (120, 500) = 2max(3,2) • 3max(1,0) • 5max(1,3) = 233153 = 3000
From here, we obtain a new formula, as we can see that
ab = gcd (a,b) • lcm (a,b)
The method described for computing the greatest common divisor of 2 integers, using the prime factorizations of these integers, is inefficient. The reason is that it is time consuming to find prime factorizations. Now I will teach you a more efficient method of finding the gcd, called the Euclidian Algorithm (also Euclid’s Algorithm). It is named after the ancient Greek mathematician Euclid, who included a description of this algorithm in his book The Elements. Let’s start with an example.
Find gcd (91, 287).
First, we use the smaller term to divide the bigger term. Then, we take the divisor of and the remainder of the equation, repeat the process, until we get no more remainder. The last remainder is the gcd that we are finding. So we have
287 = 91 • 3 + 14
91 = 14 • 6 + 7
14 = 7 • 2
∴ gcd (91, 287) = 7
You might be puzzled as in how did this method work. Basically, this method is formulated from the results
if a = bq + r, then gcd (a, b) = gcd (b, r)
From
a = bq + r
I know that if some integer k divides a, it must divide b and r as well. Now I turn the equation around
a – bq = r
If some integer divides both a and b, then it must divide r. So here, the biggest integer that can divide a, b and r must be the same integer, which is gcd (a, b), and also gcd (b, r). So therefore, the Euclidean Algorithm is valid.
That’s all for this section. The Euclidean Algorithm will be further used in the next section, so make sure you do some practices on it. ☺
No comments:
Post a Comment