Number Theory in Discrete Mathematics

---

---

Number Theory deals with the properties and relationships of numbers, particularly integers. It has applications in cryptography, coding theory, and computer science. It is also known as the "Queen of Mathematics".

It's the Number Theory that is acts as the origin of other important concepts like divisibility, prime numbers, and modular arithmetic that offer insights into the structure and behavior of natural numbers. In this chapter, we will highlight some of the fundamental concepts of Number Theory and explain their role in Discrete Mathematics.

The Basics of Number Theory

Number Theory focuses on the properties of natural numbers—the set of integers used for counting and ordering. In discrete mathematics, natural numbers often solve problems requiring whole number solutions, such as counting or forming combinations.

Traditionally a branch of pure mathematics, Number Theory now has modern applications in fields like cryptography, where prime numbers play a crucial role in securing digital communication.

Properties of Number Theory

In this section, we have explained in brief some of the important properties of Number Theory.

Divisibility

Divisibility means one number is dividing another without a remainder. For an integer a that can be divided by an integer b such that the result is an integer. So b divides a; it can be written as b | a.

• 4 | 20 − True because 20 divided by 4 is 5, it is an integer.
• 20 | 4 − False because 4 does not divide into 20 evenly.

Divisibility is a useful thing in defining multiples, factors, and in identifying prime numbers. These are numbers divisible only by 1 and themselves.

Prime Numbers and Factorization

Prime numbers are natural numbers greater than 1 and that have no divisors other than 1 and themselves. For every integer greater than 1, it can be represented as a product of primes. This is a principle known as the fundamental theorem of arithmetic. For example, the number 28 can be factored as 2² × 7. It illustrates the product of prime factors.

Prime numbers form the backbone of various algorithms in number theory, particularly in encryption.

Modular Arithmetic

Modular arithmetic, sometimes called the "clock arithmetic" is a system of arithmetic for integers, where numbers "wrap around" after reaching a certain value. We call this the modulus.

The Modulo Operation

In modular arithmetic, two numbers are said to be congruent modulo n if they have the same remainder when divided by n.

For example, 17 ≡ 2   (mod   5) because when 17 is divided by 5, and the remainder is 2.

Properties of Congruence

Congruence follows the rules similar to equality, but like transitivity and symmetry, they maintain consistency through addition, subtraction, and multiplication.

For example, if 8 ≡ 3   (mod   5) and 12 ≡ 2   (mod   5), then −

$$\mathrm{8 \:+\: 12 \:\equiv\: 3 \:+\: 2 \: (\text{mod} \: 5) \:\equiv\: 0 \: (\text{mod} \: 5)}$$

The modular arithmetic is much useful in computer science, where it is used in algorithms, cryptography, and hashing functions.

Applications of Number Theory

Number Theory is highly useful in fields like Cryptography and Coding Theory among others.

• Cryptography − Number theory is the base for cryptography. The RSA algorithm, for example, uses properties of prime numbers to create secure keys for encrypting and decrypting messages. The algorithm relies on the difficulty of factoring large numbers, a problem rooted in number theory.
• Coding Theory − The coding theory uses modular arithmetic to create error-detecting and error-correcting codes. These codes are useful in digital communication. It is ensuring that data is accurately transmitted even in the presence of noise.

Solving Diophantine Equations

A Diophantine equation is an equation that needs to find integer solutions. The classic example is ax + by = c. Here the solutions must be integers. These equations appear in problems like determining the minimum number of items in a given combination or solving puzzles where only whole-number solutions make sense.

Example

Consider using Rs.5 and Rs.8 stamps to reach an exact postage amount requires solving a Diophantine equation. It is in the form 5x + 8y = desired amount.

Advanced Topics in Number Theory

Let us now touch upon some advanced topics in Number Theory −

The Division Algorithm

The division algorithm gives the idea for any integers a and b (where b ≠ 0), there exist unique integers q and r such that a = bq + r with 0 ≤ r < |b|. This concept is the basis for division with remainders.

For example, dividing 23 by 5 gives a quotient of 4 and a remainder of 3, so 23 = 5 × 4 + 3

Greatest Common Divisor

The GCD of two integers is the largest integer that divides both without a remainder. The Euclidean algorithm states it computes the GCD. For example, for 28 and 35, the GCD is 7 because 7 is the largest number that divides both.

Modular Exponentiation and Fermat's Little Theorem

The modular exponentiation is used for finding the remainder when a large power is divided by a number. It is used in encryption and computer algorithms.

Fermat's Little Theorem: The Fermat's Little theorem states that if p is a prime number, then for any integer a not divisible by p, a^p−1 ≡ 1  (mod   p). This theorem is used in the RSA algorithm and other cryptographic systems.

Example

For a = 2 and p = 7, 2⁶ ≡ 1   (mod 7)

Remainder Classes and Partitioning

The remainder classes group numbers by their remainder when divided by a particular number. For example, modulo 5 has remainder classes like 0, 1, 2, 3, and 4. This grouping is quite useful for simplifying calculations in number theory.

Conclusion

In this chapter, we explained the concepts of number theory in discrete mathematics, including divisibility, prime numbers, modular arithmetic, applications in cryptography and coding, and the solving of Diophantine equations.

In addition, we covered some of the basic operations like the division algorithm, calculating the GCD, and modular exponentiation. We also touched upon the Fermat's Little Theorem and remainder classes.