Divisibility and Prime Numbers: Problem Solving

Hello! Welcome to your first lesson in our CAT Quant preparation course.

Given your goal to master the entire CAT quantitative syllabus and your concern about speed and conceptual clarity, we'll start with the absolute bedrock of the Number System: divisibility and prime numbers. Mastering these concepts is not just about solving specific questions; it's about developing number sense, which will make you faster and more confident across many other topics like HCF & LCM, Time & Work, and more.

Today's lesson will focus on two key areas:

Divisibility Rules: We'll learn quick shortcuts to check if a number is divisible by another, moving from common numbers like 2, 3, and 5 to more complex ones like 7, 11, and 13. We won't just memorize them; we'll understand why they work.
Properties of Prime Numbers: We'll define what prime numbers are and learn a systematic method (an algorithm, if you will) to test if a number is prime—a crucial skill for factorization problems.

Let's begin.

1. Understanding the Logic Behind Divisibility Rules

You've mentioned that you struggle with the conceptual understanding behind formulas. So, instead of just listing rules, let's first see where they come from. Any number can be expressed as a sum of its digits multiplied by powers of 10. For example, 457 is $4 \times 1 0^{2} + 5 \times 1 0^{1} + 7 \times 1 0^{0}$ . This representation is the key to unlocking most divisibility rules.

The following video does an excellent job of explaining the logic for the rules of 2, 4, 8, 3, 9, and 11 based on this principle. Understanding this will help you remember the rules far better than rote memorization.

Divisibility Rules 1 || Number Systems || Quantitative Aptitude || CAT Preparation

Watch this video from the Rodha channel to understand the mathematical reasoning behind the most common divisibility rules. This will build a strong conceptual foundation.

Please watch from the timestamp 01:00 to 20:47. Focus on how the presenter uses the place value expansion of a number to derive the rules for: Powers of 2 and 5 (like 2, 4, 8, 5, 25): Notice how it always boils down to checking the last few digits. 3 and 9: Pay attention to why the sum of the digits becomes the deciding factor. 11: See how the alternating sum of digits arises from the remainders of powers of 10 when divided by 11.

Key Idea from the Video:
The divisibility test for a number 'd' is essentially checking the remainder of a large number when divided by 'd'. Since a number $ab c$ is $100 a + 10 b + c$ , the remainder depends on the remainders of $100$ , $10$ , and $1$ when divided by 'd'.

For 9: $10 \div 9$ gives a remainder of 1, $100 \div 9$ also gives a remainder of 1, and so on. So, $100 a + 10 b + c$ becomes $1 \cdot a + 1 \cdot b + c$ . This is why we just need to check the sum of the digits, $a + b + c$ .
For 4: $100$ is divisible by 4. So any term with $1 0^{2}$ or higher powers will have a remainder of 0. We only need to check the terms that are left: $10 b + c$ , which is the number formed by the last two digits.

2. A Practical Toolkit of Divisibility Rules

Now that you have the conceptual background, let's build a practical toolkit of rules that you can apply quickly in an exam.

Here is a handy chart summarizing the most common rules.

Divisibility Rules Table — A table summarizing divisibility rules for numbers 2 through 10. It provides the condition for each rule and an example, making it a useful quick-reference guide.

Divisibility of Composite Numbers

What about a number like 12? You don't need a new rule. If a number is divisible by 12, it must be divisible by its co-prime factors. Co-prime numbers are numbers that have no common factor other than 1.

For 12, we can use the factors 3 and 4 (they are co-prime).

So, to check for divisibility by 12, simply check for divisibility by 3 AND 4.

We cannot use 2 and 6, because they are not co-prime (they share a common factor of 2).

This principle is extremely useful:

Divisibility by 6: Check for 2 and 3.
Divisibility by 15: Check for 3 and 5.
Divisibility by 18: Check for 2 and 9.

The next video explains this concept and also provides powerful shortcuts for tricky prime numbers like 7 and 13.

Number System || Divisibility Rule (LESSON-2) Tricks to Learn

This video from Feel Free to Learn provides excellent exam-oriented tricks. Pay close attention to how to test for composite numbers and the special methods for certain primes.

Watch the following two segments: Composite Numbers (12:26 - 15:12): This part explains how to use co-prime factors to create divisibility tests for numbers like 6, 12, 14, etc. Tricky Primes (15:12 - 21:34): This segment introduces the 'escalator' method for testing divisibility by 7, 13, 17, and 19. These are great shortcuts to have.

Let's summarize the rules for the tricky primes you just saw. These iterative methods are like small algorithms.

Divisibility by 7: Double the last digit and subtract it from the rest of the number. If the result is divisible by 7, the original number is too. (e.g., For 343 -> $34 - (2 \times 3) = 28$ . Since 28 is divisible by 7, 343 is too).
Divisibility by 13: Multiply the last digit by 4 and add it to the rest of the number. (e.g., For 338 -> $33 + (4 \times 8) = 33 + 32 = 65$ . Since 65 is divisible by 13, 338 is too).
Divisibility by 19: Double the last digit and add it to the rest of the number. (e.g., For 361 -> $36 + (2 \times 1) = 38$ . Since 38 is divisible by 19, 361 is too).

Test your understanding!

Is the number 7308 divisible by 12?

Show answer

To check if 7308 is divisible by 12, we must check if it's divisible by its co-prime factors, 3 and 4.

Divisibility by 4: The rule is to check the last two digits. The last two digits of 7308 form the number '08'. Since 8 is divisible by 4, the entire number 7308 is divisible by 4.
Divisibility by 3: The rule is to check if the sum of the digits is divisible by 3. The sum of digits is $7 + 3 + 0 + 8 = 18$ . Since 18 is divisible by 3, the number 7308 is divisible by 3.

Since 7308 is divisible by both 3 and 4, it is divisible by 12.

3. Understanding Prime Numbers

The second part of our lesson is about prime numbers. Divisibility rules help us find factors, and prime numbers are the fundamental building blocks of all numbers.

Basic number system & Divisibility concepts for CAT

Let's formalize our understanding of prime numbers. This text from an article by Collegedunia clearly defines prime, co-prime, and composite numbers, and outlines the standard method for testing primality.

Please read the section titled 'BASIC Numbers'. Focus on the definitions of: Prime Numbers: A number divisible only by 1 and itself. How to test whether a number is prime or not: This is the most important part. Understand the logic of checking for divisibility only by primes up to the square root of the number. Co-prime Numbers: Two numbers with no common factors other than 1.

The Primality Test: A Step-by-Step Method

As you just read, to check if a number $N$ is prime, you don't need to check for divisibility by every number up to $N$ . You only need to check for divisibility by prime numbers up to $N$ .

Example: Is 191 a prime number?

Find the approximate square root: $191$ . We know $1 3^{2} = 169$ and $1 4^{2} = 196$ . So, $191$ is between 13 and 14.
List primes up to $191$ : The prime numbers less than 14 are 2, 3, 5, 7, 11, 13.
Test for divisibility:
- 191 is not divisible by 2 (it's odd).
- Sum of digits $1 + 9 + 1 = 11$ , not divisible by 3.
- Doesn't end in 0 or 5, so not divisible by 5.
- $19 - (2 \times 1) = 17$ . Not divisible by 7.
- Alternating sum $1 - 9 + 1 = - 7$ . Not divisible by 11.
- $191 \div 13$ . $13 \times 10 = 130$ , $191 - 130 = 61$ . 61 is not a multiple of 13. So, not divisible by 13.

Since 191 is not divisible by any prime number up to its square root, 191 is a prime number.

Now, try applying this method to the following problem.

Primality Test and Prime Factorization Practice — This image provides an exercise to test your understanding of primality. First, check if the numbers are prime using the square root method. If they are not prime, express them as a product of their prime factors.

Test your understanding!

Let's solve for the first number, 323.

Approximate $323$ : We know $1 7^{2} = 289$ and $1 8^{2} = 324$ . So, $323$ is approximately 18.
List primes to check: 2, 3, 5, 7, 11, 13, 17.
Test: We can skip 2, 3, 5 by basic rules.
- 7: $32 - (2 \times 3) = 26$ . Not divisible by 7.
- 11: $3 - 2 + 3 = 4$ . Not divisible by 11.
- 13: $32 + (4 \times 3) = 44$ . Not divisible by 13.
- 17: Let's do the division. $323 \div 17$ . $17 \times 10 = 170$ . $323 - 170 = 153$ . Is 153 divisible by 17? $17 \times 9 = (10 + 7) \times 9 = 90 + 63 = 153$ . Yes!
  So, $323 = 17 \times 19$ .

Now try the same for 449, 143, and 599.

Show answers

* **449:** $\sqrt{449} \approx 21.2$. Primes to check: 2, 3, 5, 7, 11, 13, 17, 19. You will find that 449 is not divisible by any of them. It is **PRIME**. * **143:** $\sqrt{143} \approx 11.9$. Primes to check: 2, 3, 5, 7, 11. It's clearly not divisible by 2, 3, 5. Let's check 11: Alternating sum is $1 - 4 + 3 = 0$. It is divisible by 11! So, $143 = 11 \times 13$. * **599:** $\sqrt{599} \approx 24.5$. Primes to check: up to 23. After testing, you'll find it's not divisible by any of them. It is **PRIME**.

Conclusion

Excellent work today! We've laid a critical foundation for the entire quantitative section.

Here are the key takeaways:

Divisibility rules are shortcuts based on number properties. Understanding the 'why' (place value) helps you remember and apply them.
Common Rules:
- Powers of 2 & 5 (2, 4, 8, 5, 25): Check the last 1, 2, or 3 digits.
- 3 & 9: Check if the sum of digits is divisible.
- 11: Check if the alternating sum of digits is 0 or a multiple of 11.
Composite Number Rule: To check for divisibility by a composite number (like 12), check for divisibility by its co-prime factors (3 and 4).
Primality Test: To check if $N$ is prime, test for divisibility only by prime numbers up to $N$ .

In our next lesson, we will build directly on this foundation. Now that we know how to find factors, we will learn how to find the Highest Common Factor (HCF) and Lowest Common Multiple (LCM) of numbers and apply these concepts to solve classic CAT word problems.