Elementary Number Theory

Elementary Number Theory

Elementary number theory is a branch of mathematics focused on the study of integers and their properties. It is one of the oldest and most fundamental areas of mathematics, with applications in cryptography, coding theory, and various other fields.

This subject involves a variety of key topics, including divisibility, prime numbers, congruences, Diophantine equations, and more. Below, we'll explore some of the key concepts of elementary number theory.

---

1. Divisibility

Divisibility is one of the central ideas in number theory and refers to whether one integer can be evenly divided by another.

Definition:

• An integer $a$ is divisible by an integer $b$ (where $b \neq 0$) if there exists an integer $k$ such that: $$a = b \times k$$ In this case, we say that $b$ divides $a$, and we write: $$b \mid a$$
• Example: $12 \mid 36$ because $36 = 12 \times 3$.

Divisibility Rules:

There are simple rules to determine if a number is divisible by small integers like 2, 3, 5, etc. Some examples:

• A number is divisible by 2 if its last digit is even (0, 2, 4, 6, or 8).
• 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.

---

2. Prime Numbers

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

Definition:

• A prime number $p$ is one for which the only divisors are 1 and $p$ itself.
  • Example: $2, 3, 5, 7, 11$ are prime numbers.
• A composite number is a number that is not prime, meaning it has divisors other than 1 and itself.
  • Example: $4, 6, 8, 9$ are composite numbers.

Fundamental Theorem of Arithmetic:

Every integer greater than 1 can be uniquely factored into primes, up to the order of the factors. This is called prime factorization.

• Example: The prime factorization of 36 is $2^2 \times 3^2$.

---

3. Greatest Common Divisor (GCD)

The greatest common divisor of two integers is the largest integer that divides both of them without leaving a remainder.

Definition:

• The GCD of two numbers $a$ and $b$ is the largest integer $d$ such that: $$d \mid a \quad \text{and} \quad d \mid b$$ We write this as $\gcd(a, b) = d$.

Euclidean Algorithm:

This is a method to find the GCD of two numbers by repeatedly applying the division algorithm:

• Step 1: Divide $a$ by $b$ to get the quotient $q$ and remainder $r$. $$a = b \times q + r$$
• Step 2: Replace $a$ with $b$ and $b$ with $r$, and repeat the process until the remainder is 0.
• Step 3: The GCD is the last non-zero remainder.

Example: Find $\gcd(48, 18)$.

• $48 = 18 \times 2 + 12$
• $18 = 12 \times 1 + 6$
• $12 = 6 \times 2 + 0$

Thus, $\gcd(48, 18) = 6$.

---

4. Least Common Multiple (LCM)

The least common multiple of two integers is the smallest number that is a multiple of both.

Definition:

• The LCM of $a$ and $b$ is the smallest positive integer $l$ such that: $$l = \text{LCM}(a, b)$$ and $a \mid l$ and $b \mid l$.

Relationship between GCD and LCM:

There is a useful identity connecting the GCD and LCM of two numbers:

$$\gcd(a, b) \times \text{LCM}(a, b) = |a \times b|$$

This means that you can compute the LCM of two numbers using their GCD:

$$\text{LCM}(a, b) = \frac{|a \times b|}{\gcd(a, b)}$$

Example: Find $\text{LCM}(12, 18)$.

• $\gcd(12, 18) = 6$
• $\text{LCM}(12, 18) = \frac{12 \times 18}{6} = 36$

---

5. Modular Arithmetic

Modular arithmetic deals with integers and their remainders when divided by a fixed number (called the modulus). It is often used in cryptography, computer science, and number theory.

Definition:

• We say $a \equiv b \pmod{n}$ if the difference $a - b$ is divisible by $n$, i.e., $n \mid (a - b)$.
  • Example: $17 \equiv 5 \pmod{12}$ because $17 - 5 = 12$, which is divisible by 12.

Properties of Modular Arithmetic:

• Addition: $(a + b) \pmod{n} = [(a \pmod{n}) + (b \pmod{n})] \pmod{n}$
• Multiplication: $(a \times b) \pmod{n} = [(a \pmod{n}) \times (b \pmod{n})] \pmod{n}$
• Exponentiation: $a^b \pmod{n}$ can be computed efficiently using modular exponentiation.

---

6. Congruences

Congruences are a way of expressing that two numbers leave the same remainder when divided by a modulus.

Definition:

• A congruence $a \equiv b \pmod{n}$ means that $a$ and $b$ have the same remainder when divided by $n$.
• This can be written as: $$a \equiv b \pmod{n} \iff n \mid (a - b)$$

Solving Linear Congruences:

A linear congruence is an equation of the form:

$$ax \equiv b \pmod{n}$$

To solve such congruences, you can use methods like the extended Euclidean algorithm or Chinese remainder theorem.

---

7. Diophantine Equations

A Diophantine equation is an equation that seeks integer solutions. A famous example is the equation of the form:

$$ax + by = c$$

where $a$, $b$, and $c$ are integers, and $x$ and $y$ are the unknown integers.

Solving Diophantine Equations:

• A solution exists for $ax + by = c$ if and only if $\gcd(a, b) \mid c$.
• If this condition is satisfied, the equation can be solved using methods like the Euclidean algorithm.

---

8. Fermat's Little Theorem

Fermat's Little Theorem is a fundamental result in number theory, particularly in the field of cryptography.

Statement:

If $p$ is a prime number and $a$ is an integer not divisible by $p$, then:

$$a^{p-1} \equiv 1 \pmod{p}$$

This is widely used in primality testing and cryptographic algorithms like RSA.

---

Conclusion

Elementary number theory is the study of integers and their properties, including concepts like divisibility, prime numbers, GCD, LCM, modular arithmetic, and Diophantine equations. These concepts form the foundation of more advanced mathematical areas and have practical applications in areas like cryptography, computer science, and coding theory. Understanding the basics of number theory is essential for anyone interested in mathematics, algorithm design, or theoretical computer science.