# Modular Arithmetic

In this section we describe some functions that make it possible to perform modular arithmetic without conversions to residue class rings.

## Arithmetic Operations

### `Modexp(n, k, m): RngIntElt, RngIntElt, RngIntElt -> RngIntElt`

The modular power $n^k\bmod m$, where $n$ is an integer, $k$ is an integer and $m$ is an integer greater than one. If $k$ is negative, $n$ must have an inverse $i$ modulo $m$, and the result is then $i^{-k}\bmod m$. The result is always an integer $r$ with $0\leq r< m$.

### `n mod m: RngIntElt, RngIntElt -> RngIntElt`

Remainder upon dividing the integer $n$ by the integer $m$. The result always has the same sign as $m$. An error results if $m$ is zero.

### `Modinv(n, m): RngIntElt, RngIntElt -> RngIntElt`

### `InverseMod(n, m): RngIntElt, RngIntElt -> RngIntElt`

Given an integer $n$ and a positive integer $m$, such that $n$ and $m$ are coprime, return an inverse $u$ of $n$ modulo $m$, that is, return an integer $1\leq u<m$ such that $u\cdot n\equiv 1\bmod m$.

### `Modsqrt(n, m): RngIntElt, RngIntElt -> BoolElt, RngIntElt`

Given an integer $n$ and an integer $m \geq 2$, this function returns an integer $b$ such that $0 \leq b < m$ and $b^2\equiv n\bmod m$ if such $b$ exists; an error results if no such root exists.

### `Modorder(n, m): RngIntElt, RngIntElt -> RngIntElt`

For integers $n$ and $m$, $m > 1$, the function returns the least integer $k \geq 1$ such that $n^k \equiv 1 \bmod m$, or zero if $\gcd(n, m) \neq 1$.

### `IsPrimitive(n, m): RngIntElt, RngIntElt -> BoolElt`

Returns `true` if $n$ is a primitive root for $m$, `false` otherwise ($0 < n < m$).

### `PrimitiveRoot(m): RngIntElt -> RngIntElt`

Given an integer $m > 1$, this function returns an integer value defined as follows: If ${\mathbb{Z}}/m{\mathbb{Z}}$ has a primitive root and the function is successful in finding it, the root $a$ is returned. If ${\mathbb{Z}}/m{\mathbb{Z}}$ has a primitive root but the algorithm does not succeed in finding it, or ${\mathbb{Z}}/m{\mathbb{Z}}$ does not possess a primitive root, then zero is returned.

## The Solution of Modular Equations

The functions described here can be used if an occasional modular operation is required; the results are integers again. For more extensive modular arithmetic it is preferable to convert to residue class ring arithmetic. See section [Residue Class Rings](../ResidueClassRings/residue-class-rings.md#rngint-rngintres) for details.

### `Solution(a, b, m): RngIntElt, RngIntElt, RngIntElt -> RngIntElt, RngIntElt`

If a solution exists to the linear congruence $ax\equiv b \bmod m$, then returns $x0, k$ such that $x = x0 + i*k$ represents the complete set of solutions, where i can be any integer. Otherwise, returns -1.

### `ChineseRemainderTheorem(X, N): [RngIntElt], [RngIntElt] -> RngIntElt`

### `CRT(X, N): [RngIntElt], [RngIntElt] -> RngIntElt`

Apply the Chinese Remainder Theorem to the integer sequences $X$ and $N$. The sequences must have the same length, $k$ say. The function returns the unique integer $x$ in the range $0 \leq x < LCM(N[1]\cdot\ldots\cdot N[k])$ such that $x \equiv X[i] \bmod N[i]$. The elements of $N$ must all be positive integers greater than one. If there is no solution, then -1 is returned.

### `Solution(A, B, N): [RngIntElt], [RngIntElt], [RngIntElt] -> RngIntElt`

Return a solution $x$ to the system of simultaneous linear congruences defined by the integer sequences $A$, $B$ and $N$. Each of these sequences must have the same number of terms, $k$ say. The elements of $N$ must all be positive integers greater than one. The $i$-th congruence is $A[i] \cdot x \equiv B[i] \bmod N[i]$. The solution $x$ will satisfy $0 \leq x < LCM(N[1]\cdot\ldots\cdot N[k])$. If no solution exists, -1 is returned.

### `NormEquation(d, m): RngIntElt, RngIntElt -> BoolElt, RngIntElt, RngIntElt`

### `NormEquation(d, m: parameters)): RngIntElt, RngIntElt -> BoolElt, RngIntElt, RngIntElt`

```magma
Factorization: [<RngIntElt, RngIntElt>]                    Default: [ ]
```

Given a positive integer $d$ and a non-negative integer $m$, return `true` and two non-negative integers $x$ and $y$, such that $x^2+y^2d = m$, if such a solution exists. If such a solution does not exists only the value `false` is returned. If the factorization of $m$ is known, it may be supplied as the value of the parameter `Factorization` to speed up the computation.

### `Example: Norm Equation (ex-a39523)`

```magma
> d := 957440000095744000002277749760;
> m := 5102197760510219776012138128480644;
> time NormEquation(d, m);
true 98 73
Time: 2.990
> time f := Factorization(m);
Time: 4.670
> f;
[ <2, 2>, <19, 1>, <67134181059344997052791291164219, 1> ]
> time NormEquation(d, m: Factorization := f);
true 98 73
Time: 0.420

```