What are the problems on numbers?

Number theory is one of the most appealing topics in mathematics. Given one or more numeric values, a numeric algorithm performs some computation. The use of number theory in computing is important for applications like in the case of cryptographic algorithms. Number theory is also used in various applications such as calculating hash functions or in information security. Euclid’s algorithm is one of the oldest number-theoretic algorithms which is used to calculate the greatest common divisor of two numbers.

Prime number

An integer u > 1 whose only divisors are the numbers 1 and u is called a prime number (or, more simply, a prime). Primes have various important and useful features and they play an important role in number theory. The first few prime numbers are 2, 3, 5, 7, and 11.

Composite number

An integer u > 1 whose divisor is at least a single number less than u, apart from the numbers 1 and u, is called a composite number (or, more simply, a composite). The first few composite numbers are 4, 6, 8, and 9.

Relatively prime

We say that two integers u and v are relatively prime to each other or u is prime to v if gcd of u and v is 1. They are also known as co-primes. The examples of co-primes are 5 and 4, 13 and 11, and so on.

Divisibility

Integer ‘q’ is said to divide an integer ‘w’ if there exists an integer ‘e’ such that w = q * e. The operation of division is denoted in mathematics as “q / w”. The value “q” is called the dividend and the number “w” is called the divisor. The number ‘e’ is called the factor of the dividend “q” if it completely divides it. The number that completely divides a number is called its factor. If the divisor completely divides a number it will also be called the factor of the number. By, completely it means there is no remainder left or the remainder is 0. The remainder is the number that is left when dividing two numbers. 

Notice that every integer which is greater than one has at least two positive factors, 1 and the number itself.

Fermat’s Little theorem

Fermat’s little theorem asserts that when q is a prime number, then for any integer t that is not completely divided by q or for which q is not a factor, the value, 

Let s = t^(q-1)

which implies,

s ≡ 1 (mod q), and hence s is congruent to 1, or simply q divides s with a remainder of 1. 

Elaborating with an example, Let q=3, this means that for any integer t that is not divisible by q, the Fermat's little theorem holds,

Let t=2, 2^(3-1) = 2² = 4,

Now, 4 ≡ 1 (mod 3), because when 4 is divided by 3 it gives a remainder of 1.

Fermat's little theorem is used in computation systems for the creation of new cryptographic algorithms, it is also used in computer security.

Chinese remainder theorem

Suppose that we want a system of linear congruences to their different moduli, then the Chinese theorem is used. It states that, given a set of different congruent equations with one variable but different moduli which are co-primes then,

q ≡ t mod u

q ≡ e mod i,

q ≡ o mod r, and so on

When each pair of moduli is relatively prime. Then there is a unique solution.

For example, 

Q ≡ 6 (mod 11),

Q ≡ 13 (mod 16),

Q ≡ 9 (mod 21),

Q ≡ 19 (mod 25).

As 11, 16, 21, and 25 are pairwise relatively prime, the Chinese Remainder Theorem tells us that there is a unique solution,

Modulo s, where

S = 11⋅16⋅21⋅25 = 92400.

Euclidean's algorithm

Before explaining the algorithm, it is important to know what GCD is, so, the greatest common divisor (GCD) of two or more numbers is the largest integer that divides the numbers evenly and completely. It is also denoted as the highest common factor (HCF). For example, the greatest common divisor of 12 and 6 is 3, as 12 and 6 are completely divisible by 3.

Euclid’s algorithm is used to find the greatest common divisor of two positive integers. Consider a and b are two positive integers, the algorithm is mentioned below.

EUCLID (c, d)

if d = 0

then return c

else return EUCLID(d, c mod d)

Example

Find GCD of 30 and 21

EUCLID(30, 21) = EUCLID(21, 9) = EUCLID(9, 3) = EUCLID(3, 0) = 3

Drawbacks of Euclid's algorithm

• We are unable to solve linear Diophantine equations using the formula.
• Finding prime decompositions for larger integers is highly difficult (and time-consuming).

Modular arithmetic algorithm

The area of arithmetic mathematics known as modular arithmetic is concerned with the “mod” functionality. Modular arithmetic is primarily concerned with the computation of “mod” of expressions. Expressions can contain digits as well as addition, subtraction, multiplication, division, and other computational symbols. All modular arithmetic procedures will be briefly discussed here.

Modular arithmetic is an integer-based arithmetic method that takes the remainder into account. If two integers a and b have the same remainder when divided by N, they are said to be congruent (or in the same equivalence class).

a≡b(mod N)

Quotient Remainder Theorem:

It states that, for any pair of integers w and e (e is positive), there exist two unique integers t and y such that:

w = e * t + y

where 0 <= y < e

For example:

when  w = 14, e = 3

then t = 4, y = 2 such that 14 = 3 * 4 + 2

Modular Addition:

The modular addition is as follows:

(w + i) mod r = ((w mod r) + (i mod r)) mod r

For example:

(4 + 3) % 5

= ((4 % 5) + (3 % 5)) % 5

= (4 + 3) % 5

= 7 % 5

= 2

Modular Multiplication:

The modular multiplication is as follows:

(w x r) mod y = ((w mod y) x (r mod y)) mod y

Example:

(3 x 2) % 4

= ((3 % 4) x (2 % 4)) % 4

= (4 x 4) % 4

= 16 % 4

= 0

Applications of problems on numbers

Computer organization and security, coding and cryptography, random number generation, hash functions, and graphics are all applications of number theory. Number theorists, on the other hand, use computers to factor big integers, find primes, test hypotheses, and solve other difficulties. Because of the invention of cryptographic schemes based on large prime numbers, number-theoretic algorithms are now widely used.

Context and Applications

This topic is important for postgraduate and undergraduate courses, particularly for, 

• Bachelors in Computer Science Engineering.
• Associate of Science in Computer Science.

Practice Problems

Question 1: Find the GCD of 57 and 38.

1. 23
2. 38
3. 57
4. 19

Answer: 4. 19

Explanation: GCD(57, 38) = GCD(38, 19) = GCD(19, 0) = 19

Question 2: What is the value of (5 + 7)mod 7?

1. 7
2. 5
3. 2
4. None of these

Answer: Option (2) is correct.

Explanation: (5 + 7)mod 7 = 12 mod 7 = 5

Question 3: Find the gcd of 1547 ad 560 using the Euclidean algorithm.

1. 1547
2. 560
3. 1
4. 7

Answer: 4. 7

Explanation:

1547 = 2 * 560 + 427

560 = 1 * 427 + 133

427 = 3 * 133 + 28

133 = 4 * 28 + 21

28 = 1 * 21 + 7

21 = 3 * 7 + 0

Therefore, gcd(1547, 560) = 7.

Question 4: Express 7 as a linear combination of 1547 and 560.

1. 7=21 * 1547 - 58 * 560
2. 7=58 * 1547 - 21 * 560
3. 7=21 * 1547 - 21 * 560
4. 7=58 * 1547 - 58 * 560

Answer: 1. 7=21 * 1547 - 58 * 560

Question 5: What is the value of (132 * 7) mod 8

1. 924
2. 4
3. 8
4. 7

Answer: Option (2) is correct.

Explanation: (132 * 7) mod 8 = 924 mod 8 = 4