Basic Concepts in Elementary Number Theory

1. Basic Concepts in Number Theory

a) Integers:

• The set of integers ($\mathbb{Z}$) includes positive and negative whole numbers as well as zero: $$\mathbb{Z} = \{ \ldots, -3, -2, -1, 0, 1, 2, 3, \dots \}$$

b) Divisibility:

• An integer $a$ divides another integer $b$ (denoted as $a \mid b$) if there exists an integer $k$ such that $b = ak$
• 
  
 For example, $3 \mid 9$ because $9 = 3 \times 3$

c) Prime Numbers:

• A prime number is a natural number greater than 1 that has no divisors other than 1 and itself. For example, $2, 3, 5, 7, 11, 13$ are prime numbers.

d) Greatest Common Divisor (GCD):

• The GCD of two integers $a$ and $b$ is the largest number that divides both $a$ and $b$.
•  For example, $\text{gcd}(12,8)=4$

e) Least Common Multiple (LCM):

• The least common multiple of two integers $a$ and $b$ is the smallest positive integer divisible by both. For example, $\text{lcm}(12, 8) = 24$.

---

2. Prime Numbers and Factorization

a) Fundamental Theorem of Arithmetic:

• Every integer greater than 1 can be factored uniquely into a product of prime numbers. This is the basis of prime factorization. For example: $$60 = 2^2 \times 3 \times 5$$
  

b) Sieve of Eratosthenes:

• A method to find all prime numbers less than a given $n$. By eliminating multiples of each prime starting from 2, we identify the primes in a range.

---

3. Modular Arithmetic

a) Concept:

• Modular arithmetic involves numbers wrapping around after reaching a certain value, called the modulus. For example, $12 \equiv 0 \ (\text{mod} \ 12)$ since 12 leaves a remainder of 0 when divided by 12.

b) Basic Properties:

• Modular arithmetic obeys the basic rules of addition, subtraction, and multiplication. For example: $$(7 + 9) \mod 5 = 16 \mod 5 = 1$$

4. Linear Congruences

a) Definition:

• A linear congruence takes the form $ax \equiv b \ (\text{mod} \ n)$where $a, b,$ and $n$ are integers. Solving for $x$ involves finding values of $x$ that satisfy the equation within the modular system.

b) Solving Linear Congruences:

• Solving these equations often requires using the Euclidean algorithm to find the multiplicative inverse of $a$ modulo $n$.

---

5. Diophantine Equations

a) Definition:

• Diophantine equations are polynomial equations where integer solutions are sought. For example: $$ax + by = c$$ where $a, b, c$ are integers and $x, y$ are unknowns.

b) Solutions:

• A solution to this equation exists if and only if $\text{gcd}(a, b)$ divides $c$.

---

6. Theorems in Number Theory

a) Fermat's Little Theorem:

• If $p$ is a prime and $a$ is not divisible by $p$, then: $$a^{p-1}\equiv 1(\text{mod }p)$$
•  This theorem has applications in cryptography and computational mathematics.

b) Euler’s Theorem:

• For any integer $a$ coprime to $n$: $$a^{\phi(n)} \equiv 1 \ (\text{mod} \ n)$$where $\phi(n)$ is Euler’s totient function, counting the integers up to $n$ that are coprime to $n$.

---

7. Cryptography and Number Theory

a) RSA Encryption:

• RSA encryption is a public-key cryptographic system based on the difficulty of factoring large integers. It relies on modular arithmetic and the properties of prime numbers.

b) Diffie-Hellman Key Exchange:

• This method uses modular exponentiation to enable two parties to securely exchange cryptographic keys.

---

8. Applications of Elementary Number Theory

a) Cryptography:

• Elementary number theory is central to encryption methods, such as RSA, which secure online communications.

b) Computer Algorithms:

• Many algorithms, like those for primality testing, are rooted in number theory. Modular arithmetic is also essential for hash functions in computer science.

c) Pure Mathematics:

• Number theory provides tools for exploring deep mathematical problems, including unsolved questions like the Goldbach conjecture or the Riemann hypothesis.

Some Examples

1. Divisibility and Prime Numbers

Example 1: Divisibility

• Determine whether $18 \mid 54$ (i.e., check if 18 divides 54).
  • Solution: $54 \div 18 = 3$ which is an integer. Therefore, $18 \mid 54$.

Example 2: Prime Numbers

• Check if 29 is a prime number.
  • Solution: To verify, we check divisibility by all prime numbers less than $\sqrt{29}$ (i.e., 2, 3, 5). Since 29 is not divisible by any of them, 29 is prime.

---

2. Greatest Common Divisor (GCD)

Example 3: Using Euclidean Algorithm

• Find the GCD of 56 and 98 using the Euclidean algorithm.
  • Solution: Apply the division algorithm: $$98 = 1 \times 56 + 42$$$$56 = 1 \times 42 + 14$$$$42 = 3 \times 14 + 0$$ Since the remainder is 0, the GCD is the last non-zero remainder, $\text{gcd}(56, 98) = 14$.

---

3. Modular Arithmetic

Example 4: Modular Addition

• Compute $(7+10)\mathrm{m}\mathrm{o}\mathrm{d}6$
  • Solution: First, add the numbers: $7 + 10 = 17$ Now, divide by 6 and take the remainder: $$17 \div 6 = 2 \text{ remainder } 5$$Therefore, $17 \equiv 5 \ (\text{mod} \ 6)$.

Example 5: Modular Multiplication

• Compute $(5\times 9)\mathrm{m}\mathrm{o}\mathrm{d}7.$
  • Solution: First, multiply the numbers: $5 \times 9 = 45$ Now, divide by 7 and take the remainder: $$45 \div 7 = 6 \text{ remainder } 3$$Therefore, $45 \equiv 3 \ (\text{mod} \ 7)$
    

---

4. Linear Diophantine Equation

Example 6: Solving a Diophantine Equation

• Solve $15x + 21y = 3$ for integer values of $x$ and $y$.
  • Solution: First, find the GCD of 15 and 21, which is 3 (since $3 \mid 15$ and $3 \mid 21$).
  • Divide the equation by 3: $$5x + 7y = 1$$ Using the extended Euclidean algorithm, we solve for $x$ and $y$: $$7 = 1 \times 5 + 2$$$$5 = 2 \times 2 + 1$$Working backwards: $$1 = 5 - 2 \times 2 = 5 - 2 \times (7 - 1 \times 5) = 3 \times 5 - 2 \times 7$$ Thus, $x=3$$y = -2$ is a particular solution to the equation.

---

5. Fermat's Little Theorem

Example 7: Using Fermat’s Little Theorem

• Find $2^{100} \mod 13$.
  • Solution: Fermat's Little Theorem states that for a prime $p$, if $a$ is not divisible by $p$ then: $$a^{p-1} \equiv 1 \ (\text{mod} \ p)$$ Here, $p = 13$ and $a=\mathrm{2\; so:}$$$2^{12} \equiv 1 \ (\text{mod} \ 13)$$Now, write $100=8\times 12+\mathrm{4\; so:}$$$2^{100} = (2^{12})^8 \times 2^4 \equiv 1^8 \times 2^4 \ (\text{mod} \ 13)$$ Compute $2^4 = 16$ and $16\mathrm{m}\mathrm{o}\mathrm{d}13=\mathrm{3\; Therefore:}$$$2^{100} \equiv 3 \ (\text{mod} \ 13)$$

These examples illustrate key concepts of divisibility, modular arithmetic, GCD, Diophantine equations, and theorems like Fermat’s Little Theorem.