MultiplicativeGroup

Calculate the multiplicative group of integers modulo n

DefinitionResourceCreateNotebook

We calculate the finite abelian group representation of (Subscript[U, n]):

ClearAll[MGFR];
MGFR[n_]:=
If[n<=2,{1},
Sort@Flatten[
MapApply[
Function[{p,k},
If[p==2,
Which[
k==1,{},
k==2,{2},
k>=3,{2,2^(k-2)}],
{(p-1)p^(k-1)}]],
FactorInteger[n]]]]

Use it to construct the resultant group:

ClearAll[MultiplicativeGroup];
MultiplicativeGroup::usage="MultiplicativeGroup[n] calculates the multiplicative group of integers modulo n.";
MultiplicativeGroup::nnarg="The argument `1` is not greater than or equal to one.";
MultiplicativeGroup[n_Integer]:=
If[n<1,Message[MultiplicativeGroup::nnarg,n];$Failed,
AbelianGroup@MGFR[n]]

Documentation

UsageResourceCreateNotebook

Details & OptionsResourceCreateNotebook

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

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

For n equal to powers of 2, we have (Subscript[U, 2])≅(Subscript[U, 4])≅(Subscript[C, 2]) and (Subscript[U, (2^k)])≅(Subscript[C, 2])×(Subscript[C, (2^(k-2))]) for k>=3.

For n=((Subscript[p, i])^(Subscript[k, i])), we have (Subscript[U, n])≅(Subscript[C, (p-1)(p^(k-1))]).

For n=(∏_(i=1)^k)((Subscript[p, i])^(Subscript[k, i])), we have (Subscript[U, n])≅(∏_(i=1)^k)(Subscript[U, ((Subscript[p, i])^(Subscript[k, i]))]).

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

ExamplesResourceCreateNotebook

Basic Examples

Find the multiplicative group of integers modulo 5:

MultiplicativeGroup[5]

See its group multiplication table:

GroupMultiplicationTable[%]//MatrixForm

See the elements of (Subscript[U, 10]):

GroupElements@MultiplicativeGroup[10]

Compute the multiplicative group of various integers:

MultiplicativeGroup/@Range[10]

Multiple cyclic factors emerge for composite inputs:

MultiplicativeGroup[12]

Calculate large groups:

AbsoluteTiming@MultiplicativeGroup[50!]

Calculate its order:

GroupOrder[%[[2]]]

Scope

Text about additional examples expanding scope (and see other sections for options, applications, etc):

MyFunction[x,y,z]

Options

Applications

Properties and Relations

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

GroupOrder[MultiplicativeGroup[#]]==EulerPhi[#]&/@{3,4,12,15,101}

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

MultiplicativeGroup/@{13,101}

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

MultiplicativeGroup[(29^10)]

CyclicGroup[(29-1)(29^(10-1))]

For powers of 2, we have:

Table[{(2^k),MultiplicativeGroup[(2^k)]},{k,8}]//TableForm

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

MultiplicativeGroup[3 5 7]

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

MultiplicativeGroup[0]

MultiplicativeGroup[x] returns unevaluated for arbitrary inputs:

MultiplicativeGroup[x]

%/.x->4

Possible Issues

Neat Examples

See the Cayley graph of a large MultiplicativeGroup:

CayleyGraph[MultiplicativeGroup[800]]

Source & Additional Information

Contributed ByResourceCreateNotebook

Naman T.

KeywordsResourceCreateNotebook

group theory

multiplicative group

integers

finite abelian groups

cyclic groups

direct products

CategoriesResourceCreateNotebook

Related SymbolsResourceCreateNotebook

Related Resource ObjectsResourceCreateNotebook

Resource Name (resources from any Wolfram repository)

Source/Reference CitationResourceCreateNotebook

Source, reference or citation information

LinksResourceCreateNotebook

Link to other related material

TestsResourceCreateNotebook

VerificationTest[
MultiplicativeGroup[4],
CyclicGroup[2]
]

VerificationTest[
MultiplicativeGroup[0],
$Failed,
{MultiplicativeGroup::nnarg}
]

VerificationTest[
MultiplicativeGroup[12],
AbelianGroup[{2,2}]
]

CompatibilityResourceCreateNotebook

Wolfram Language VersionResourceCreateNotebook

14.3+

Operating SystemResourceCreateNotebook

EnvironmentsResourceCreateNotebook

Cloud SupportResourceCreateNotebook

Required FeaturesResourceCreateNotebook

Author NotesResourceCreateNotebook

Additional information about limitations, issues, etc.

Submission NotesResourceCreateNotebook

Additional information for the reviewer.