Number Theory Basics

Introduction to Number Theory

Number Theory is a branch of mathematics that deals with the properties and relationships of numbers, especially integers. It is one of the oldest and most fundamental areas of mathematics, with applications in cryptography, computer science, and coding theory.

The Set of Integers

Definition

Integers are whole numbers that can be positive, negative, or zero.

Notation: ℤ = {…, -3, -2, -1, 0, 1, 2, 3, …}

Subsets of Integers

1. Natural Numbers (ℕ): {1, 2, 3, 4, 5, …}

   • Sometimes includes 0: {0, 1, 2, 3, …}

2. Whole Numbers: {0, 1, 2, 3, 4, …}

   • Natural numbers plus zero

3. Positive Integers (ℤ⁺): {1, 2, 3, 4, …}

4. Negative Integers (ℤ⁻): {-1, -2, -3, -4, …}

5. Non-negative Integers: {0, 1, 2, 3, …}

Basic Number Classifications

Even and Odd Numbers

Even Number: An integer n is even if n = 2k for some integer k.

Examples: 0, 2, 4, 6, 8, -2, -4, -6

• 0 = 2(0) → even
• 6 = 2(3) → even
• -4 = 2(-2) → even

Odd Number: An integer n is odd if n = 2k + 1 for some integer k.

Examples: 1, 3, 5, 7, -1, -3, -5

• 1 = 2(0) + 1 → odd
• 7 = 2(3) + 1 → odd
• -3 = 2(-2) + 1 → odd

Important Properties:

• Every integer is either even or odd (never both)
• Even + Even = Even
• Odd + Odd = Even
• Even + Odd = Odd
• Even × Even = Even
• Odd × Odd = Odd
• Even × Odd = Even

Positive, Negative, and Zero

Positive Numbers: Greater than 0 (1, 2, 3, …)

Negative Numbers: Less than 0 (-1, -2, -3, …)

Zero: Neither positive nor negative

Divisibility

Definition

Let a and b be integers with a ≠ 0. We say a divides b (written as a | b) if there exists an integer k such that b = ak.

Read as: “a divides b” or “a is a divisor of b” or “b is divisible by a” or “b is a multiple of a”

Examples

Example 1: Does 3 divide 12?

• 12 = 3 × 4
• Yes, 3 | 12 ✓

Example 2: Does 5 divide 17?

• 17 = 5 × 3 + 2 (remainder 2)
• No, 5 ∤ 17 ✗

Example 3: Does -4 divide 20?

• 20 = -4 × (-5)
• Yes, -4 | 20 ✓

Example 4: Special cases

• 1 | n for all integers n (1 divides everything)
• n | 0 for all n ≠ 0 (everything divides 0 because 0 = n × 0)
• n | n for all n ≠ 0 (every number divides itself)

Properties of Divisibility

1. Transitivity: If a | b and b | c, then a | c

   • Example: 2 | 6 and 6 | 18, so 2 | 18 ✓

2. Linear Combination: If a | b and a | c, then a | (mb + nc) for any integers m, n

   • Example: 3 | 6 and 3 | 9, so 3 | (2×6 + 5×9) = 3 | 57 ✓

3. Divisor of Product: If a | b, then a | bc for any integer c

   • Example: 4 | 12, so 4 | (12 × 5) = 4 | 60 ✓

4. Reflexive: n | n for all n ≠ 0

5. Antisymmetric: If a | b and b | a, then a = ±b

Division Algorithm

Theorem (Division Algorithm)

For any integers a and b with b > 0, there exist unique integers q (quotient) and r (remainder) such that:

a = bq + r where 0 ≤ r < b

Understanding the Components

• a = dividend (number being divided)
• b = divisor (number we’re dividing by)
• q = quotient (result of division)
• r = remainder (what’s left over)

Examples

Example 1: Divide 17 by 5

• 17 = 5 × 3 + 2
• a = 17, b = 5, q = 3, r = 2
• Check: 5 × 3 + 2 = 15 + 2 = 17 ✓
• Check: 0 ≤ 2 < 5 ✓

Example 2: Divide 50 by 7

• 50 = 7 × 7 + 1
• a = 50, b = 7, q = 7, r = 1

Example 3: Divide 24 by 6

• 24 = 6 × 4 + 0
• a = 24, b = 6, q = 4, r = 0
• Note: r = 0 means 6 | 24 (divides evenly)

Example 4: Negative dividend: -17 by 5

• -17 = 5 × (-4) + 3
• Note: remainder must be non-negative (0 ≤ r < 5)
• NOT: -17 = 5 × (-3) + (-2) ✗ (remainder must be ≥ 0)

Example 5: Divide 100 by 13

• 100 = 13 × 7 + 9
• a = 100, b = 13, q = 7, r = 9

Absolute Value

Definition

The absolute value of an integer n, written as |n|, is the distance from n to 0 on the number line.

Formula:

|n| = { n,   if n ≥ 0
      {-n,  if n < 0

Examples

• |5| = 5
• |-7| = 7
• |0| = 0
• |100| = 100
• |-100| = 100

Properties

1. |n| ≥ 0 for all n (always non-negative)
2. |n| = 0 if and only if n = 0
3. |-n| = |n|
4. |mn| = |m| × |n|
5. |m + n| ≤ |m| + |n| (Triangle Inequality)

Well-Ordering Principle

Principle

Every non-empty set of non-negative integers has a smallest element.

Example 1

Set S = {5, 2, 8, 1, 9}

• Smallest element: 1

Example 2

Set T = {n ∈ ℕ : n² > 10}

• T = {4, 5, 6, 7, …}
• Smallest element: 4 (since 4² = 16 > 10)

Why It’s Important

This principle is used to prove many theorems in number theory, especially using mathematical induction.

Factorization

Definition

A factorization of a positive integer n is an expression of n as a product of positive integers greater than 1.

Examples

Example 1: 12

• 12 = 2 × 6
• 12 = 3 × 4
• 12 = 2 × 2 × 3

Example 2: 30

• 30 = 2 × 15
• 30 = 3 × 10
• 30 = 5 × 6
• 30 = 2 × 3 × 5

Example 3: 7

• 7 = 7 (no other factorization)
• 7 is prime

Basic Number Representations

Standard Form

A number written in decimal notation.

• Example: 347

Expanded Form

Expressing a number as a sum of place values.

• Example: 347 = 3×100 + 4×10 + 7×1 = 3×10² + 4×10¹ + 7×10⁰

Prime Factorization Form

Expressing a number as a product of prime powers.

• Example: 360 = 2³ × 3² × 5

Floor and Ceiling Functions

Floor Function ⌊x⌋

The floor of x is the largest integer less than or equal to x.

Examples:

• ⌊3.7⌋ = 3
• ⌊5.0⌋ = 5
• ⌊-2.3⌋ = -3 (NOT -2!)
• ⌊π⌋ = ⌊3.14159…⌋ = 3

Ceiling Function ⌈x⌉

The ceiling of x is the smallest integer greater than or equal to x.

Examples:

• ⌈3.7⌉ = 4
• ⌈5.0⌉ = 5
• ⌈-2.3⌉ = -2 (NOT -3!)
• ⌈π⌉ = ⌈3.14159…⌉ = 4

Properties

1. ⌊n⌋ = n if n is an integer
2. ⌈n⌉ = n if n is an integer
3. ⌊x⌋ ≤ x < ⌊x⌋ + 1
4. ⌈x⌉ - 1 < x ≤ ⌈x⌉
5. ⌊-x⌋ = -⌈x⌉

Applications of Number Theory

1. Cryptography

Number theory is fundamental to modern encryption systems (RSA, etc.).

2. Computer Science

Hashing, random number generation, algorithm analysis.

3. Coding Theory

Error detection and correction codes.

4. Digital Signal Processing

Fast Fourier Transforms use number-theoretic properties.

5. Everyday Life

• Calendar calculations
• ISBN and credit card check digits
• Barcode systems

Key Terminology Summary

Key Points for Exams

1. Know the definition of divisibility - can express as b = ak
2. Division algorithm: a = bq + r where 0 ≤ r < b
3. Remainder is always non-negative even for negative dividends
4. Zero is even (0 = 2 × 0)
5. 1 divides every integer
6. Every integer divides 0
7. Floor of negative numbers goes down: ⌊-2.3⌋ = -3
8. Transitivity of divisibility is very useful in proofs
9. Understand difference between divisor, quotient, and remainder
10. Properties of even/odd for addition and multiplication

Practice Problems

1. Prove that if a | b and b | c, then a | c.

2. Find q and r when:

   • a = 100, b = 7
   • a = -23, b = 5
   • a = 0, b = 4

3. Prove that the product of two consecutive integers is even.

4. True or False:

   • If a | b and a | c, then a | (b + c)
   • If a | bc, then a | b or a | c

5. Calculate:

   • ⌊7.9⌋
   • ⌈7.1⌉
   • ⌊-4.2⌋
   • ⌈-4.2⌉

6. Prove that if n is odd, then n² is odd.

7. Show that 3 | (n³ - n) for all integers n.

8. Find all divisors of 36.