## Number-Theory

AlgorithmsCollection.chinese_remainder_theoremFunction
chinese_remainder_theorem(array::Array{Int64}, remainder::Array{Int64}))

The Chinese remainder theorem is based on simultaneous congruence. In more detail, if x knows the remainder of the Euclidean division of an array[i] by several integers, then x can determine the remainder of the division of array[i] by the product of these integers uniquely, following the condition that the divisors are pairwise coprime. For more information see: https://en.wikipedia.org/wiki/Chineseremaindertheorem

Arguments

• array::Array{Int64}: Array with elements.
• remainder::Array{Int64}: Number of elements

Examples

julia> import ClassicAlgorithmsCollections
julia> num = [3, 4, 5]
julia> rem = [2, 3, 1]
julia> ClassicAlgorithmsCollections.chinese_remainder_theorem(num, rem)
11
AlgorithmsCollection.euler_totientFunction
euler_totient(n::Int64)

Compute the positive integers up to a given integer n that are relatively prime to n; also known as Euler's totient. For more information see: https://en.wikipedia.org/wiki/Euler%27stotientfunction

Arguments

• n::Int64: Number of elements

Examples

julia> import ClassicAlgorithmsCollections
julia> ClassicAlgorithmsCollections.euler_totient(20)
[1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8]
AlgorithmsCollection.modular_exponentiationFunction
modular_exponentiation(base::Int64, exponent::Int64, modulus::Int64)

Compute the residuum of the base raised to the exponent, which is divided by the modulus.

Arguments

• base::Int64: base
• exponent::Int64: exponent
• modulus ::Int64: modulus

Examples

julia> import ClassicAlgorithmsCollections
julia> ClassicAlgorithmsCollections.modular_exponentiation(2, 3, 15)
8
AlgorithmsCollection.modular_inverseFunction
modular_inverse(base::Int64, modulus::Int64)

Compute the multiplicative inverse of the base under the modulus.

Arguments

• base::Int64: base
• modulus ::Int64: modulus

Examples

julia> import ClassicAlgorithmsCollections
julia> ClassicAlgorithmsCollections.modular_inverse(3, 11)
4
AlgorithmsCollection.sieve_of_eratosthenesFunction
sieve_of_eratosthenes(n::Int64)

The Sieve of Eratosthenes is one of the historical algorithms dedicated to finding all prime numbers up to any given limit. The algorithm is split into four steps:

1. Create a list of sequential integers from 2 to n.
2. Define initially p=2 as the first prime number.
3. Reconstruct all multiple combinations from p=2.
4. Find the first number greater than p in the array that is not listed. Then decided:
* If no number exists => stop.
* p becomes equal to the number and go back to step 3.

• n::Int64: Number of elements
julia> import ClassicAlgorithmsCollections
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]