Prime Numbers, Composite Numbers and Divisibility

Welcome to this essential topic in Algebra and Number Theory! Understanding prime numbers, composite numbers, and divisibility is fundamental to many areas of mathematics, including cryptography, number theory, and even basic arithmetic. Let's break down these concepts step by step.

What are Natural Numbers?

Before diving into primes and composites, let's quickly define natural numbers. Natural numbers are the positive whole numbers: 1, 2, 3, 4, 5, and so on. Sometimes, zero is included, but for the context of prime and composite numbers, we focus on numbers greater than 1.

What are Factors and Multiples?

To understand prime and composite numbers, we first need to grasp the concepts of factors and multiples.

Factors

A factor of a number is any number that divides into it exactly, with no remainder. For example, the factors of 12 are 1, 2, 3, 4, 6, and 12 because each of these numbers divides 12 evenly.

Multiples

A multiple of a number is the result of multiplying that number by any whole number. For example, the multiples of 5 are 5 (5x1), 10 (5x2), 15 (5x3), 20 (5x4), and so on.

Understanding Divisibility

Divisibility is the concept of whether one number can be divided by another number without leaving a remainder. If a number 'a' is divisible by a number 'b', it means that 'b' is a factor of 'a'.

For example, 15 is divisible by 3 because 15 ÷ 3 = 5, with no remainder. However, 15 is not divisible by 4 because 15 ÷ 4 = 3 with a remainder of 3.

Divisibility Rules

Memorizing divisibility rules can save a lot of time when checking if a number is divisible by another, especially for larger numbers. Here are some common divisibility rules:

  • Divisibility by 2: A number is divisible by 2 if its last digit is even (0, 2, 4, 6, or 8). Example: 134 is divisible by 2.
  • Divisibility by 3: A number is divisible by 3 if the sum of its digits is divisible by 3. Example: 246. Sum of digits = 2 + 4 + 6 = 12. Since 12 is divisible by 3, 246 is divisible by 3.
  • Divisibility by 4: A number is divisible by 4 if the number formed by its last two digits is divisible by 4. Example: 716. The last two digits form 16. Since 16 is divisible by 4, 716 is divisible by 4.
  • Divisibility by 5: A number is divisible by 5 if its last digit is 0 or 5. Example: 125 is divisible by 5.
  • Divisibility by 6: A number is divisible by 6 if it is divisible by both 2 and 3. Example: 132 is divisible by 2 (ends in 2) and by 3 (1+3+2=6, which is divisible by 3). Therefore, 132 is divisible by 6.
  • Divisibility by 7: There isn't a simple rule, but one method is to double the last digit and subtract it from the remaining number. If the result is divisible by 7, the original number is too. Example: 343. Double the last digit (3) is 6. Subtract from 34: 34 - 6 = 28. Since 28 is divisible by 7, 343 is divisible by 7.
  • Divisibility by 8: A number is divisible by 8 if the number formed by its last three digits is divisible by 8. Example: 5128. The last three digits form 128. Since 128 ÷ 8 = 16, 5128 is divisible by 8.
  • Divisibility by 9: A number is divisible by 9 if the sum of its digits is divisible by 9. Example: 729. Sum of digits = 7 + 2 + 9 = 18. Since 18 is divisible by 9, 729 is divisible by 9.
  • Divisibility by 10: A number is divisible by 10 if its last digit is 0. Example: 500 is divisible by 10.
  • Divisibility by 11: A number is divisible by 11 if the alternating sum of its digits is divisible by 11. Example: 1331. Alternating sum: 1 - 3 + 3 - 1 = 0. Since 0 is divisible by 11, 1331 is divisible by 11. Another example: 9482. Alternating sum: 9 - 4 + 8 - 2 = 11. Since 11 is divisible by 11, 9482 is divisible by 11.

Prime Numbers

A prime number is a natural number greater than 1 that has exactly two distinct positive divisors: 1 and itself. In simpler terms, it cannot be formed by multiplying two smaller natural numbers.

Let's look at some examples:

  • 2: The only divisors are 1 and 2. It's the smallest prime number and the only even prime number.
  • 3: The only divisors are 1 and 3.
  • 5: The only divisors are 1 and 5.
  • 7: The only divisors are 1 and 7.
  • 11: The only divisors are 1 and 11.
  • 13: The only divisors are 1 and 13.

The number 1 is NOT a prime number. It only has one divisor (itself). Prime numbers must have exactly *two* distinct divisors.

Mnemonic for first few primes: Think of a racecar driver named "Primus". He loves to drive fast (2), has a lucky number 3, drives a sleek car that looks like a 5, and his pit crew is a team of 7. He often needs to go to 11 and then 13 for repairs.

Composite Numbers

A composite number is a natural number greater than 1 that has more than two distinct positive divisors. This means a composite number can be formed by multiplying two smaller natural numbers (other than 1 and itself).

Let's look at some examples:

  • 4: Divisors are 1, 2, and 4. It can be formed by 2 x 2.
  • 6: Divisors are 1, 2, 3, and 6. It can be formed by 2 x 3.
  • 8: Divisors are 1, 2, 4, and 8. It can be formed by 2 x 4.
  • 9: Divisors are 1, 3, and 9. It can be formed by 3 x 3.
  • 10: Divisors are 1, 2, 5, and 10. It can be formed by 2 x 5.
  • 12: Divisors are 1, 2, 3, 4, 6, and 12. It can be formed by 2 x 6 or 3 x 4.

Every natural number greater than 1 is either a prime number or a composite number. There is no overlap, and no number (greater than 1) can be neither.

The Fundamental Theorem of Arithmetic

This is a very important theorem in number theory. It states that every integer greater than 1 either is a prime number itself or can be represented as a product of prime numbers, and this representation is unique, apart from the order of the factors.

This means that every composite number has a unique "prime factorization."

Examples of prime factorization:

  • 12 = 2 x 2 x 3 (or 22 x 3)
  • 30 = 2 x 3 x 5
  • 100 = 2 x 2 x 5 x 5 (or 22 x 52)
  • 72 = 2 x 2 x 2 x 3 x 3 (or 23 x 32)

How to Find the Prime Factorization of a Number

We can use a method called a "factor tree" or repeated division by prime numbers.

Method 1: Factor Tree

Let's find the prime factorization of 72.

  1. Start with 72. Find any two factors (it doesn't matter which pair you choose first). Let's use 8 and 9.
  2. Write 72 = 8 x 9.
  3. Now, look at 8. Is it prime? No. Find two factors of 8, say 2 and 4. Write 72 = 2 x 4 x 9.
  4. Look at 4. Is it prime? No. Find two factors of 4, which are 2 and 2. Write 72 = 2 x 2 x 2 x 9.
  5. Look at 9. Is it prime? No. Find two factors of 9, which are 3 and 3. Write 72 = 2 x 2 x 2 x 3 x 3.
  6. Now, all the numbers at the end of the branches (2, 2, 2, 3, 3) are prime numbers. We have found the prime factorization.

Method 2: Repeated Division

Let's find the prime factorization of 72 using this method.

  1. Start with the smallest prime number, 2. Can 72 be divided by 2? Yes. 72 ÷ 2 = 36. Write down 2.
  2. Now, take the result, 36. Can it be divided by 2? Yes. 36 ÷ 2 = 18. Write down another 2.
  3. Take 18. Can it be divided by 2? Yes. 18 ÷ 2 = 9. Write down another 2.
  4. Take 9. Can it be divided by 2? No. Move to the next smallest prime number, 3. Can 9 be divided by 3? Yes. 9 ÷ 3 = 3. Write down a 3.
  5. Take 3. Can it be divided by 3? Yes. 3 ÷ 3 = 1. Write down a 3.
  6. We have reached 1, so we stop. The prime factors are the numbers we wrote down: 2, 2, 2, 3, 3.

So, the prime factorization of 72 is 2 x 2 x 2 x 3 x 3, which can be written in exponential form as 23 x 32.

Exam Tip: When asked to find the prime factorization, always ensure you break down the number all the way to its prime components. For example, if you write 12 = 3 x 4, this is not the prime factorization because 4 is not a prime number. The correct prime factorization is 12 = 2 x 2 x 3.

Relationship between Prime, Composite, and Divisibility

These concepts are deeply interconnected.

  • A number is prime if its only divisors are 1 and itself.
  • A number is composite if it has divisors other than 1 and itself. These "other" divisors are always less than the number itself.
  • The divisibility rules help us quickly identify potential factors, which in turn helps us determine if a number is prime or composite. For example, if a number ends in 0, we know it's divisible by 2, 5, and 10, so it must be composite (unless the number is 2, 5, or 10 itself, but we are considering numbers greater than 1).

Why are Prime Numbers Important?

Prime numbers are often called the "building blocks" of integers because of the Fundamental Theorem of Arithmetic. They are crucial in many advanced mathematical fields:

  • Cryptography: The security of many encryption methods (like RSA) relies on the fact that it is very difficult to find the prime factors of extremely large composite numbers.
  • Number Theory: They are central to many unsolved problems and theorems in number theory.
  • Computer Science: Used in algorithms for hashing, random number generation, and data structures.

Summary Table

Let's summarize the key distinctions:

Feature Prime Number Composite Number Number 1
Definition Natural number > 1 with exactly two distinct positive divisors (1 and itself). Natural number > 1 with more than two distinct positive divisors. Natural number.
Number of Divisors Exactly 2 More than 2 Exactly 1
Examples 2, 3, 5, 7, 11, 13, 17, 19... 4, 6, 8, 9, 10, 12, 14, 15... 1
Can be formed by multiplying smaller natural numbers? No Yes No (only 1x1)

Practice Problems

Try these to test your understanding:

  1. Is 97 a prime number? How can you tell?
  2. Find the prime factorization of 144.
  3. List all the divisors of 36. Identify if 36 is prime or composite.
  4. Which of the following numbers are divisible by 3? 234, 567, 891, 1012.
  5. Explain why 1 is neither prime nor composite.

Answers to Practice Problems:

  1. To check if 97 is prime, we can try dividing it by prime numbers up to the square root of 97 (which is roughly 9.8). The primes to check are 2, 3, 5, 7. 97 is not divisible by 2 (it's odd). The sum of digits (9+7=16) is not divisible by 3. It doesn't end in 0 or 5, so not divisible by 5. 97 ÷ 7 = 13 with a remainder of 6. Since it's not divisible by any prime up to its square root, 97 is prime.
  2. 144 = 2 x 72 = 2 x 2 x 36 = 2 x 2 x 2 x 18 = 2 x 2 x 2 x 2 x 9 = 2 x 2 x 2 x 2 x 3 x 3, or 24 x 32.
  3. Divisors of 36 are: 1, 2, 3, 4, 6, 9, 12, 18, 36. Since 36 has more than two divisors, it is a composite number.
  4. 234: 2+3+4=9 (divisible by 3). Yes. 567: 5+6+7=18 (divisible by 3). Yes. 891: 8+9+1=18 (divisible by 3). Yes. 1012: 1+0+1+2=4 (not divisible by 3). No.
  5. The definition of a prime number requires exactly *two* distinct positive divisors (1 and itself). The number 1 only has one divisor (1). The definition of a composite number requires *more than two* distinct positive divisors. Since 1 does not meet either of these criteria, it is classified as neither prime nor composite.
All E-Books
Online Test Prime Numbers, Composite Numbers and Divisibility One Line Questions Prime Numbers, Composite Numbers and Divisibility Question Bank Prime Numbers, Composite Numbers and Divisibility