Function Repository Resource:

MultiplicativeGroup

Calculate the multiplicative group of integers modulo n

Contributed by: Naman T.

ResourceFunction["MultiplicativeGroup"][n]

calculates the multiplicative group of integers modulo n.

Details and Options

The multiplicative group of integers modulo n, denoted U_n, consists of integers 1<=a<n such that gcd(a,n)=1. Its order is given by EulerPhi[n].

ResourceFunction["MultiplicativeGroup"][n] uses the fundamental theorem of finite abelian groups.

For n equal to powers of 2, we have U₂≅U₄≅C₂ and U_2^k≅C₂×C_2^k-2 for k>=3.

For n=p_i^k_i, we have U_n≅C_(p-1)p^k-1.

For

, we have

ResourceFunction["MultiplicativeGroup"][n] evaluates to an appropriate AbelianGroup, CyclicGroup, or more.

Examples

Basic Examples (5)

Find the multiplicative group of integers modulo 5:

In[1]:=

Out[1]=

See its group multiplication table:

In[2]:=

Out[2]=

See the elements of U₁₀:

In[3]:=

Out[3]=

Compute the multiplicative group of various integers:

In[4]:=

Out[4]=

Multiple cyclic factors emerge for composite inputs:

In[5]:=

Out[5]=

Calculate large groups:

In[6]:=

Out[6]=

Calculate its order:

In[7]:=

Out[7]=

Properties and Relations (7)

Order of MultiplicativeGroup[n] equals EulerPhi[n]:

In[8]:=

Out[8]=

For prime p, MultiplicativeGroup[p] evaluates to CyclicGroup[n-1]:

In[9]:=

Out[9]=

For odd prime powers, MultiplicativeGroup[p^k] evaluates to CyclicGroup[(p-1)p^k-1]:

In[10]:=

Out[10]=

In[11]:=

Out[11]=

For powers of 2, we have:

In[12]:=

$Table[{2^k, ResourceFunction[ CloudObject[ "https://www.wolframcloud.com/obj/namantaggar11/DeployedResources/Function/MultiplicativeGroup"]][2^k]}, {k, 8}] // TableForm$

Out[12]=

MultiplicativeGroup[n] where n has multiple distinct prime factors is never cyclic:

In[13]:=

Out[13]=

MultiplicativeGroup[n] expects n to be a positive integer:

In[14]:=

Out[14]=

MultiplicativeGroup[x] returns unevaluated for arbitrary inputs:

In[15]:=

Out[15]=

In[16]:=

Out[16]=

Neat Examples (1)

See the Cayley graph of a large MultiplicativeGroup:

In[17]:=

Out[17]=