Number Theory Basics

Number theory is the study of integers and their properties, including divisibility, primes, and integer solutions to equations.

Key Concepts in Number Theory

Divisibility

An integer a divides another integer b if there exists an integer k such that b = a \times k.

Prime Numbers

A prime number is an integer greater than 1 that has no positive divisors other than 1 and itself.

Examples: 2, 3, 5, 7, 11, 13, 17

Greatest Common Divisor (GCD)

The greatest common divisor or Highest Common Factor (HCF) of two integers is the largest integer that divides both.

Notation: gcd(a, b)

Least Common Multiple (LCM)

The least common multiple of two integers is the smallest positive integer divisible by both.

Notation: lcm(a, b)

Example 1: Find gcd(24, 36) and lcm(24, 36).

Solution:

  • gcd(24, 36) = 12
  • lcm(24, 36) = 72

Example 2: Is 29 a prime number?

Solution: Yes, because it has no divisors other than 1 and 29.

Step-by-Step Solutions

How to Find GCD Using Euclidean Algorithm

  1. Divide the larger number by the smaller number and find the remainder.
  2. Replace the larger number with the smaller number, and the smaller number with the remainder.
  3. Repeat until the remainder is 0.
  4. The non-zero remainder just before 0 is the GCD.

How to Check if a Number is Prime

  1. Check divisibility by all prime numbers less than or equal to the square root of the number.
  2. If none divide the number, it is prime.

Practice Problems

1. Find the gcd(48, 180).

2. Check if 37 is a prime number.

3. Find the lcm(12, 15).

4. Is 51 a prime number?