# Multiplicative Order Calculator mod n (ordₙ(a))

Smallest k with a^k ≡ 1 (mod n) via φ(n) reduction: power table, minimality proof, cyclic subgroup , primitive-root and maximal-order flags.

> Canonical page: https://elysiatools.com/en/tools/order-of-element-mod-n

- **Category:** Math & Numbers

- **Keywords:** multiplicative order, order of element, primitive root, cyclic subgroup, multiplicative group, discrete log, number theory, euler totient

## Overview

The Multiplicative Order Calculator finds the smallest positive integer k such that a^k ≡ 1 (mod n) for any coprime integer a and modulus n. It computes values using Euler's totient function φ(n) and Carmichael's function λ(n), providing a step-by-step modular power table, minimality checks, the generated cyclic subgroup ⟨a⟩, and primitive root identification.

## Inputs

- **Element a** (text): The element whose order is computed; reduced mod n first (up to 10⁵¹²).
- **Modulus n** (text): Modulus, 2 ≤ n ≤ 10¹² (needs factorization of n and φ(n)).

## When to use

- Determining if an integer a is a primitive root modulo n by checking if its order equals φ(n).
- Analyzing cyclic subgroups and subgroup sizes within multiplicative groups (ℤ/nℤ)* for abstract algebra and number theory problems.
- Selecting generator candidates and verifying cycle lengths for modular arithmetic, discrete logarithm protocols, or cryptographic algorithms.

## How it works

- Checks coprimality by evaluating gcd(a, n); if gcd(a, n) = 1, it computes φ(n) and λ(n) using the prime factorization of n.
- Reduces potential order candidates from divisors of φ(n) by iteratively testing prime factors via modular exponentiation.
- Generates the sequence of modular powers a^1, a^2, ..., a^k (mod n) to list the elements in the cyclic subgroup ⟨a⟩.
- Verifies minimality by ensuring a^(k/p) ≢ 1 (mod n) for all prime divisors p of k, then flags whether a achieves maximal order or is a primitive root.

## Use cases

- Verifying generator elements for Diffie-Hellman key exchanges and discrete log constructions.
- Solving number theory assignments involving subgroup orders, order dividing φ(n), and modular exponentiation cycles.
- Determining whether a composite modulus n admits a primitive root by evaluating maximal orders against λ(n).

## Frequently asked questions

### What happens if a and n are not coprime?

The multiplicative order is undefined when gcd(a, n) > 1 because no positive integer power of a can be congruent to 1 modulo n.

### What is the difference between φ(n) and λ(n)?

Euler's totient function φ(n) counts integers coprime to n, while Carmichael's function λ(n) represents the smallest universal exponent such that a^λ(n) ≡ 1 (mod n) for all coprime a.

### How does the tool prove minimality?

It tests a^(k/p) mod n for each prime factor p dividing the computed order k to demonstrate that no smaller proper divisor yields 1.

### What are the input limits for a and n?

Element a accepts values up to 10⁵¹² (which are reduced modulo n), while modulus n supports values between 2 and 10¹².

### What does a primitive root flag indicate?

It indicates that ordₙ(a) = φ(n), meaning the powers of a generate every coprime residue in the multiplicative group (ℤ/nℤ)*.

## Related tools

- [Carmichael Function λ(n) Calculator](https://elysiatools.com/en/tools/carmichael-function): Group exponent λ(n) from prime factorization with φ(n) comparison, primitive-root existence, Korselt's Carmichael-number detection, and optional sample-unit verification.
- [Chinese Remainder Theorem Solver (System of Congruences)](https://elysiatools.com/en/tools/chinese-remainder-theorem): Generalized pairwise-merge CRT for 2–20 congruences: coprime moduli give the product modulus, consistent non-coprime moduli give the lcm, inconsistent systems are rejected.
- [Permutation / Combination / Subset Generator (With Repeats)](https://elysiatools.com/en/tools/combinatorial-generation): Deduplicated, lexicographic permutations / combinations / subsets of up to 12 items with exact multiset counts; display capped at 200 entries.
- [Euler Totient Function φ(n) Calculator](https://elysiatools.com/en/tools/euler-totient-function): Exact φ(n) from trial-division factorization (n ≤ 10¹²) with optional coprime listing and Euler's theorem recall.
- [Fraction Decimal Converter](https://elysiatools.com/en/tools/fraction-decimal-converter): Convert between fractions and decimals with support for mixed numbers, improper fractions, and various decimal formats
- [Zero-Sum Game Solver (Saddle Point / Linear Programming)](https://elysiatools.com/en/tools/game-theory-zero-sum): Two-person zero-sum games: saddle-point test first, then mixed strategies from a single-phase simplex LP with dual shadow prices, verified by security-level checks.
- [Inverse Laplace Transform Calculator (Partial Fractions)](https://elysiatools.com/en/tools/inverse-laplace-calculator): Partial-fraction inverse Laplace transform for proper rational functions: root factorization (real + conjugate pairs), exact coefficient system, term-by-term inversion.
- [Laplace Transform Calculator (Table Lookup)](https://elysiatools.com/en/tools/laplace-transform-calculator): Table lookup of L{f(t)} for 14 standard pairs, with parameter substitution, region of convergence, derivation note, and optional numeric F(s₀) evaluation.

## Samples

- [Web Image Processing Python Samples](https://elysiatools.com/en/samples/web-image-processing-python): Web Python image processing examples using PIL/Pillow including reading, saving, resizing, and format conversion
- [Android Image Processing Java Samples](https://elysiatools.com/en/samples/android-image-processing-java): Android Java image processing examples including reading/saving images, scaling, and format conversion
- [Android Image Processing Kotlin Samples](https://elysiatools.com/en/samples/android-image-processing-kotlin): Android Kotlin image processing examples including reading/saving images, scaling, and format conversion
- [Web Image Processing Rust Samples](https://elysiatools.com/en/samples/web-image-processing-rust): Web Rust image processing examples including image read/save, scaling, and format conversion