Number System - Basics 2

Wednesday, April 26, 2006

Previously we saw classification of numbers, we can further classify natural numbers (from 1 to infinity) as Prime and Composite.

Factor: Let x and y be two integers, if x divides y completely, means the remainder is zero, then we can say that x is a factor of y. Example, 6 and 3, where 3 divides 6 completely, hence 3 is a factor of 6. What are the other factors of 6? Find out.

Multiple: In the above example, 6 is a multiple of 3 and 2 both, hence 3 and 2 are factors of 6 and 6 is a multiple of 3 and 2.

1) Prime Numbers:
If a number has only two factors, unity and itself, then the number is said to be prime. Numbers like 2, 3, 5, 7, etc. For example if we list down the factors of 28 we have 1, 2, 4, 7, 14 and 28. We have more than 2 factors, suppose we list down factors of 31 we only have 2 factors, 1 and 31, hence we can say that 31 is a prime number.

2) Composite Numbers:
In the above example we listed down the factors of 28, which has more than 2 factors, hence such number is known as composite number.

Note: 1 is neither prime nor composite.

Prime numbers from 1 to 200:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199.

It would be helpful to remember primes till 100, because all the composite numbers are composed of prime numbers, we will explore this in later section.

Q1) How to find out if the given number is a prime?
A) Divide the number with all the primes less than its square root. Example, take 29, nearest square is 36, hence the square root of 29 will lie in between of 5 and 6, if the number is divisible by any of the primes less than 6, then it is not a prime number.

Q2) Why does this work?
A) If we divide the number n with its factor x which is greater than its square root, then the result of n/x will be a smaller number than the square root of n, hence we can safely determine if number is prime or not with the above test. We can even say when we multiply with numbers greater than its square root we will get a bigger number then the number itself, hence we just need to check the divisibility with smaller numbers than the square root of the number.

We can use the formula 6n ± 1 to find out prime numbers greater than 3, where n > 0. Example, 6(1) + 1 = 7 and 6(1) - 1 = 5, both 7 and 5 are primes, where n = 1. But it doesn't always work, try few numbers.

3) Relatively Prime or Co-Prime Numbers:
If two or more numbers does not have common factors other than 1 than they are said to be relatively prime or co-primes. In other words the HCF (Highest common factor) of the numbers is 1. We will see HCF in later section. Example, 14 and 15, the Factors of 14 are 1, 2, 7, 14 and the factors of 15 are 1, 3, 5, and 15. There are no common factors other than 1 between 14 and 15, hence they are said to be relatively prime.

Actually, the concept of relatively prime is always used when we reduce the fraction to its smallest term. Example, when we reduce 12/15, we cancel out 3 and we get 4/5, which does not have any more common factors, hence 4 and 5 are relatively prime.

4) Perfect Numbers:
If the sum of the divisors(factors) of a number n is equal to 2n then the number is said to be a perfect number. Example 28, factors of 28 are 1, 2, 4, 7, 14, 28. When we add all the factors of 28 we get 2 x 28 i.e 56. You can exclude the number n in the sum, then you will get the number itself rather than 2n, give it some thought.

The sum of the reciprocals of the factors of a perfect number is always 2.
Example, 1/1 + 1/2 + 1/4 + 1/7 + 1/14 + 1/28 = 2.

5) Even and Odd Numbers:
Numbers can be classified in two groups namely Even or Odd. Any number which is divisible by 2 is an even number can be denoted by 2n, all the other numbers are odd, means which are not divisible by 2 and can be denoted by 2n + 1.

Properties:
Addition or subtraction:
odd ± odd = even.
even ± even = even.
even ± odd = odd.

Multiplication:
odd x odd = odd.
even x even = even.
odd x even = even.

The base determines if the final result is even or odd.
even number raised to even or odd will result in even.
odd number raised to even or odd will result in odd.

Summing it up :

1. Sum of any number of even numbers is even, eg. 2 + 6 + 8 = 16.
2. Sum of even number of odd numbers is even, eg. 1 + 3 + 5 + 7 = 16.
3. Sum of odd number of odd numbers is odd, eg. 5 + 7 + 3 = 15.
4. If the product of numbers is even, at least one of the numbers has to be even.
5. If the product of the numbers is odd, all the numbers have to be odd.

Some more observations:
The product of any 3 consecutive numbers is always divisible by 24 if the first number is even. Why? Because the factors of 24 are 8 x 3, any 3 consecutive numbers multiplied will contain these factors if the first number of the three is even.
If the first number of the 3 numbers is odd then the number will always be divisible by 6 and not 24. Why? Because the result will always contain the factors 2 x 3.

*Note: 2 is the only prime which is even.

Prime numbers play an important role in Number Theory. Understanding of primes, even and odd numbers is essential from the point of view of the exam. We will look into prime, even and odd numbers in more details later when I take up problems.

*TIP: As I mentioned earlier there won't be any silly question in CAT, like, is the number prime or not, but there are questions asked in which the terms are often used. Hence, the concept should be understood in and out.