# MultiplicativeOrder

MultiplicativeOrder[k,n]

gives the multiplicative order of k modulo n, defined as the smallest integer such that .

MultiplicativeOrder[k,n,{r1,r2,}]

gives the generalized multiplicative order of k modulo n, defined as the smallest integer such that for some .

# Details • MultiplicativeOrder is also known as modulo order or hauptexponent.
• Integer mathematical function, suitable for both symbolic and numerical manipulation.
• Typically used in modular arithmetic and cryptography.
• MultiplicativeOrder[k,n] gives the smallest positive integer m such that the remainder when dividing km by n is equal to 1.
• MultiplicativeOrder returns unevaluated if there is no integer satisfying the necessary conditions.
• # Examples

open allclose all

## Basic Examples(2)

The multiplicative order of 5 modulo 8:

Plot the sequence with a fixed modulus:

Plot the sequence, varying the modulus:

## Scope(6)

### Numerical Manipulation(4)

Compute using integers:

Generalized multiplicative order:

Compute using large numbers:

### Symbolic Manipulation(2)

Use Solve to find solutions of equations:

Use FindInstance to find solutions:

## Applications(9)

### Basic Applications(5)

Find all primitive roots modulo 43:

A rational number has a digit cycle of length if is prime and 10 is a primitive root for :

Compute MultiplicativeOrder using NestWhileList:

Count number of possible multiplicative orders modulo a given prime number:

The number of divisors of where is prime:

These are in fact the same list:

### Number Theory(4)

The repetition period in Rule for odd divides q[n]:

The digits of in base repeat with period :

The function digitCycleLength gives the digit period for any rational number in base :

This shows that the decimal representation of in base 10 repeats every 3 digits:

Build an RSA-like toy encryption scheme:

Perform a cycling attack. One of the outputs will be the plaintext:

## Properties & Relations(5)

The multiplicative order of a primitive root modulo n is EulerPhi[n]:

EulerPhi divides MultiplicativeOrder:

The result is always positive:

Find the smallest integer such that 2, 3, or 4 mod 7:

Find which of the remainders satisfies :

Solve the discrete log problem with :

## Possible Issues(1)

For nonzero integers k and n, MultiplicativeOrder[k,n] exists if and only if k and n are coprime:

However, 10 and 22 are not coprime:

## Interactive Examples(1)

MultiplicativeOrder of each integer below a given prime number:

## Neat Examples(2)

Visualize when a number has multiplicative order modulo 12:

Ulam spiral of MultiplicativeOrder:

Introduced in 1999
(4.0)