## Number-Theory

`AlgorithmsCollection.chinese_remainder_theorem`

— Function`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/Chinese*remainder*theorem

**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_totient`

— Function`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%27s*totient*function

**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_exponentiation`

— Function`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_inverse`

— Function`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_eratosthenes`

— Function`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:

- Create a list of sequential integers from 2 to n.
- Define initially
`p=2`

as the first prime number. - Reconstruct all multiple combinations from
`p=2`

. - 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.
```

For more information see: https://en.wikipedia.org/wiki/Sieve*of*Eratosthenes

**Arguments**

`n::Int64`

: Number of elements

**Examples**

```
julia> import ClassicAlgorithmsCollections
julia> ClassicAlgorithmsCollections.sieve_of_eratosthenes(50)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
```