Number Theory

Definition

Number Theory is the study of integers and their properties, especially divisibility, prime factorization, congruences, and arithmetic relationships among numbers.

In simpler words, it examines how whole numbers behave, how they can be broken into factors, how they interact under division, and how they follow patterns in remainders and modular systems.

Examples:

• $12$ is divisible by $3$ because $12 \div 3 = 4$ exactly.
• $17$ is a prime number because it has only two positive factors: $1$ and $17$.
• $29 \equiv 5 \pmod{12}$ means that when 29 is divided by 12, the remainder is 5.

Main Content

1. Divisibility, Factors, and Multiples

Divisibility

• means one integer can be divided by another with no remainder. If $a$ divides $b$, we write $a \mid b$. For example, $4 \mid 20$ because $20 = 4 \times 5$, but $4 \nmid 18$ because 18 leaves a remainder when divided by 4.

Factors

• are numbers that divide a given number exactly, and multiples are numbers obtained by multiplying a number by integers. For example, the factors of 18 are $1, 2, 3, 6, 9, 18$, while its multiples are $18, 36, 54, 72,\dots$

Divisibility rules help quickly determine whether a number is divisible by another number:

• A number is divisible by 2 if its last digit is even.
• A number is divisible by 3 if the sum of its digits is divisible by 3.
• A number is divisible by 5 if it ends in 0 or 5.
• A number is divisible by 9 if the sum of its digits is divisible by 9.

Example:

• Check whether 372 is divisible by 3:
• $3 + 7 + 2 = 12$
• Since 12 is divisible by 3, 372 is also divisible by 3.

This concept is foundational because many later ideas in Number Theory depend on understanding how integers divide one another.

2. Prime Numbers and Composite Numbers

• A prime number is a positive integer greater than 1 that has exactly two positive divisors: 1 and itself. Examples include 2, 3, 5, 7, 11, 13, 17, and 19.
• A composite number is a positive integer greater than 1 that has more than two positive divisors. Examples include 4, 6, 8, 9, 10, 12, and 15.

The number 1 is neither prime nor composite because it has only one positive factor. The number 2 is the only even prime number, since every other even number is divisible by 2 and therefore composite.

Prime numbers are extremely important because every positive integer greater than 1 can be written uniquely as a product of primes. This is called prime factorization or the Fundamental Theorem of Arithmetic.

Example:

• $60 = 2 \times 2 \times 3 \times 5 = 2^2 \times 3 \times 5$
• This factorization into primes is unique except for the order of factors.

A useful visual idea:

60
├── 2
├── 2
├── 3
└── 5

Primes act like the “building blocks” of integers, which makes them central to all of Number Theory.

3. Congruences and Modular Arithmetic

Congruence

• describes numbers that leave the same remainder when divided by a given number. We write $a \equiv b \pmod{n}$, meaning $a$ and $b$ are congruent modulo $n$.

Modular arithmetic

• is arithmetic based on remainders. It is often called “clock arithmetic” because numbers wrap around after reaching a fixed modulus.

Example:

• $17 \equiv 5 \pmod{12}$, because both 17 and 5 leave remainder 5 when divided by 12.
• $29 \equiv 1 \pmod{7}$, because 29 divided by 7 leaves remainder 1.

In modular arithmetic:

• Addition: $(a+b) \bmod n$
• Subtraction: $(a-b) \bmod n$
• Multiplication: $(a \times b) \bmod n$

Example:

• $(8 + 9) \bmod 10 = 17 \bmod 10 = 7$
• $(6 \times 7) \bmod 5 = 42 \bmod 5 = 2$

Clock example:

• On a 12-hour clock, after 12 comes 1 again.
• This is why time calculations naturally use modulo 12.

Congruences are essential in solving divisibility problems, encryption systems, calendars, and many algebraic structures.

Working / Process

1. Identify the number-theoretic property

• Determine whether the problem is asking about divisibility, prime factorization, remainders, gcd, or modular arithmetic.
• Example: If asked whether a number is prime, first check whether it has factors other than 1 and itself.

2. Apply the appropriate rule or method

• Use divisibility rules for quick checks.
• Use prime factorization for breaking numbers into basic building blocks.
• Use modular reduction when dealing with remainders.
• Example: To find $83 \bmod 7$, divide 83 by 7 and keep the remainder. Since $83 = 7 \times 11 + 6$, the remainder is 6.

3. Interpret the result in number-theoretic form

• State the answer using correct mathematical language.
• Example: If $24$ is divisible by $6$, then $6 \mid 24$.
• If $35 \equiv 2 \pmod{11}$, then 35 and 2 belong to the same congruence class modulo 11.

Advantages / Applications

Cryptography and cybersecurity

• : Number Theory is the foundation of public-key cryptography, including RSA encryption, which uses large prime numbers and modular arithmetic to secure digital communication.

Computer science and algorithms

• : It helps in hashing, error detection, random number generation, and algorithm design, especially for problems involving large integers and modular computations.

Pure mathematics and problem solving

• : Number-theoretic ideas are widely used in algebra, combinatorics, and mathematical proofs, and they are essential in competitive mathematics and advanced research.

Summary

• Number Theory studies the properties and relationships of integers.
• It focuses on divisibility, primes, and modular patterns.
• It is useful in mathematics, computing, and cryptography.

Important terms to remember

• integer, divisor, factor, multiple, prime number, composite number, congruence, modulo.