Number theory is a branch of mathematics which helps to study the set of positive whole numbers.

1 Divisibility

• The notatotion a | b means “a divides b”.
• The notatotion a ∤ b means “a does not divide b”.
• When a divides b, we say that a is a factor of b and b is a multiple of a.
• Divisibility Theorems
  • If n and d are integers, then n is divisible by d if and only if n = dk for some integer k.
  • If a | b and a | c, then a | (b + c)
  • If a | b, then a | bc for all integers c
  • If a | b and b | c, then a | c (transitivity)
• Prime numbers are integers greater than 1 whose only positive divisors are itself and 1.

2 Greatest Common Divisor

If we assume that a|b and a|c, then we can say that a is the common divisor of b and c. The greatest common divisor is the greatest among all the commom divisors of b and c and it is denoted as gcd(b,c).

Example

Find the greatest common divisor of (24,30).

The factors of 30 are: 1,2,3,5,6,10,15,30

The factors of 24 are: 1,2,3,4,6,8,12,24

Common Factors: 1,2,3,6

gcd(24, 30) = 6

2.1 Prime factorisation

Another method to find the GCD is by using prime factorisation.

Example

Find the greatest common divisor of 120 and 500.

gcd(120, 500) = 2^min(3,2) ⋅ 3^min(1,0) ⋅ 5^min(1,3)

gcd(120, 500) = 2² ⋅ 3⁰ ⋅ 5¹ = 20

• The integers a and b are relatively prime if their greatest common divisor is 1.

3 Lowest Common Multiples

The least common multiple of the positive integers a and b is the smallest positive integer that is divisible by both a and b. The least common multiple of a and b is denoted by lcm(a, b).

• Finding LCM using prime factorisaiton:

Example

Find the least common multiple of 120 and 500.

lcm(120, 500) = 2^max(3,2) ⋅ 3^max(1,0) ⋅ 5^max(1,3)

lcm(120, 500) = 2³ ⋅ 3¹ ⋅ 5³ = 3000

4 Division Algorithm

If a is an integer and d is a positive integer, then there exists unique integers q and r, with 0 ≤ r < d, such that a = dq + r.

• d is called the divisor
• a is called the dividend
• q is called the quotient
• r is called the remainder

5 Euclidean Algorithm

Let a = bq + r, where a, b, q, r are integers. Then gcd(a, b) = gcd(b, r).

Example

gcd(1001, 1331)

1331 = 1001(1) + 330

1001 = 330(3) + 11

330 = 11(30) + 0

gcd(1001, 1331) = gcd(1001, 330) = gcd(330, 11) = gcd(11, 0) = 11

6 Modular Arithmetic

Let a be an integer and m be a positive integer. We denote the remainder when a is divided by m with “a mod m”.

Examples

9 mod 4 = 1

-13 mod 4 = 3

7 Modular Congruences

Let a and b be integers and m be a positive integer.

• We say that a is congruent to b modulo m if and only if m | (a – b).
• Two integers are congruent mod m if and only if they have the same remainder when divided by m (i.e. a ≡ b (mod m) if and only if a mod m = b mod m)

Example

1. Is 80 congruent to 5 mod 17?

   8 = 17(4) + 12

   No as 17 does not divide (80 - 5).

2. Is -29 congruent to 5 mod 17?

   -29 = 17(-2) + 5

   Yes as 17 divides (-29 - 5).