What is number theory?

Number theory is a branch in mathematics that deals with the study of integers and integer-valued functions. It involves studies related to prime numbers and properties of mathematical concepts such as rational numbers.

Importance of number theory in computer algorithms

Number theory is used in various computer applications for coding, random number generation, cryptography, and graphics. Questions on number theoretic concepts are also asked in competitive programming interviews and quizzes. So, programmers need to know the basic concepts of number theory.

Number theory algorithms

Number theory algorithm is a category in data structure and algorithms that involve studies related to algorithms in number theory. Such algorithms are used to conduct tests such as primality testing. A primality test is an algorithm that verifies whether a number is a prime or not.

Examples of number theory algorithms are as follows:

GCD and LCM

Greatest common divisor (GCD)

The GCD of a given set of two or more numbers is the largest number that divides all of the numbers.

The GCD of two numbers can be determined using the following method:

• Write the divisors of all the numbers separately.
• List the common divisors of all the numbers.
• Now, check which divisor is the highest in all the numbers.

For example, the GCD of 20 and 28 can be computed as:

Divisors of 20: 1, 2, 4, 5, 10, 20

Divisors of 28: 1, 2, 4, 7, 14, 28

It can be clearly said that the GCD of 20 and 28 is 4.

Least common multiple (LCM)

The LCM of a given set of two or more numbers is the smallest number that can be divided by all the numbers. The LCM of a given set of numbers can be determined using the following method:

• Write the given numbers in the form of prime factors.
• Multiply all the prime factors but remember to include the common factors only once.

For example, the LCM of 60 and 90 can be computed as follows:

Prime factors of 60 and 90:

$60 = 2\times 2 \times 3 \times 5$

$90 = 2 \times 3 \times 3 \times 5$

The product of all prime factors = $2 \times 3 \times 5 \times 2 \times 3 =180$

The LCM will be $2 \times 3 \times 5 \times 2 \times 3 =180$

LCM of Array

It is possible to find the LCM of an array having positive integers. The method to calculate the LCM of an array is as follows:

• Initialize the result as 1.
• Select two or more elements of the array and identify their common factors.
• Multiply the result by the common factor and divide all elements by that common factor.
• Repeat the last two steps until no common factor exists.
• Multiply the rest elements by the current answer.

Consider an array a[] = {1, 2, 3, 4, 28}

Solution:

Step 1: Initialize the ans = 1

Step 2: For the above array, 2 is the common factor in two or more elements. So, by dividing all the multiples by two and multiplying the answer by 2, the array will be:

a[] = {1, 1, 3, 2, 14}

ans = 2

Again, 2 is the common factor for more than two elements. So, by repeating the above process, the array will be:

a[] = { 1, 1, 3, 1, 7}

ans = 4

There is no common factor left in more than two elements of the array. So, multiply the current elements by the result to find the LCM.

ans =$4 \times 1 \times 1 \times 3 \times 1 \times 7 = 84$

The LCM is 84.

Basic and Extended Euclidean algorithms

The basic Euclidean algorithm is a more efficient technique used to find the GCD of two numbers. According to the algorithm, the GCD of two numbers remains the same if the larger number is changed by its difference with the smaller number. Therefore, to find the GCD of two numbers using this method, the smaller number of the two numbers has to be subtracted continuously. Furthermore, if the smaller number is divided by, the larger one, the algorithm will stop when the remainder becomes 0. 

The extended Euclidean algorithm is an extended version of the Euclidean algorithm. It finds the GCD of two integers and coefficients x and y where:

$ax + by = gcd(a,b)$

Prime factorization

Prime factorization is a method used to represent a number as the product of its prime factors. Prime factors are prime numbers which are factors of a number. A prime number is a number having factors 0 and the number itself. In other words, prime factorization finds which prime numbers return the original number when they are multiplied together.

For example, as shown in the figure below, the prime factors of 

$864 = 2 \times 2 \times 2 \times 2 \times 2 \times 3 \times 3 \times 3$

Here, the numbers 2, and 3 are prime numbers.

Fibonacci numbers

A Fibonacci number sequence is a sequence of numbers where each number is the sum of the previous two numbers. The sequence mainly begins from 0 or 1. For example, the following sequence is a Fibonacci sequence:

0, 1, 1, 2, 3, 5, 8, 13, 21, …

Applications of number theory

Number theory algorithms are important topics in data structure and algorithms and they have a wide range of applications in the computer science field. Some of these include:

• Prime numbers are helpful in cryptography.
• The Euclidean algorithm is used to compute modular multiplicative inverse in the RSA-key encryption method in cryptography.
• Number theory algorithms are used in encryption algorithms.
• Number theory algorithms are used for generating random numbers.

Context and Applications

Problems on the number-theoretic algorithm is a concept of data structure and algorithms. The topic is studied by students studying in courses like:

• Bachelor of Science in Computer Science
• Master of Science in Computer Science
• Bachelor of Science in information technology
• Master of Science in information technology
• Bachelor of Science in computer engineering

Practice Problems

Q1) Which type of algorithm is used to identify whether a number is prime or not?

1. Primality testing algorithm
2. Modular-exponentiation notations
3. Algebraic time complexity
4. Square root finder

Answer: Option a

Explanation: A primality test algorithm is used to verify if a number is a prime or not.

Q2) What does LCM stand for?

1. Least Common Multiplier
2. Least Common Multiple
3. Least Common Mathematics
4. Least Common Mean

Answer: Option b

Explanation: LCM is the acronym for Least Common Multiplier.

Q3) Which of the following is an application of number theory algorithms?

1. For generating random numbers
2. For interviews related to programming theory
3. To find the total number of divisors
4. To solve time complexity

Answer: Option a

Explanation: One of the applications of number theory algorithms is that they are used to generate random numbers.

Q4) What is a Fibonacci sequence?

1. It is a cryptography algorithm
2. It is used to find the recursion relations
3. It is a sequence where every number is the sum of the preceding two numbers
4. It is used to solve asymptotic notations

Answer: Option c

Explanation: According to the definition, a Fibonacci sequence is a sequence where each number is the sum of the last two numbers.

Q5) The Euclidean algorithm is used to compute

1. GCD of integers
2. Prime factors
3. Square root
4. Arithmetic problems

Answer: Option a

Explanation: The Euclidean algorithm is used to find the GCD of integers.

Related concepts

• Modular Arithmetic
• Modular Exponentiation
• Pollard’s Rho algorithm
• Sieve of Eratosthenes