👁 Preview — Study, Practice and Revise are open; mock tests and the rest of the syllabus unlock on subscription. Unlock all · ₹4,999
← Back to Number System
Study mode

Applications in Number Theory

Study Practice Revise 🔒 Test

Introduction

Number theory is a branch of mathematics that deals with the properties and relationships of numbers, especially integers. In competitive exams, number theory forms the backbone of many quantitative aptitude problems. Understanding concepts like divisibility, factorization, and modular arithmetic allows you to solve complex problems quickly and accurately without resorting to lengthy calculations.

In this section, we will explore how fundamental number concepts apply to problem-solving, learn shortcuts through divisibility rules, use the remainder theorem and division algorithm to handle remainders efficiently, work with different number bases, and apply modular arithmetic to solve congruences and remainder problems. These tools are essential for cracking entrance exams with confidence.

Prime and Composite Numbers

Before diving into applications, it's important to understand two fundamental types of numbers:

  • Prime Numbers: A prime number is a natural number greater than 1 that has exactly two distinct positive divisors: 1 and itself. For example, 2, 3, 5, 7 are prime numbers.
  • Composite Numbers: A composite number is a natural number greater than 1 that has more than two positive divisors. For example, 4, 6, 8, 9 are composite numbers.

Note that 1 is neither prime nor composite.

Prime and Composite Numbers (1 to 20)
Number Status
1Neither prime nor composite
2Prime
3Prime
4Composite
5Prime
6Composite
7Prime
8Composite
9Composite
10Composite
11Prime
12Composite
13Prime
14Composite
15Composite
16Composite
17Prime
18Composite
19Prime
20Composite

Why are prime numbers important? Because every composite number can be uniquely expressed as a product of prime numbers. This is called prime factorization, and it is the foundation for finding the Greatest Common Divisor (GCD) and Least Common Multiple (LCM) of numbers.

Divisibility Rules

Divisibility rules help us quickly determine whether one number divides another without performing full division. This saves time in factorization and remainder problems.

Common Divisibility Rules
Divisor Divisibility Rule Example
2 Number ends with 0, 2, 4, 6, or 8 124 is divisible by 2
3 Sum of digits divisible by 3 123 (1+2+3=6) divisible by 3
5 Number ends with 0 or 5 145 ends with 5, divisible by 5
7 Double last digit, subtract from remaining number; result divisible by 7 203: 20 - (3x2)=20-6=14 divisible by 7
11 Difference between sum of digits in odd and even positions divisible by 11 121: (1+1) - 2 = 0 divisible by 11
13 Multiply last digit by 4, add to remaining number; result divisible by 13 273: 27 + (3x4)=27+12=39 divisible by 13

Remainder Theorem and Division Algorithm

When dividing numbers or polynomials, understanding the relationship between dividend, divisor, quotient, and remainder is crucial.

Division Algorithm: For any integers \(a\) (dividend) and \(b\) (divisor, \(b eq 0\)), there exist unique integers \(q\) (quotient) and \(r\) (remainder) such that:

\[ a = bq + r, \quad 0 \leq r < |b| \]

This means when you divide \(a\) by \(b\), the remainder \(r\) is always less than the divisor \(b\).

graph TD    A[Start with dividend a and divisor b]    A --> B[Divide a by b to get quotient q]    B --> C[Calculate remainder r = a - bq]    C --> D{Is 0 ≤ r < |b|?}    D -->|Yes| E[Division Algorithm complete: a = bq + r]    D -->|No| F[Adjust q and r accordingly]    F --> E

Remainder Theorem: When a polynomial \(f(x)\) is divided by a linear divisor \((x - a)\), the remainder is simply \(f(a)\). This allows quick calculation of remainders without performing full polynomial division.

Number Bases and Base Conversion

Numbers can be represented in different bases (or radix), which is the number of unique digits including zero used to represent numbers.

  • Binary (Base 2): Uses digits 0 and 1. Common in computer science.
  • Octal (Base 8): Uses digits 0 to 7.
  • Decimal (Base 10): Uses digits 0 to 9. Our everyday number system.
  • Hexadecimal (Base 16): Uses digits 0 to 9 and letters A to F (representing 10 to 15).

Converting numbers between bases is essential for understanding computer-related problems and some competitive exam questions.

Base Conversion Examples
Decimal Binary (Base 2) Octal (Base 8) Hexadecimal (Base 16)
10101012A
3111111371F
156100111002349C
25511111111377FF

Arithmetic in Different Bases: Addition, subtraction, multiplication, and division follow the same principles as decimal but carry over or borrow according to the base.

Modular Arithmetic and Congruences

Modular arithmetic deals with integers wrapped around after reaching a certain value called the modulus. It is like the arithmetic of a clock, where after 12 hours, the count resets to 0.

Definition: For integers \(a\), \(b\), and modulus \(m > 0\), we say:

\[ a \equiv b \pmod{m} \iff m \mid (a - b) \]

This means \(a\) and \(b\) leave the same remainder when divided by \(m\).

graph TD    A[Start with numbers a and b, modulus m]    A --> B[Calculate a mod m and b mod m]    B --> C{Are remainders equal?}    C -->|Yes| D[a ≡ b (mod m)]    C -->|No| E[a ≠ b (mod m)]

Modular arithmetic simplifies calculations in remainder problems, cyclic patterns, and solving congruence equations.

Key Concept

Modular Arithmetic

Numbers wrap around after reaching the modulus, similar to hours on a clock.

Worked Examples

Example 1: Finding GCD and LCM of 84 and 126 Easy
Find the Greatest Common Divisor (GCD) and Least Common Multiple (LCM) of 84 and 126 using prime factorization.

Step 1: Prime factorize both numbers.

84 = 2 x 2 x 3 x 7 = \(2^2 \times 3^1 \times 7^1\)

126 = 2 x 3 x 3 x 7 = \(2^1 \times 3^2 \times 7^1\)

Step 2: For GCD, take the minimum powers of common primes.

GCD = \(2^{\min(2,1)} \times 3^{\min(1,2)} \times 7^{\min(1,1)} = 2^1 \times 3^1 \times 7^1 = 42\)

Step 3: For LCM, take the maximum powers of all primes involved.

LCM = \(2^{\max(2,1)} \times 3^{\max(1,2)} \times 7^{\max(1,1)} = 2^2 \times 3^2 \times 7^1 = 252\)

Answer: GCD = 42, LCM = 252

Example 2: Check divisibility of 123456 by 3 and 11 Medium
Determine if 123456 is divisible by 3 and by 11 using divisibility rules.

Step 1: Check divisibility by 3 by summing digits.

Sum = 1 + 2 + 3 + 4 + 5 + 6 = 21

Since 21 is divisible by 3, 123456 is divisible by 3.

Step 2: Check divisibility by 11 by taking difference of sums of digits in odd and even positions.

Positions (from right):

  • Odd positions: 6 (1st), 4 (3rd), 2 (5th) -> sum = 6 + 4 + 2 = 12
  • Even positions: 5 (2nd), 3 (4th), 1 (6th) -> sum = 5 + 3 + 1 = 9

Difference = 12 - 9 = 3, which is not divisible by 11.

Therefore, 123456 is not divisible by 11.

Answer: Divisible by 3 but not by 11.

Example 3: Find remainder when \(x^3 + 2x^2 - x + 5\) is divided by \(x - 2\) Medium
Use the remainder theorem to find the remainder when the polynomial \(f(x) = x^3 + 2x^2 - x + 5\) is divided by \(x - 2\).

Step 1: According to the remainder theorem, the remainder is \(f(2)\).

Calculate \(f(2) = (2)^3 + 2(2)^2 - 2 + 5 = 8 + 8 - 2 + 5 = 19\).

Answer: The remainder is 19.

Example 4: Convert decimal 156 to binary and add 1011 (binary) Medium
Convert the decimal number 156 to binary and add the binary number 1011 to it.

Step 1: Convert 156 to binary.

Divide 156 by 2 repeatedly:

  • 156 / 2 = 78 remainder 0
  • 78 / 2 = 39 remainder 0
  • 39 / 2 = 19 remainder 1
  • 19 / 2 = 9 remainder 1
  • 9 / 2 = 4 remainder 1
  • 4 / 2 = 2 remainder 0
  • 2 / 2 = 1 remainder 0
  • 1 / 2 = 0 remainder 1

Binary (from bottom to top): 10011100

Step 2: Add binary 1011 (which is 11 in decimal) to 10011100.

Align digits:

      10011100    +     1011    ------------

Perform binary addition:

  • 0 + 1 = 1
  • 0 + 1 = 1
  • 1 + 0 = 1
  • 1 + 1 = 10 (write 0, carry 1)
  • 1 + 0 + 1 (carry) = 10 (write 0, carry 1)
  • 0 + 0 + 1 (carry) = 1
  • 0 + 0 = 0
  • 1 + 0 = 1

Result: 10100111

Answer: 156 in binary is 10011100; adding 1011 gives 10100111.

Example 5: Solve \(7x \equiv 4 \pmod{11}\) Hard
Find all integer solutions \(x\) such that \(7x \equiv 4 \pmod{11}\).

Step 1: We want to solve for \(x\) in the congruence:

\(7x \equiv 4 \pmod{11}\)

Step 2: Find the modular inverse of 7 modulo 11, i.e., find \(k\) such that:

\(7k \equiv 1 \pmod{11}\)

Try values of \(k\):

  • 7 x 8 = 56 ≡ 1 (mod 11), since 56 - 55 = 1

So, the inverse of 7 mod 11 is 8.

Step 3: Multiply both sides of the original congruence by 8:

\(8 \times 7x \equiv 8 \times 4 \pmod{11}\)

\(x \equiv 32 \pmod{11}\)

Calculate \(32 \mod 11\): 32 - 2x11 = 32 - 22 = 10

Answer: \(x \equiv 10 \pmod{11}\). All integers congruent to 10 modulo 11 satisfy the equation.

Greatest Common Divisor (GCD)

\[\mathrm{GCD}(a,b) = \prod p_i^{\min(\alpha_i, \beta_i)}\]

Highest common factor from prime factorization

\(p_i\) = prime factors
\(\alpha_i, \beta_i\) = exponents in factorization of a and b

Least Common Multiple (LCM)

\[\mathrm{LCM}(a,b) = \prod p_i^{\max(\alpha_i, \beta_i)}\]

Smallest common multiple from prime factorization

\(p_i\) = prime factors
\(\alpha_i, \beta_i\) = exponents in factorization of a and b

Division Algorithm

\[a = bq + r, \quad 0 \leq r < |b|\]

Expresses division with quotient and remainder

a = dividend
b = divisor
q = quotient
r = remainder

Modular Arithmetic

\[a \equiv b \pmod{m} \iff m \mid (a - b)\]

Congruence relation modulo m

a, b = integers
m = modulus

Remainder Theorem

\[Remainder \text{ when } f(x) \text{ divided by } (x - a) \text{ is } f(a)\]

Quickly find remainder of polynomial division

f(x) = polynomial
a = constant

Tips & Tricks

Tip: Use the sum of digits rule to quickly check divisibility by 3 or 9.

When to use: When you need to verify divisibility of large numbers without full division.

Tip: Prime factorization is the fastest way to find GCD and LCM, especially for multiple numbers.

When to use: When dealing with problems involving common factors or multiples.

Tip: Apply the remainder theorem to avoid lengthy polynomial division.

When to use: When asked for the remainder of a polynomial divided by a linear factor.

Tip: Convert numbers to decimal before performing arithmetic in other bases if unsure.

When to use: When addition, subtraction, or multiplication in binary, octal, or hexadecimal seems complex.

Tip: Use modular inverses to solve linear congruences efficiently.

When to use: When solving equations like \(ax \equiv b \pmod{m}\) in competitive exams.

Common Mistakes to Avoid

❌ Including 1 as a prime number
✓ Remember that 1 is neither prime nor composite; primes have exactly two distinct positive divisors.
Why: Misunderstanding the definition leads to incorrect factorization and problem-solving errors.
❌ Misapplying divisibility rules for 7 and 11
✓ Follow the specific step-by-step rules carefully and practice examples to build familiarity.
Why: These rules are less intuitive and often cause confusion.
❌ Forgetting that remainder must be less than the divisor in the division algorithm
✓ Always ensure remainder \(r\) satisfies \(0 \leq r < |b|\).
Why: Misunderstanding this leads to incorrect quotient and remainder calculations.
❌ Errors in base conversion due to mixing place values
✓ Review place values and powers of the base before converting.
Why: Confusing digits and place values across bases causes incorrect conversions.
❌ Treating modular congruence as equality
✓ Understand that \(a \equiv b \pmod{m}\) means \(a\) and \(b\) differ by a multiple of \(m\), not that they are equal.
Why: Misinterpretation leads to wrong conclusions in modular arithmetic problems.
Curated videos per subtopic
Top YouTube explainers, AI-ranked for your exam and language. Unlocks with subscription.
Unlock

Try Practice next.

Progress tracking is paywalled — subscribe to mark subtopics as understood and save your streak.

Go to practice →
Ask a doubt
Applications in Number Theory · 10 free messages
Ask me anything about this subtopic. You have 10 free messages this session — chat history isn't saved in preview.