Overview

  • A prime number is a natural number greater than 1 that has only two factors: 1 and itself.
  • Identifying primes is essential in factorization, cryptography, and competitive exams.

Basic Tests for Small Numbers

  • If a number is less than 2, it is not prime.
  • If a number is exactly 2, it is prime (the only even prime).
  • If a number is even and greater than 2, it is composite.
  • Check divisibility by 3, 5, 7, 11 for numbers up to 100.

Trial Division Method

  • Divide the number by all prime numbers less than or equal to its square root.
  • If no divisor is found, the number is prime.
  • Example: To check 29, test divisibility by 2, 3, and 5.

Sieve of Eratosthenes

  • A method to find all primes up to a given limit n.
  • Write numbers from 2 to n.
  • Repeatedly mark multiples of each unmarked number as composite.
  • The unmarked numbers are prime numbers.
  • Useful for generating a list of primes up to 100 or 1000.

Divisibility Tests

  • If a number ends with 0 or 5, check divisibility by 5.
  • If the sum of digits is divisible by 3, the number is composite.
  • If the last digit is even and number >2, it is composite.

Fermat’s Primality Test

  • A probabilistic test based on Fermat's Little Theorem.
  • If a^(n−1) ≡ 1 mod n, n is likely prime.
  • Used for very large numbers but can give false positives (Carmichael numbers).

Miller-Rabin Primality Test

  • A more reliable probabilistic test for large numbers.
  • Based on checking certain conditions using modular exponentiation.
  • Widely used in cryptography applications.

AKS Primality Test

  • A deterministic test that runs in polynomial time.
  • Proves whether a number is prime with certainty.
  • Less common in exams but important in theoretical studies.

Checking by Divisibility Patterns

  • If a number >2 is even, it is not prime.
  • If last digit is 0 or 5, it is divisible by 5 (except 5 itself).
  • If sum of digits divisible by 3 or 9, the number is composite.

Prime Number Properties Useful in Tests

  • All primes >3 are of the form 6n ± 1.
  • There are no two consecutive prime numbers except 2 and 3.
  • Every composite number has a prime factor ≤ its square root.

Example Applications

  • Check if 83 is prime: Divisible by 2? No. 3? 8+3=11, not divisible. 5? No. 7? No. So prime.
  • Check 91: Divisible by 7 (7×13=91), so composite.

Common Mistakes to Avoid

  • Assuming all odd numbers are prime (e.g., 9, 15 are composite).
  • Forgetting that 2 is the only even prime.
  • Thinking 1 is prime (it is not).

Tips for Competitive Exams

  • Memorize primes up to 100 for faster recognition.
  • Use trial division for numbers up to 500.
  • Remember special divisibility rules for quick elimination.

Miscellaneous Facts

  • Prime tests are fundamental in factorization and encryption.
  • They improve speed in HCF and LCM calculations.
  • Knowing primes aids in solving number series and patterns.

Category

Questions