---
title: "Modular Arithmetic"
canonical: "https://docs.magma-maths.org/v2.30-1/BasicRings/Integers/modular.html"
source: "https://docs.magma-maths.org/v2.30-1/BasicRings/Integers/modular.md"
part: "Basic Rings"
chapter: "Ring of Integers"
breadcrumbs:
  - {"title": "Magma Handbook", "source": "https://docs.magma-maths.org/v2.30-1/index.md"}
  - {"title": "Basic Rings", "source": "https://docs.magma-maths.org/v2.30-1/BasicRings/index-basic-rings.md"}
  - {"title": "Ring of Integers", "source": "https://docs.magma-maths.org/v2.30-1/BasicRings/Integers/index-integers.md"}
prev: {"title": "Factorization Sequences", "source": "https://docs.magma-maths.org/v2.30-1/BasicRings/Integers/factorization-sequence.md"}
next: {"title": "Infinities", "source": "https://docs.magma-maths.org/v2.30-1/BasicRings/Integers/infinity.md"}
intrinsics:
  - {"name": "Modexp", "signature": "Modexp(n, k, m): RngIntElt, RngIntElt, RngIntElt -> RngIntElt"}
  - {"name": "mod", "signature": "n mod m: RngIntElt, RngIntElt -> RngIntElt"}
  - {"name": "Modinv", "signature": "Modinv(n, m): RngIntElt, RngIntElt -> RngIntElt"}
  - {"name": "InverseMod", "signature": "InverseMod(n, m): RngIntElt, RngIntElt -> RngIntElt"}
  - {"name": "Modsqrt", "signature": "Modsqrt(n, m): RngIntElt, RngIntElt -> BoolElt, RngIntElt"}
  - {"name": "Modorder", "signature": "Modorder(n, m): RngIntElt, RngIntElt -> RngIntElt"}
  - {"name": "IsPrimitive", "signature": "IsPrimitive(n, m): RngIntElt, RngIntElt -> BoolElt"}
  - {"name": "PrimitiveRoot", "signature": "PrimitiveRoot(m): RngIntElt -> RngIntElt"}
  - {"name": "Solution", "signature": "Solution(a, b, m): RngIntElt, RngIntElt, RngIntElt -> RngIntElt, RngIntElt"}
  - {"name": "ChineseRemainderTheorem", "signature": "ChineseRemainderTheorem(X, N): [RngIntElt], [RngIntElt] -> RngIntElt"}
  - {"name": "CRT", "signature": "CRT(X, N): [RngIntElt], [RngIntElt] -> RngIntElt"}
  - {"name": "Solution", "signature": "Solution(A, B, N): [RngIntElt], [RngIntElt], [RngIntElt] -> RngIntElt"}
  - {"name": "NormEquation", "signature": "NormEquation(d, m): RngIntElt, RngIntElt -> BoolElt, RngIntElt, RngIntElt"}
  - {"name": "NormEquation", "signature": "NormEquation(d, m: parameters)): RngIntElt, RngIntElt -> BoolElt, RngIntElt, RngIntElt"}
examples:
  - "ex-a39523"
---

# 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

<a id="function-modexp-rngintelt-rngintelt-rngintelt"></a>
### `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$.

<a id="operation-operation-mod-rngintelt-rngintelt-rngintelt"></a>
### `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.

<a id="function-modinv-rngintelt-rngintelt"></a>
### `Modinv(n, m): RngIntElt, RngIntElt -> RngIntElt`

<a id="function-inversemod-rngintelt-rngintelt"></a>
### `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$.

<a id="function-modsqrt-rngintelt-rngintelt"></a>
### `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.

<a id="function-modorder-rngintelt-rngintelt"></a>
### `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$.

<a id="function-isprimitive-rngintelt-rngintelt"></a>
### `IsPrimitive(n, m): RngIntElt, RngIntElt -> BoolElt`

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

<a id="function-primitiveroot-rngintelt"></a>
### `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.

<a id="equation"></a>
<a id="rngint-normeq"></a>
## 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](https://docs.magma-maths.org/v2.30-1/BasicRings/ResidueClassRings/residue-class-rings.md#rngint-rngintres) for details.

<a id="function-solution-rngintelt-rngintelt-rngintelt"></a>
### `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.

<a id="function-chineseremaindertheorem-rngintelt-rngintelt"></a>
### `ChineseRemainderTheorem(X, N): [RngIntElt], [RngIntElt] -> RngIntElt`

<a id="function-crt-rngintelt-rngintelt"></a>
### `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.

<a id="function-solution-rngintelt-rngintelt-rngintelt-2"></a>
### `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.

<a id="function-normequation-rngintelt-rngintelt"></a>
### `NormEquation(d, m): RngIntElt, RngIntElt -> BoolElt, RngIntElt, RngIntElt`

<a id="function-normequation-rngintelt-rngintelt-2"></a>
### `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.

<a id="example-ex-a39523"></a>
### `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
```
