Multiplicative group of integers modulo n

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Multiplicative group of integers modulo n - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available";var cookie=document.cookie.match(/(?:^|; )enwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy", "wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"00f03255-4f8a-42c5-b91e-a73342f1fb59","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Multiplicative_group_of_integers_modulo_n","wgTitle":"Multiplicative group of integers modulo n","wgCurRevisionId":1249898660,"wgRevisionId":1249898660,"wgArticleId":1195234,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Articles with short description","Short description matches Wikidata","Finite groups","Modular arithmetic","Multiplication"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Multiplicative_group_of_integers_modulo_n","wgRelevantArticleId":1195234,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[], "wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}},"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":30000,"wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":false,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q1169249","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false, "wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.math.styles":"ready","ext.cite.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","jquery.makeCollapsible.styles":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","ext.scribunto.logs","site","mediawiki.page.ready","jquery.makeCollapsible","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.popups", "ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.quicksurveys.init","ext.growthExperiments.SuggestedEditSession","wikibase.sidebar.tracking"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=en&modules=ext.cite.styles%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cext.wikimediamessages.styles%7Cjquery.makeCollapsible.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.4"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/5/5f/Cyclic_group.svg/1200px-Cyclic_group.svg.png"> <meta property="og:image:width" content="1200"> <meta property="og:image:height" content="1167"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/5/5f/Cyclic_group.svg/800px-Cyclic_group.svg.png"> <meta property="og:image:width" content="800"> <meta property="og:image:height" content="778"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/5/5f/Cyclic_group.svg/640px-Cyclic_group.svg.png"> <meta property="og:image:width" content="640"> <meta property="og:image:height" content="623"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Multiplicative group of integers modulo n - Wikipedia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//en.m.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Multiplicative_group_of_integers_modulo_n&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipedia (en)"> <link rel="EditURI" type="application/rsd+xml" href="//en.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en"> <link rel="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="/w/index.php?title=Special:RecentChanges&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="//login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Multiplicative_group_of_integers_modulo_n rootpage-Multiplicative_group_of_integers_modulo_n skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Jump to content</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Main menu" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Main menu</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Main menu</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">hide</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z"><span>Main page</span></a></li><li id="n-contents" class="mw-list-item"><a href="/wiki/Wikipedia:Contents" title="Guides to browsing Wikipedia"><span>Contents</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:Current_events" title="Articles related to current events"><span>Current events</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Random" title="Visit a randomly selected article [x]" accesskey="x"><span>Random article</span></a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:About" title="Learn about Wikipedia and how it works"><span>About Wikipedia</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia"><span>Contact us</span></a></li> </ul> </div> </div> <div id="p-interaction" class="vector-menu mw-portlet mw-portlet-interaction" > <div class="vector-menu-heading"> Contribute </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia"><span>Help</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/Help:Introduction" title="Learn how to edit Wikipedia"><span>Learn to edit</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Community_portal" title="The hub for editors"><span>Community portal</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:RecentChanges" title="A list of recent changes to Wikipedia [r]" accesskey="r"><span>Recent changes</span></a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_upload_wizard" title="Add images or other media for use on Wikipedia"><span>Upload file</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Main_Page" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="The Free Encyclopedia" src="/static/images/mobile/copyright/wikipedia-tagline-en.svg" width="117" height="13" style="width: 7.3125em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Special:Search" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Search Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search Wikipedia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Personal tools"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Appearance" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Appearance</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en" class=""><span>Donate</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:CreateAccount&returnto=Multiplicative+group+of+integers+modulo+n" title="You are encouraged to create an account and log in; however, it is not mandatory" class=""><span>Create account</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:UserLogin&returnto=Multiplicative+group+of+integers+modulo+n" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o" class=""><span>Log in</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Log in and more options" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Personal tools" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Personal tools</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="User menu" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en"><span>Donate</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&returnto=Multiplicative+group+of+integers+modulo+n" title="You are encouraged to create an account and log in; however, it is not mandatory"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Create account</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:UserLogin&returnto=Multiplicative+group+of+integers+modulo+n" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Log in</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pages for logged out editors <a href="/wiki/Help:Introduction" aria-label="Learn more about editing"><span>learn more</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Special:MyContributions" title="A list of edits made from this IP address [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Special:MyTalk" title="Discussion about edits from this IP address [n]" accesskey="n"><span>Talk</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Contents" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Contents</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">hide</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">(Top)</div> </a> </li> <li id="toc-Group_axioms" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Group_axioms"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Group axioms</span> </div> </a> <ul id="toc-Group_axioms-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Notation" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Notation"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Notation</span> </div> </a> <ul id="toc-Notation-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Structure" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Structure"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Structure</span> </div> </a> <button aria-controls="toc-Structure-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Structure subsection</span> </button> <ul id="toc-Structure-sublist" class="vector-toc-list"> <li id="toc-Cyclic_case" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Cyclic_case"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.1</span> <span>Cyclic case</span> </div> </a> <ul id="toc-Cyclic_case-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Powers_of_2" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Powers_of_2"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.2</span> <span>Powers of 2</span> </div> </a> <ul id="toc-Powers_of_2-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-General_composite_numbers" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#General_composite_numbers"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.3</span> <span>General composite numbers</span> </div> </a> <ul id="toc-General_composite_numbers-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Subgroup_of_false_witnesses" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Subgroup_of_false_witnesses"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Subgroup of false witnesses</span> </div> </a> <button aria-controls="toc-Subgroup_of_false_witnesses-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Subgroup of false witnesses subsection</span> </button> <ul id="toc-Subgroup_of_false_witnesses-sublist" class="vector-toc-list"> <li id="toc-Examples" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Examples"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.1</span> <span>Examples</span> </div> </a> <ul id="toc-Examples-sublist" class="vector-toc-list"> <li id="toc-n_=_9" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#n_=_9"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.1.1</span> <span><i>n</i> = 9</span> </div> </a> <ul id="toc-n_=_9-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-n_=_91" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#n_=_91"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.1.2</span> <span><i>n</i> = 91</span> </div> </a> <ul id="toc-n_=_91-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-n_=_561" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#n_=_561"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.1.3</span> <span><i>n</i> = 561</span> </div> </a> <ul id="toc-n_=_561-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> </ul> </li> <li id="toc-Examples_2" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Examples_2"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Examples</span> </div> </a> <ul id="toc-Examples_2-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-See_also" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#See_also"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>See also</span> </div> </a> <ul id="toc-See_also-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Notes" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Notes"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>Notes</span> </div> </a> <ul id="toc-Notes-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-References" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#References"> <div class="vector-toc-text"> <span class="vector-toc-numb">8</span> <span>References</span> </div> </a> <ul id="toc-References-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-External_links" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#External_links"> <div class="vector-toc-text"> <span class="vector-toc-numb">9</span> <span>External links</span> </div> </a> <ul id="toc-External_links-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading">Multiplicative group of integers modulo <i>n</i></h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Go to an article in another language. Available in 7 languages" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-7" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> <span class="vector-dropdown-label-text">7 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Prime_Restklassengruppe" title="Prime Restklassengruppe – German" lang="de" hreflang="de" data-title="Prime Restklassengruppe" data-language-autonym="Deutsch" data-language-local-name="German" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/Grupo_multiplicativo_de_enteros_m%C3%B3dulo_n" title="Grupo multiplicativo de enteros módulo n – Spanish" lang="es" hreflang="es" data-title="Grupo multiplicativo de enteros módulo n" data-language-autonym="Español" data-language-local-name="Spanish" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-he mw-list-item"><a href="https://he.wikipedia.org/wiki/%D7%97%D7%91%D7%95%D7%A8%D7%AA_%D7%90%D7%95%D7%99%D7%9C%D7%A8" title="חבורת אוילר – Hebrew" lang="he" hreflang="he" data-title="חבורת אוילר" data-language-autonym="עברית" data-language-local-name="Hebrew" class="interlanguage-link-target"><span>עברית</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%9C%D1%83%D0%BB%D1%8C%D1%82%D0%B8%D0%BF%D0%BB%D0%B8%D0%BA%D0%B0%D1%82%D0%B8%D0%B2%D0%BD%D0%B0%D1%8F_%D0%B3%D1%80%D1%83%D0%BF%D0%BF%D0%B0_%D0%BA%D0%BE%D0%BB%D1%8C%D1%86%D0%B0_%D0%B2%D1%8B%D1%87%D0%B5%D1%82%D0%BE%D0%B2" title="Мультипликативная группа кольца вычетов – Russian" lang="ru" hreflang="ru" data-title="Мультипликативная группа кольца вычетов" data-language-autonym="Русский" data-language-local-name="Russian" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%9C%D1%83%D0%BB%D1%8C%D1%82%D0%B8%D0%BF%D0%BB%D1%96%D0%BA%D0%B0%D1%82%D0%B8%D0%B2%D0%BD%D0%B0_%D0%B3%D1%80%D1%83%D0%BF%D0%B0_%D0%BA%D1%96%D0%BB%D1%8C%D1%86%D1%8F_%D0%BB%D0%B8%D1%88%D0%BA%D1%96%D0%B2_%D0%B7%D0%B0_%D0%BC%D0%BE%D0%B4%D1%83%D0%BB%D0%B5%D0%BC_n" title="Мультиплікативна група кільця лишків за модулем n – Ukrainian" lang="uk" hreflang="uk" data-title="Мультиплікативна група кільця лишків за модулем n" data-language-autonym="Українська" data-language-local-name="Ukrainian" class="interlanguage-link-target"><span>Українська</span></a></li><li class="interlanguage-link interwiki-vi mw-list-item"><a href="https://vi.wikipedia.org/wiki/Nh%C3%B3m_nh%C3%A2n_c%C3%A1c_s%E1%BB%91_nguy%C3%AAn_modulo_n" title="Nhóm nhân các số nguyên modulo n – Vietnamese" lang="vi" hreflang="vi" data-title="Nhóm nhân các số nguyên modulo n" data-language-autonym="Tiếng Việt" data-language-local-name="Vietnamese" class="interlanguage-link-target"><span>Tiếng Việt</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E6%95%B4%E6%95%B0%E6%A8%A1n%E4%B9%98%E6%B3%95%E7%BE%A4" title="整数模n乘法群 – Chinese" lang="zh" hreflang="zh" data-title="整数模n乘法群" data-language-autonym="中文" data-language-local-name="Chinese" class="interlanguage-link-target"><span>中文</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q1169249#sitelinks-wikipedia" title="Edit interlanguage links" class="wbc-editpage">Edit links</a></span></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Namespaces"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Multiplicative_group_of_integers_modulo_n" title="View the content page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Talk:Multiplicative_group_of_integers_modulo_n" rel="discussion" title="Discuss improvements to the content page [t]" accesskey="t"><span>Talk</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Change language variant" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">English</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Views"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Multiplicative_group_of_integers_modulo_n"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Multiplicative_group_of_integers_modulo_n&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Multiplicative_group_of_integers_modulo_n&action=history" title="Past revisions of this page [h]" accesskey="h"><span>View history</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Tools" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Tools</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Tools</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">hide</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="More options" > <div class="vector-menu-heading"> Actions </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/Multiplicative_group_of_integers_modulo_n"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Multiplicative_group_of_integers_modulo_n&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Multiplicative_group_of_integers_modulo_n&action=history"><span>View history</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> General </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Special:WhatLinksHere/Multiplicative_group_of_integers_modulo_n" title="List of all English Wikipedia pages containing links to this page [j]" accesskey="j"><span>What links here</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Special:RecentChangesLinked/Multiplicative_group_of_integers_modulo_n" rel="nofollow" title="Recent changes in pages linked from this page [k]" accesskey="k"><span>Related changes</span></a></li><li id="t-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages" title="A list of all special pages [q]" accesskey="q"><span>Special pages</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Multiplicative_group_of_integers_modulo_n&oldid=1249898660" title="Permanent link to this revision of this page"><span>Permanent link</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Multiplicative_group_of_integers_modulo_n&action=info" title="More information about this page"><span>Page information</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Special:CiteThisPage&page=Multiplicative_group_of_integers_modulo_n&id=1249898660&wpFormIdentifier=titleform" title="Information on how to cite this page"><span>Cite this page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FMultiplicative_group_of_integers_modulo_n"><span>Get shortened URL</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Special:QrCode&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FMultiplicative_group_of_integers_modulo_n"><span>Download QR code</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Print/export </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Special:DownloadAsPdf&page=Multiplicative_group_of_integers_modulo_n&action=show-download-screen" title="Download this page as a PDF file"><span>Download as PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Multiplicative_group_of_integers_modulo_n&printable=yes" title="Printable version of this page [p]" accesskey="p"><span>Printable version</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> In other projects </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q1169249" title="Structured data on this page hosted by Wikidata [g]" accesskey="g"><span>Wikidata item</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Appearance</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">hide</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">From Wikipedia, the free encyclopedia</div> </div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><div class="shortdescription nomobile noexcerpt noprint searchaux" style="display:none">Group of units of the ring of integers modulo n</div> <p>In <a href="/wiki/Modular_arithmetic" title="Modular arithmetic">modular arithmetic</a>, the <a href="/wiki/Integer" title="Integer">integers</a> <a href="/wiki/Coprime" class="mw-redirect" title="Coprime">coprime</a> (relatively prime) to <i>n</i> from the set <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{0,1,\dots ,n-1\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">{</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo>,</mo> <mo>…</mo> <mo>,</mo> <mi>n</mi> <mo>−</mo> <mn>1</mn> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \{0,1,\dots ,n-1\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/83abd2a9b860d2cb7cbb2357e3308468fb8dcd4b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.26ex; height:2.843ex;" alt="{\displaystyle \{0,1,\dots ,n-1\}}"></span> of <i>n</i> non-negative integers form a <a href="/wiki/Group_(mathematics)" title="Group (mathematics)">group</a> under multiplication <a href="/wiki/Integers_modulo_n" class="mw-redirect" title="Integers modulo n">modulo <i>n</i></a>, called the <b>multiplicative group of integers modulo <i>n</i></b>. Equivalently, the elements of this group can be thought of as the <a href="/wiki/Modular_arithmetic#Congruence_class" title="Modular arithmetic">congruence classes</a>, also known as <i>residues</i> modulo <i>n</i>, that are coprime to <i>n</i>. Hence another name is the group of <b>primitive residue classes modulo <i>n</i></b>. In the <a href="/wiki/Ring_(algebra)" class="mw-redirect" title="Ring (algebra)">theory of rings</a>, a branch of <a href="/wiki/Abstract_algebra" title="Abstract algebra">abstract algebra</a>, it is described as the <a href="/wiki/Group_of_units" class="mw-redirect" title="Group of units">group of units</a> of the <a href="/wiki/Ring_of_integers_modulo_n" class="mw-redirect" title="Ring of integers modulo n">ring of integers modulo <i>n</i></a>. Here <i>units</i> refers to elements with a <a href="/wiki/Modular_multiplicative_inverse" title="Modular multiplicative inverse">multiplicative inverse</a>, which, in this ring, are exactly those coprime to <i>n</i>. </p> <style data-mw-deduplicate="TemplateStyles:r1129693374">.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}</style><style data-mw-deduplicate="TemplateStyles:r1246091330">.mw-parser-output .sidebar{width:22em;float:right;clear:right;margin:0.5em 0 1em 1em;background:var(--background-color-neutral-subtle,#f8f9fa);border:1px solid var(--border-color-base,#a2a9b1);padding:0.2em;text-align:center;line-height:1.4em;font-size:88%;border-collapse:collapse;display:table}body.skin-minerva .mw-parser-output .sidebar{display:table!important;float:right!important;margin:0.5em 0 1em 1em!important}.mw-parser-output .sidebar-subgroup{width:100%;margin:0;border-spacing:0}.mw-parser-output .sidebar-left{float:left;clear:left;margin:0.5em 1em 1em 0}.mw-parser-output .sidebar-none{float:none;clear:both;margin:0.5em 1em 1em 0}.mw-parser-output .sidebar-outer-title{padding:0 0.4em 0.2em;font-size:125%;line-height:1.2em;font-weight:bold}.mw-parser-output .sidebar-top-image{padding:0.4em}.mw-parser-output .sidebar-top-caption,.mw-parser-output .sidebar-pretitle-with-top-image,.mw-parser-output .sidebar-caption{padding:0.2em 0.4em 0;line-height:1.2em}.mw-parser-output .sidebar-pretitle{padding:0.4em 0.4em 0;line-height:1.2em}.mw-parser-output .sidebar-title,.mw-parser-output .sidebar-title-with-pretitle{padding:0.2em 0.8em;font-size:145%;line-height:1.2em}.mw-parser-output .sidebar-title-with-pretitle{padding:0.1em 0.4em}.mw-parser-output .sidebar-image{padding:0.2em 0.4em 0.4em}.mw-parser-output .sidebar-heading{padding:0.1em 0.4em}.mw-parser-output .sidebar-content{padding:0 0.5em 0.4em}.mw-parser-output .sidebar-content-with-subgroup{padding:0.1em 0.4em 0.2em}.mw-parser-output .sidebar-above,.mw-parser-output .sidebar-below{padding:0.3em 0.8em;font-weight:bold}.mw-parser-output .sidebar-collapse .sidebar-above,.mw-parser-output .sidebar-collapse .sidebar-below{border-top:1px solid #aaa;border-bottom:1px solid #aaa}.mw-parser-output .sidebar-navbar{text-align:right;font-size:115%;padding:0 0.4em 0.4em}.mw-parser-output .sidebar-list-title{padding:0 0.4em;text-align:left;font-weight:bold;line-height:1.6em;font-size:105%}.mw-parser-output .sidebar-list-title-c{padding:0 0.4em;text-align:center;margin:0 3.3em}@media(max-width:640px){body.mediawiki .mw-parser-output .sidebar{width:100%!important;clear:both;float:none!important;margin-left:0!important;margin-right:0!important}}body.skin--responsive .mw-parser-output .sidebar a>img{max-width:none!important}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-list-title,html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle{background:transparent!important}html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle a{color:var(--color-progressive)!important}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-list-title,html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle{background:transparent!important}html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle a{color:var(--color-progressive)!important}}@media print{body.ns-0 .mw-parser-output .sidebar{display:none!important}}</style><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1246091330"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1246091330"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1246091330"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1246091330"><table class="sidebar sidebar-collapse nomobile nowraplinks" style="width:20.0em;"><tbody><tr><th class="sidebar-title" style="padding-bottom:0.4em;"><span style="font-size: 8pt; font-weight: none"><a href="/wiki/Algebraic_structure" title="Algebraic structure">Algebraic structure</a> → <b>Group theory</b></span><br /><a href="/wiki/Group_theory" title="Group theory">Group theory</a></th></tr><tr><td class="sidebar-image"><span class="skin-invert"><span typeof="mw:File"><a href="/wiki/File:Cyclic_group.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/5/5f/Cyclic_group.svg/120px-Cyclic_group.svg.png" decoding="async" width="120" height="117" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/5/5f/Cyclic_group.svg/180px-Cyclic_group.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/5/5f/Cyclic_group.svg/240px-Cyclic_group.svg.png 2x" data-file-width="443" data-file-height="431" /></a></span></span></td></tr><tr><td class="sidebar-content"> <div class="sidebar-list mw-collapsible mw-collapsed"><div class="sidebar-list-title" style="background:transparent;border-top:1px solid #aaa;text-align:center;;color: var(--color-base)">Basic notions</div><div class="sidebar-list-content mw-collapsible-content hlist" style="border-top:1px solid #aaa;border-bottom:1px solid #aaa;"><table class="sidebar nomobile nowraplinks" style="background-color: transparent; color: var( --color-base ); border-collapse:collapse; border-spacing:0px; border:none; width:100%; margin:0px; font-size:100%; clear:none; float:none"><tbody><tr><td class="sidebar-content"> <ul><li><a href="/wiki/Subgroup" title="Subgroup">Subgroup</a></li> <li><a href="/wiki/Normal_subgroup" title="Normal subgroup">Normal subgroup</a></li> <li><a href="/wiki/Group_action" title="Group action">Group action</a></li></ul></td> </tr><tr><td class="sidebar-content"> <ul><li><a href="/wiki/Quotient_group" title="Quotient group">Quotient group</a></li> <li><a href="/wiki/Semidirect_product" title="Semidirect product">(Semi-)</a><a href="/wiki/Direct_product_of_groups" title="Direct product of groups">direct product</a></li> <li><a href="/wiki/Direct_sum_of_groups" title="Direct sum of groups">Direct sum</a></li> <li><a href="/wiki/Free_product" title="Free product">Free product</a></li> <li><a href="/wiki/Wreath_product" title="Wreath product">Wreath product</a></li></ul></td> </tr><tr><th class="sidebar-heading"> <i><a href="/wiki/Group_homomorphism" title="Group homomorphism">Group homomorphisms</a></i></th></tr><tr><td class="sidebar-content"> <ul><li><a href="/wiki/Kernel_(algebra)#Group_homomorphisms" title="Kernel (algebra)">kernel</a></li> <li><a href="/wiki/Image_(mathematics)" title="Image (mathematics)">image</a></li></ul></td> </tr><tr><td class="sidebar-content"> <ul><li><a href="/wiki/Simple_group" title="Simple group">simple</a></li> <li><a href="/wiki/Finite_group" title="Finite group">finite</a></li> <li><a href="/wiki/Infinite_group" title="Infinite group">infinite</a></li> <li><a href="/wiki/Continuous_group" class="mw-redirect" title="Continuous group">continuous</a></li> <li><a href="/wiki/Multiplicative_group" title="Multiplicative group">multiplicative</a></li> <li><a href="/wiki/Additive_group" title="Additive group">additive</a></li> <li><a href="/wiki/Cyclic_group" title="Cyclic group">cyclic</a></li> <li><a href="/wiki/Abelian_group" title="Abelian group">abelian</a></li> <li><a href="/wiki/Dihedral_group" title="Dihedral group">dihedral</a></li> <li><a href="/wiki/Nilpotent_group" title="Nilpotent group">nilpotent</a></li> <li><a href="/wiki/Solvable_group" title="Solvable group">solvable</a></li></ul></td> </tr><tr><td class="sidebar-content"> <ul><li><a href="/wiki/Glossary_of_group_theory" title="Glossary of group theory">Glossary of group theory</a></li> <li><a href="/wiki/List_of_group_theory_topics" title="List of group theory topics">List of group theory topics</a></li></ul></td> </tr></tbody></table></div></div></td> </tr><tr><td class="sidebar-content"> <div class="sidebar-list mw-collapsible"><div class="sidebar-list-title" style="background:transparent;border-top:1px solid #aaa;text-align:center;;color: var(--color-base)"><a href="/wiki/Finite_group" title="Finite group">Finite groups</a></div><div class="sidebar-list-content mw-collapsible-content hlist" style="border-top:1px solid #aaa;border-bottom:1px solid #aaa;"><table class="sidebar nomobile nowraplinks" style="background-color: transparent; color: var( --color-base ); border-collapse:collapse; border-spacing:0px; border:none; width:100%; margin:0px; font-size:100%; clear:none; float:none"><tbody><tr><td class="sidebar-content"> <ul><li><a href="/wiki/Cyclic_group" title="Cyclic group">Cyclic group</a> Z<sub><i>n</i></sub></li> <li><a href="/wiki/Symmetric_group" title="Symmetric group">Symmetric group</a> S<sub><i>n</i></sub></li> <li><a href="/wiki/Alternating_group" title="Alternating group">Alternating group</a> A<sub><i>n</i></sub></li></ul> <ul><li><a href="/wiki/Dihedral_group" title="Dihedral group">Dihedral group</a> D<sub><i>n</i></sub></li> <li><a href="/wiki/Quaternion_group" title="Quaternion group">Quaternion group</a> Q</li></ul></td> </tr><tr><td class="sidebar-content"> <ul><li><a href="/wiki/Cauchy%27s_theorem_(group_theory)" title="Cauchy's theorem (group theory)">Cauchy's theorem</a></li> <li><a href="/wiki/Lagrange%27s_theorem_(group_theory)" title="Lagrange's theorem (group theory)">Lagrange's theorem</a></li></ul> <ul><li><a href="/wiki/Sylow_theorems" title="Sylow theorems">Sylow theorems</a></li> <li><a href="/wiki/Hall_subgroup" title="Hall subgroup">Hall's theorem</a></li></ul> <ul><li><a href="/wiki/P-group" title="P-group"><i>p</i>-group</a></li> <li><a href="/wiki/Elementary_abelian_group" title="Elementary abelian group">Elementary abelian group</a></li></ul> <ul><li><a href="/wiki/Frobenius_group" title="Frobenius group">Frobenius group</a></li></ul> <ul><li><a href="/wiki/Schur_multiplier" title="Schur multiplier">Schur multiplier</a></li></ul></td> </tr><tr><th class="sidebar-heading"> <a href="/wiki/Classification_of_finite_simple_groups" title="Classification of finite simple groups">Classification of finite simple groups</a></th></tr><tr><td class="sidebar-content"> <ul><li>cyclic</li> <li>alternating</li> <li><a href="/wiki/Group_of_Lie_type" title="Group of Lie type">Lie type</a></li> <li><a href="/wiki/Sporadic_group" title="Sporadic group">sporadic</a></li></ul></td> </tr></tbody></table></div></div></td> </tr><tr><td class="sidebar-content"> <div class="sidebar-list mw-collapsible mw-collapsed"><div class="sidebar-list-title" style="background:transparent;border-top:1px solid #aaa;text-align:center;;color: var(--color-base)"><div class="hlist"><ul><li><a href="/wiki/Discrete_group" title="Discrete group">Discrete groups</a></li><li><a href="/wiki/Lattice_(discrete_subgroup)" title="Lattice (discrete subgroup)">Lattices</a></li></ul></div></div><div class="sidebar-list-content mw-collapsible-content hlist" style="border-top:1px solid #aaa;border-bottom:1px solid #aaa;"> <ul><li><a href="/wiki/Integer" title="Integer">Integers</a> (<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/449494a083e0a1fda2b61c62b2f09b6bee4633dc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.55ex; height:2.176ex;" alt="{\displaystyle \mathbb {Z} }"></span>)</li> <li><a href="/wiki/Free_group" title="Free group">Free group</a></li></ul> <div style="display:inline-block; padding:0.2em 0.4em; line-height:1.2em;"><a href="/wiki/Modular_group" title="Modular group">Modular groups</a> <div class="hlist"><ul><li>PSL(2, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/449494a083e0a1fda2b61c62b2f09b6bee4633dc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.55ex; height:2.176ex;" alt="{\displaystyle \mathbb {Z} }"></span>)</li><li>SL(2, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/449494a083e0a1fda2b61c62b2f09b6bee4633dc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.55ex; height:2.176ex;" alt="{\displaystyle \mathbb {Z} }"></span>)</li></ul></div></div> <ul><li><a href="/wiki/Arithmetic_group" title="Arithmetic group">Arithmetic group</a></li> <li><a href="/wiki/Lattice_(group)" title="Lattice (group)">Lattice</a></li> <li><a href="/wiki/Hyperbolic_group" title="Hyperbolic group">Hyperbolic group</a></li></ul></div></div></td> </tr><tr><td class="sidebar-content"> <div class="sidebar-list mw-collapsible mw-collapsed"><div class="sidebar-list-title" style="background:transparent;border-top:1px solid #aaa;text-align:center;;color: var(--color-base)"><a href="/wiki/Topological_group" title="Topological group">Topological</a> and <a href="/wiki/Lie_group" title="Lie group">Lie groups</a></div><div class="sidebar-list-content mw-collapsible-content hlist" style="border-top:1px solid #aaa;border-bottom:1px solid #aaa;"> <ul><li><a href="/wiki/Solenoid_(mathematics)" title="Solenoid (mathematics)">Solenoid</a></li> <li><a href="/wiki/Circle_group" title="Circle group">Circle</a></li></ul> <ul><li><a href="/wiki/General_linear_group" title="General linear group">General linear</a> GL(<i>n</i>)</li></ul> <ul><li><a href="/wiki/Special_linear_group" title="Special linear group">Special linear</a> SL(<i>n</i>)</li></ul> <ul><li><a href="/wiki/Orthogonal_group" title="Orthogonal group">Orthogonal</a> O(<i>n</i>)</li></ul> <ul><li><a href="/wiki/Euclidean_group" title="Euclidean group">Euclidean</a> E(<i>n</i>)</li></ul> <ul><li><a href="/wiki/Special_orthogonal_group" class="mw-redirect" title="Special orthogonal group">Special orthogonal</a> SO(<i>n</i>)</li></ul> <ul><li><a href="/wiki/Unitary_group" title="Unitary group">Unitary</a> U(<i>n</i>)</li></ul> <ul><li><a href="/wiki/Special_unitary_group" title="Special unitary group">Special unitary</a> SU(<i>n</i>)</li></ul> <ul><li><a href="/wiki/Symplectic_group" title="Symplectic group">Symplectic</a> Sp(<i>n</i>)</li></ul> <ul><li><a href="/wiki/G2_(mathematics)" title="G2 (mathematics)">G<sub>2</sub></a></li> <li><a href="/wiki/F4_(mathematics)" title="F4 (mathematics)">F<sub>4</sub></a></li> <li><a href="/wiki/E6_(mathematics)" title="E6 (mathematics)">E<sub>6</sub></a></li> <li><a href="/wiki/E7_(mathematics)" title="E7 (mathematics)">E<sub>7</sub></a></li> <li><a href="/wiki/E8_(mathematics)" title="E8 (mathematics)">E<sub>8</sub></a></li></ul> <ul><li><a href="/wiki/Lorentz_group" title="Lorentz group">Lorentz</a></li> <li><a href="/wiki/Poincar%C3%A9_group" title="Poincaré group">Poincaré</a></li> <li><a href="/wiki/Conformal_group" title="Conformal group">Conformal</a></li></ul> <ul><li><a href="/wiki/Diffeomorphism" title="Diffeomorphism">Diffeomorphism</a></li> <li><a href="/wiki/Loop_group" title="Loop group">Loop</a></li></ul> <div style="display:inline-block; padding:0.2em 0.4em; line-height:1.2em;"><a href="/wiki/Infinite_dimensional_Lie_group" class="mw-redirect" title="Infinite dimensional Lie group">Infinite dimensional Lie group</a> <div class="hlist"><ul><li>O(∞)</li><li>SU(∞)</li><li>Sp(∞)</li></ul></div></div></div></div></td> </tr><tr><td class="sidebar-content"> <div class="sidebar-list mw-collapsible mw-collapsed"><div class="sidebar-list-title" style="background:transparent;border-top:1px solid #aaa;text-align:center;;color: var(--color-base)"><a href="/wiki/Algebraic_group" title="Algebraic group">Algebraic groups</a></div><div class="sidebar-list-content mw-collapsible-content hlist" style="border-top:1px solid #aaa;border-bottom:1px solid #aaa;"> <ul><li><a href="/wiki/Linear_algebraic_group" title="Linear algebraic group">Linear algebraic group</a></li></ul> <ul><li><a href="/wiki/Reductive_group" title="Reductive group">Reductive group</a></li></ul> <ul><li><a href="/wiki/Abelian_variety" title="Abelian variety">Abelian variety</a></li></ul> <ul><li><a href="/wiki/Elliptic_curve" title="Elliptic curve">Elliptic curve</a></li></ul></div></div></td> </tr><tr><td class="sidebar-navbar"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><style data-mw-deduplicate="TemplateStyles:r1239400231">.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}</style><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Group_theory_sidebar" title="Template:Group theory sidebar"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Group_theory_sidebar" title="Template talk:Group theory sidebar"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Group_theory_sidebar" title="Special:EditPage/Template:Group theory sidebar"><abbr title="Edit this template">e</abbr></a></li></ul></div></td></tr></tbody></table> <p>This group, usually denoted <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>×</mo> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bffe12a165220346c352fd4839b7c35dbaa08eb0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.978ex; height:2.843ex;" alt="{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}"></span>, is fundamental in <a href="/wiki/Number_theory" title="Number theory">number theory</a>. It is used in <a href="/wiki/Cryptography" title="Cryptography">cryptography</a>, <a href="/wiki/Integer_factorization" title="Integer factorization">integer factorization</a>, and <a href="/wiki/Primality_test" title="Primality test">primality testing</a>. It is an <a href="/wiki/Abelian_group" title="Abelian group">abelian</a>, <a href="/wiki/Finite_group" title="Finite group">finite</a> group whose <a href="/wiki/Order_of_a_group" class="mw-redirect" title="Order of a group">order</a> is given by <a href="/wiki/Euler%27s_totient_function" title="Euler's totient function">Euler's totient function</a>: <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |(\mathbb {Z} /n\mathbb {Z} )^{\times }|=\varphi (n).}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>×</mo> </mrow> </msup> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mo>=</mo> <mi>φ</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |(\mathbb {Z} /n\mathbb {Z} )^{\times }|=\varphi (n).}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9c9ed148855d19b96070cb7badb69060742e590f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.741ex; height:2.843ex;" alt="{\displaystyle |(\mathbb {Z} /n\mathbb {Z} )^{\times }|=\varphi (n).}"></span> For prime <i>n</i> the group is <a href="/wiki/Cyclic_group" title="Cyclic group">cyclic</a>, and in general the structure is easy to describe, but no simple general formula for finding <a href="/wiki/Generating_set_of_a_group" title="Generating set of a group">generators</a> is known. </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Group_axioms">Group axioms</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Multiplicative_group_of_integers_modulo_n&action=edit&section=1" title="Edit section: Group axioms"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>It is a straightforward exercise to show that, under multiplication, the set of <a href="/wiki/Congruence_class" class="mw-redirect" title="Congruence class">congruence classes</a> modulo <i>n</i> that are coprime to <i>n</i> satisfy the axioms for an <a href="/wiki/Abelian_group" title="Abelian group">abelian group</a>. </p><p>Indeed, <i>a</i> is coprime to <i>n</i> if and only if <span class="nowrap"><a href="/wiki/Greatest_common_divisor" title="Greatest common divisor">gcd</a>(<i>a</i>, <i>n</i>) = 1</span>. Integers in the same congruence class <span class="nowrap"><i>a</i> ≡ <i>b</i> (mod <i>n</i>)</span> satisfy <span class="nowrap">gcd(<i>a</i>, <i>n</i>) = gcd(<i>b</i>, <i>n</i>)</span>; hence one is coprime to <i>n</i> if and only if the other is. Thus the notion of congruence classes modulo <i>n</i> that are coprime to <i>n</i> is well-defined. </p><p>Since <span class="nowrap">gcd(<i>a</i>, <i>n</i>) = 1</span> and <span class="nowrap">gcd(<i>b</i>, <i>n</i>) = 1</span> implies <span class="nowrap">gcd(<i>ab</i>, <i>n</i>) = 1</span>, the set of classes coprime to <i>n</i> is closed under multiplication. </p><p>Integer multiplication respects the congruence classes, that is, <span class="nowrap"><i>a</i> ≡ <i>a' </i></span> and <span class="nowrap"><i>b</i> ≡ <i>b' </i> (mod <i>n</i>)</span> implies <span class="nowrap"><i>ab</i> ≡ <i>a'b' </i> (mod <i>n</i>)</span>. This implies that the multiplication is associative, commutative, and that the class of 1 is the unique multiplicative identity. </p><p>Finally, given <i>a</i>, the <a href="/wiki/Modular_multiplicative_inverse" title="Modular multiplicative inverse">multiplicative inverse</a> of <i>a</i> modulo <i>n</i> is an integer <i>x</i> satisfying <span class="nowrap"><i>ax</i> ≡ 1 (mod <i>n</i>)</span>. It exists precisely when <i>a</i> is coprime to <i>n</i>, because in that case <span class="nowrap">gcd(<i>a</i>, <i>n</i>) = 1</span> and by <a href="/wiki/B%C3%A9zout%27s_lemma" class="mw-redirect" title="Bézout's lemma">Bézout's lemma</a> there are integers <i>x</i> and <i>y</i> satisfying <span class="nowrap"><i>ax</i> + <i>ny</i> = 1</span>. Notice that the equation <span class="nowrap"><i>ax</i> + <i>ny</i> = 1</span> implies that <i>x</i> is coprime to <i>n</i>, so the multiplicative inverse belongs to the group. </p> <div class="mw-heading mw-heading2"><h2 id="Notation">Notation</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Multiplicative_group_of_integers_modulo_n&action=edit&section=2" title="Edit section: Notation"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The set of (congruence classes of) integers modulo <i>n</i> with the operations of addition and multiplication is a <a href="/wiki/Ring_(mathematics)" title="Ring (mathematics)">ring</a>. It is denoted <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} /n\mathbb {Z} }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} /n\mathbb {Z} }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f2120ebbc85f91df66c6de5446367bf9fd620844" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.658ex; height:2.843ex;" alt="{\displaystyle \mathbb {Z} /n\mathbb {Z} }"></span>  or  <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} /(n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} /(n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0639d2973f71226a502767b14c0b7f9f5876c6c2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.917ex; height:2.843ex;" alt="{\displaystyle \mathbb {Z} /(n)}"></span>  (the notation refers to taking the <a href="/wiki/Quotient_ring" title="Quotient ring">quotient</a> of integers modulo the <a href="/wiki/Ideal_(ring_theory)" title="Ideal (ring theory)">ideal</a> <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\mathbb {Z} }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n\mathbb {Z} }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/33e5e8bd9b24ba5d0b31eda653b78a63e1af831d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.945ex; height:2.176ex;" alt="{\displaystyle n\mathbb {Z} }"></span> or <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6dcf3083121187f661e0add2f50615aa21428e68" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.204ex; height:2.843ex;" alt="{\displaystyle (n)}"></span> consisting of the multiples of <i>n</i>). Outside of number theory the simpler notation <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} _{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} _{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7b729c334a9863c47f0b7e3ad61342c2f0881bdb" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.769ex; height:2.509ex;" alt="{\displaystyle \mathbb {Z} _{n}}"></span> is often used, though it can be confused with the <a href="/wiki/P-adic_number" title="P-adic number"><span class="texhtml"><var>p</var></span>-adic integers</a> when <i>n</i> is a prime number. </p><p>The multiplicative group of integers modulo <i>n</i>, which is the <a href="/wiki/Group_of_units" class="mw-redirect" title="Group of units">group of units</a> in this ring, may be written as (depending on the author) <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times },}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>×</mo> </mrow> </msup> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times },}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3fe8cc69f7ba238d7604880ea92f4b7c707fb65b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.625ex; height:2.843ex;" alt="{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times },}"></span>   <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*},}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>∗</mo> </mrow> </msup> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*},}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1b26dd634f583aaab1cf6fb581918e0ed3d4432c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.168ex; height:2.843ex;" alt="{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*},}"></span>   <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathrm {U} (\mathbb {Z} /n\mathbb {Z} ),}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">U</mi> </mrow> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mo stretchy="false">)</mo> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathrm {U} (\mathbb {Z} /n\mathbb {Z} ),}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/843617c87ea4f560adacf30e2b4376984263baf2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.857ex; height:2.843ex;" alt="{\displaystyle \mathrm {U} (\mathbb {Z} /n\mathbb {Z} ),}"></span>   <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathrm {E} (\mathbb {Z} /n\mathbb {Z} )}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">E</mi> </mrow> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathrm {E} (\mathbb {Z} /n\mathbb {Z} )}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f59276ccafb30413e86f8a3fecb6027c6fc07ae5" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.05ex; height:2.843ex;" alt="{\displaystyle \mathrm {E} (\mathbb {Z} /n\mathbb {Z} )}"></span>   (for German <i>Einheit</i>, which translates as <i>unit</i>), <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} _{n}^{*}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msubsup> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>∗</mo> </mrow> </msubsup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} _{n}^{*}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4f61825e3fdaaeb1c4839c3da1ec7bbecdcb4676" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.769ex; height:2.843ex;" alt="{\displaystyle \mathbb {Z} _{n}^{*}}"></span>, or similar notations. This article uses <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>×</mo> </mrow> </msup> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bea2d23c3b7b7cfa11a2cda0fddb18ec72397999" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.625ex; height:2.843ex;" alt="{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }.}"></span> </p><p>The notation <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathrm {C} _{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">C</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathrm {C} _{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c9cd15d2dd0b4299b0ae5953cff1274b283f239e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.897ex; height:2.509ex;" alt="{\displaystyle \mathrm {C} _{n}}"></span> refers to the <a href="/wiki/Cyclic_group" title="Cyclic group">cyclic group</a> of order <i>n</i>. It is <a href="/wiki/Group_isomorphism" title="Group isomorphism">isomorphic</a> to the group of integers modulo <i>n</i> under addition. Note that <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} /n\mathbb {Z} }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} /n\mathbb {Z} }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f2120ebbc85f91df66c6de5446367bf9fd620844" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.658ex; height:2.843ex;" alt="{\displaystyle \mathbb {Z} /n\mathbb {Z} }"></span> or <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} _{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} _{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7b729c334a9863c47f0b7e3ad61342c2f0881bdb" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.769ex; height:2.509ex;" alt="{\displaystyle \mathbb {Z} _{n}}"></span> may also refer to the group under addition. For example, the multiplicative group <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\mathbb {Z} /p\mathbb {Z} )^{\times }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>×</mo> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (\mathbb {Z} /p\mathbb {Z} )^{\times }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1d2670be05ebf32be93c2f2b0ca6ab899e325f37" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.753ex; height:2.843ex;" alt="{\displaystyle (\mathbb {Z} /p\mathbb {Z} )^{\times }}"></span> for a prime <i>p</i> is cyclic and hence isomorphic to the additive group <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} /(p-1)\mathbb {Z} }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mo stretchy="false">(</mo> <mi>p</mi> <mo>−</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} /(p-1)\mathbb {Z} }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/749daa4cfa7463c32d80c78a3bcb853bd13f13a7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.245ex; height:2.843ex;" alt="{\displaystyle \mathbb {Z} /(p-1)\mathbb {Z} }"></span>, but the isomorphism is not obvious. </p> <div class="mw-heading mw-heading2"><h2 id="Structure">Structure</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Multiplicative_group_of_integers_modulo_n&action=edit&section=3" title="Edit section: Structure"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The order of the multiplicative group of integers modulo <i>n</i> is the number of integers in <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{0,1,\dots ,n-1\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">{</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo>,</mo> <mo>…</mo> <mo>,</mo> <mi>n</mi> <mo>−</mo> <mn>1</mn> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \{0,1,\dots ,n-1\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/83abd2a9b860d2cb7cbb2357e3308468fb8dcd4b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.26ex; height:2.843ex;" alt="{\displaystyle \{0,1,\dots ,n-1\}}"></span> coprime to <i>n</i>. It is given by <a href="/wiki/Euler%27s_totient_function" title="Euler's totient function">Euler's totient function</a>: <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |(\mathbb {Z} /n\mathbb {Z} )^{\times }|=\varphi (n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>×</mo> </mrow> </msup> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mo>=</mo> <mi>φ</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |(\mathbb {Z} /n\mathbb {Z} )^{\times }|=\varphi (n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1d3237f50d3082dd95c596ba9a9055f975ffdd44" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.094ex; height:2.843ex;" alt="{\displaystyle |(\mathbb {Z} /n\mathbb {Z} )^{\times }|=\varphi (n)}"></span> (sequence <span class="nowrap external"><a href="//oeis.org/A000010" class="extiw" title="oeis:A000010">A000010</a></span> in the <a href="/wiki/On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>). For prime <i>p</i>, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varphi (p)=p-1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>φ</mi> <mo stretchy="false">(</mo> <mi>p</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mi>p</mi> <mo>−</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \varphi (p)=p-1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9f222be570dc2170ecd7c23259f90ab6e0247330" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.77ex; height:2.843ex;" alt="{\displaystyle \varphi (p)=p-1}"></span>. </p> <div class="mw-heading mw-heading3"><h3 id="Cyclic_case">Cyclic case</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Multiplicative_group_of_integers_modulo_n&action=edit&section=4" title="Edit section: Cyclic case"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1236090951">.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}</style><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="/wiki/Primitive_root_modulo_n" title="Primitive root modulo n">primitive root modulo n</a></div> <p>The group <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>×</mo> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bffe12a165220346c352fd4839b7c35dbaa08eb0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.978ex; height:2.843ex;" alt="{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}"></span> is <a href="/wiki/Cyclic_group" title="Cyclic group">cyclic</a> if and only if <i>n</i> is 1, 2, 4, <i>p</i><sup><i>k</i></sup> or 2<i>p</i><sup><i>k</i></sup>, where <i>p</i> is an odd prime and <span class="nowrap"><i>k</i> > 0</span>. For all other values of <i>n</i> the group is not cyclic.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Vinogradov2003.pp=105-121_3-0" class="reference"><a href="#cite_note-Vinogradov2003.pp=105-121-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> This was first proved by <a href="/wiki/Carl_Friedrich_Gauss" title="Carl Friedrich Gauss">Gauss</a>.<sup id="cite_ref-FOOTNOTEGauss1986arts._52–56,_82–891_4-0" class="reference"><a href="#cite_note-FOOTNOTEGauss1986arts._52–56,_82–891-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> </p><p>This means that for these <i>n</i>: </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }\cong \mathrm {C} _{\varphi (n)},}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>×</mo> </mrow> </msup> <mo>≅</mo> <msub> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">C</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>φ</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </msub> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }\cong \mathrm {C} _{\varphi (n)},}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/423eae6d41235ea661f1ada5b859033862f28459" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:17.974ex; height:3.176ex;" alt="{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }\cong \mathrm {C} _{\varphi (n)},}"></span> where <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varphi (p^{k})=\varphi (2p^{k})=p^{k}-p^{k-1}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>φ</mi> <mo stretchy="false">(</mo> <msup> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msup> <mo stretchy="false">)</mo> <mo>=</mo> <mi>φ</mi> <mo stretchy="false">(</mo> <mn>2</mn> <msup> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msup> <mo stretchy="false">)</mo> <mo>=</mo> <msup> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msup> <mo>−</mo> <msup> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \varphi (p^{k})=\varphi (2p^{k})=p^{k}-p^{k-1}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b143f88906f8fb0ce40cb26739a02d34d6037cd7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:28.639ex; height:3.176ex;" alt="{\displaystyle \varphi (p^{k})=\varphi (2p^{k})=p^{k}-p^{k-1}.}"></span></dd></dl> <p>By definition, the group is cyclic if and only if it has a <a href="/wiki/Generating_set_of_a_group" title="Generating set of a group">generator</a> <i>g</i> (a <a href="/wiki/Generating_set_of_a_group" title="Generating set of a group">generating set</a> {<i>g</i>} of size one), that is, the powers <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g^{0},g^{1},g^{2},\dots ,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>g</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msup> <mo>,</mo> <msup> <mi>g</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msup> <mo>,</mo> <msup> <mi>g</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>,</mo> <mo>…</mo> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle g^{0},g^{1},g^{2},\dots ,}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/92d0eff536c548cbf09a4ac645f92cefc76b8ffb" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.376ex; height:3.009ex;" alt="{\displaystyle g^{0},g^{1},g^{2},\dots ,}"></span> give all possible residues modulo <i>n</i> coprime to <i>n</i> (the first <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varphi (n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>φ</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \varphi (n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f067864064667dd5f8b2508b9cbf983d89788629" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.724ex; height:2.843ex;" alt="{\displaystyle \varphi (n)}"></span> powers <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g^{0},\dots ,g^{\varphi (n)-1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>g</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msup> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msup> <mi>g</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>φ</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo>−</mo> <mn>1</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle g^{0},\dots ,g^{\varphi (n)-1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f6b7606d420d3faba6e4e7f8ee6f90adf87d7447" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:14.142ex; height:3.176ex;" alt="{\displaystyle g^{0},\dots ,g^{\varphi (n)-1}}"></span> give each exactly once). A generator of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>×</mo> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bffe12a165220346c352fd4839b7c35dbaa08eb0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.978ex; height:2.843ex;" alt="{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}"></span> is called a <b><a href="/wiki/Primitive_root_modulo_n" title="Primitive root modulo n">primitive root modulo <i>n</i></a></b>.<sup id="cite_ref-FOOTNOTEVinogradov2003106_5-0" class="reference"><a href="#cite_note-FOOTNOTEVinogradov2003106-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> If there is any generator, then there are <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varphi (\varphi (n))}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>φ</mi> <mo stretchy="false">(</mo> <mi>φ</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \varphi (\varphi (n))}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8fba23324fad77c600d42341e854329a4557f4ca" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.054ex; height:2.843ex;" alt="{\displaystyle \varphi (\varphi (n))}"></span> of them. </p> <div class="mw-heading mw-heading3"><h3 id="Powers_of_2">Powers of 2</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Multiplicative_group_of_integers_modulo_n&action=edit&section=5" title="Edit section: Powers of 2"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Modulo 1 any two integers are congruent, i.e., there is only one congruence class, [0], coprime to 1. Therefore, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\mathbb {Z} /1\,\mathbb {Z} )^{\times }\cong \mathrm {C} _{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>1</mn> <mspace width="thinmathspace" /> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>×</mo> </mrow> </msup> <mo>≅</mo> <msub> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">C</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (\mathbb {Z} /1\,\mathbb {Z} )^{\times }\cong \mathrm {C} _{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/db9c234ab190f6fd5370666c18bcf1828dea9faa" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.964ex; height:2.843ex;" alt="{\displaystyle (\mathbb {Z} /1\,\mathbb {Z} )^{\times }\cong \mathrm {C} _{1}}"></span> is the trivial group with <span class="nowrap">φ(1) = 1</span> element. Because of its trivial nature, the case of congruences modulo 1 is generally ignored and some authors choose not to include the case of <i>n</i> = 1 in theorem statements. </p><p>Modulo 2 there is only one coprime congruence class, [1], so <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{\times }\cong \mathrm {C} _{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>×</mo> </mrow> </msup> <mo>≅</mo> <msub> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">C</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{\times }\cong \mathrm {C} _{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1036265cc21f2ce6a16b37f98fb12e43c01ed8f3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.576ex; height:2.843ex;" alt="{\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{\times }\cong \mathrm {C} _{1}}"></span> is the <a href="/wiki/Trivial_group" title="Trivial group">trivial group</a>. </p><p>Modulo 4 there are two coprime congruence classes, [1] and [3], so <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\mathbb {Z} /4\mathbb {Z} )^{\times }\cong \mathrm {C} _{2},}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>4</mn> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>×</mo> </mrow> </msup> <mo>≅</mo> <msub> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">C</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (\mathbb {Z} /4\mathbb {Z} )^{\times }\cong \mathrm {C} _{2},}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cc13af24b796489d8e4a6cdc04ef54d2091b482d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.223ex; height:2.843ex;" alt="{\displaystyle (\mathbb {Z} /4\mathbb {Z} )^{\times }\cong \mathrm {C} _{2},}"></span> the cyclic group with two elements. </p><p>Modulo 8 there are four coprime congruence classes, [1], [3], [5] and [7]. The square of each of these is 1, so <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\mathbb {Z} /8\mathbb {Z} )^{\times }\cong \mathrm {C} _{2}\times \mathrm {C} _{2},}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>8</mn> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>×</mo> </mrow> </msup> <mo>≅</mo> <msub> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">C</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>×</mo> <msub> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">C</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (\mathbb {Z} /8\mathbb {Z} )^{\times }\cong \mathrm {C} _{2}\times \mathrm {C} _{2},}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/94f1f7cf646a4341739a0a74e6ba4e4b1dd2a390" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.796ex; height:2.843ex;" alt="{\displaystyle (\mathbb {Z} /8\mathbb {Z} )^{\times }\cong \mathrm {C} _{2}\times \mathrm {C} _{2},}"></span> the <a href="/wiki/Klein_four-group" title="Klein four-group">Klein four-group</a>. </p><p>Modulo 16 there are eight coprime congruence classes [1], [3], [5], [7], [9], [11], [13] and [15]. <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{\pm 1,\pm 7\}\cong \mathrm {C} _{2}\times \mathrm {C} _{2},}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">{</mo> <mo>±</mo> <mn>1</mn> <mo>,</mo> <mo>±</mo> <mn>7</mn> <mo fence="false" stretchy="false">}</mo> <mo>≅</mo> <msub> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">C</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>×</mo> <msub> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">C</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \{\pm 1,\pm 7\}\cong \mathrm {C} _{2}\times \mathrm {C} _{2},}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/21f068a177b462548614ac78d0f3f66448509f63" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.35ex; height:2.843ex;" alt="{\displaystyle \{\pm 1,\pm 7\}\cong \mathrm {C} _{2}\times \mathrm {C} _{2},}"></span> is the 2-<a href="/wiki/Torsion_subgroup" title="Torsion subgroup">torsion subgroup</a> (i.e., the square of each element is 1), so <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\mathbb {Z} /16\mathbb {Z} )^{\times }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>16</mn> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>×</mo> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (\mathbb {Z} /16\mathbb {Z} )^{\times }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/13cb732a2966faae4b1f923473bc84deb0a69cac" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.908ex; height:2.843ex;" alt="{\displaystyle (\mathbb {Z} /16\mathbb {Z} )^{\times }}"></span> is not cyclic. The powers of 3, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{1,3,9,11\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">{</mo> <mn>1</mn> <mo>,</mo> <mn>3</mn> <mo>,</mo> <mn>9</mn> <mo>,</mo> <mn>11</mn> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \{1,3,9,11\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/954adcee426e3b394e3068918bc08c7e46248171" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.239ex; height:2.843ex;" alt="{\displaystyle \{1,3,9,11\}}"></span> are a subgroup of order 4, as are the powers of 5, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{1,5,9,13\}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">{</mo> <mn>1</mn> <mo>,</mo> <mn>5</mn> <mo>,</mo> <mn>9</mn> <mo>,</mo> <mn>13</mn> <mo fence="false" stretchy="false">}</mo> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \{1,5,9,13\}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ae82c6986d4558ca5f82fcd1430447cdec520fc5" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.886ex; height:2.843ex;" alt="{\displaystyle \{1,5,9,13\}.}"></span>   Thus <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\mathbb {Z} /16\mathbb {Z} )^{\times }\cong \mathrm {C} _{2}\times \mathrm {C} _{4}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>16</mn> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>×</mo> </mrow> </msup> <mo>≅</mo> <msub> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">C</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>×</mo> <msub> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">C</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>4</mn> </mrow> </msub> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (\mathbb {Z} /16\mathbb {Z} )^{\times }\cong \mathrm {C} _{2}\times \mathrm {C} _{4}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/63805318dbe91ed7abeda07dc8c5c912911351b6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.958ex; height:2.843ex;" alt="{\displaystyle (\mathbb {Z} /16\mathbb {Z} )^{\times }\cong \mathrm {C} _{2}\times \mathrm {C} _{4}.}"></span> </p><p> The pattern shown by 8 and 16 holds<sup id="cite_ref-FOOTNOTEGauss1986arts._90–91_6-0" class="reference"><a href="#cite_note-FOOTNOTEGauss1986arts._90–91-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> for higher powers 2<sup><i>k</i></sup>, <span class="nowrap"><i>k</i> > 2</span>: <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{\pm 1,2^{k-1}\pm 1\}\cong \mathrm {C} _{2}\times \mathrm {C} _{2},}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">{</mo> <mo>±</mo> <mn>1</mn> <mo>,</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo>±</mo> <mn>1</mn> <mo fence="false" stretchy="false">}</mo> <mo>≅</mo> <msub> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">C</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>×</mo> <msub> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">C</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \{\pm 1,2^{k-1}\pm 1\}\cong \mathrm {C} _{2}\times \mathrm {C} _{2},}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ff42b95cb5db0086a70836a44d07a8a2d7f234cd" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:26.734ex; height:3.176ex;" alt="{\displaystyle \{\pm 1,2^{k-1}\pm 1\}\cong \mathrm {C} _{2}\times \mathrm {C} _{2},}"></span> is the 2-torsion subgroup, so <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\mathbb {Z} /2^{k}\mathbb {Z} )^{\times }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msup> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>×</mo> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (\mathbb {Z} /2^{k}\mathbb {Z} )^{\times }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/10a0307d5e93ac6296f3cda9f14ffc5b6854877e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.834ex; height:3.176ex;" alt="{\displaystyle (\mathbb {Z} /2^{k}\mathbb {Z} )^{\times }}"></span> cannot be cyclic, and the powers of 3 are a cyclic subgroup of order <span class="nowrap">2<sup><i>k</i> − 2</sup></span>, so:</p><blockquote><p><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\mathbb {Z} /2^{k}\mathbb {Z} )^{\times }\cong \mathrm {C} _{2}\times \mathrm {C} _{2^{k-2}}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msup> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>×</mo> </mrow> </msup> <mo>≅</mo> <msub> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">C</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>×</mo> <msub> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">C</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> <mo>−</mo> <mn>2</mn> </mrow> </msup> </mrow> </msub> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (\mathbb {Z} /2^{k}\mathbb {Z} )^{\times }\cong \mathrm {C} _{2}\times \mathrm {C} _{2^{k-2}}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e02cc93731dfe90575b76fb72b1d58d1d870d6c4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:24.45ex; height:3.343ex;" alt="{\displaystyle (\mathbb {Z} /2^{k}\mathbb {Z} )^{\times }\cong \mathrm {C} _{2}\times \mathrm {C} _{2^{k-2}}.}"></span></p></blockquote> <div class="mw-heading mw-heading3"><h3 id="General_composite_numbers">General composite numbers</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Multiplicative_group_of_integers_modulo_n&action=edit&section=6" title="Edit section: General composite numbers"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>By the <a href="/wiki/Fundamental_theorem_of_finite_abelian_groups" class="mw-redirect" title="Fundamental theorem of finite abelian groups">fundamental theorem of finite abelian groups</a>, the group <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>×</mo> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bffe12a165220346c352fd4839b7c35dbaa08eb0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.978ex; height:2.843ex;" alt="{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}"></span> is isomorphic to a <a href="/wiki/Direct_product_of_groups" title="Direct product of groups">direct product</a> of cyclic groups of prime power orders. </p><p>More specifically, the <a href="/wiki/Chinese_remainder_theorem" title="Chinese remainder theorem">Chinese remainder theorem</a><sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> says that if <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \;\;n=p_{1}^{k_{1}}p_{2}^{k_{2}}p_{3}^{k_{3}}\dots ,\;}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mspace width="thickmathspace" /> <mspace width="thickmathspace" /> <mi>n</mi> <mo>=</mo> <msubsup> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mrow> </msubsup> <msubsup> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mrow> </msubsup> <msubsup> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> </mrow> </msubsup> <mo>…</mo> <mo>,</mo> <mspace width="thickmathspace" /> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \;\;n=p_{1}^{k_{1}}p_{2}^{k_{2}}p_{3}^{k_{3}}\dots ,\;}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/44139310e1d3efc38ad3b1760d7e88260cce78a4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:19.842ex; height:3.509ex;" alt="{\displaystyle \;\;n=p_{1}^{k_{1}}p_{2}^{k_{2}}p_{3}^{k_{3}}\dots ,\;}"></span> then the ring <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} /n\mathbb {Z} }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} /n\mathbb {Z} }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f2120ebbc85f91df66c6de5446367bf9fd620844" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.658ex; height:2.843ex;" alt="{\displaystyle \mathbb {Z} /n\mathbb {Z} }"></span> is the <a href="/wiki/Product_of_rings" title="Product of rings">direct product</a> of the rings corresponding to each of its prime power factors: </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} /n\mathbb {Z} \cong \mathbb {Z} /{p_{1}^{k_{1}}}\mathbb {Z} \;\times \;\mathbb {Z} /{p_{2}^{k_{2}}}\mathbb {Z} \;\times \;\mathbb {Z} /{p_{3}^{k_{3}}}\mathbb {Z} \dots \;\;}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mo>≅</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <msubsup> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mrow> </msubsup> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mspace width="thickmathspace" /> <mo>×</mo> <mspace width="thickmathspace" /> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <msubsup> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mrow> </msubsup> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mspace width="thickmathspace" /> <mo>×</mo> <mspace width="thickmathspace" /> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <msubsup> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> </mrow> </msubsup> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mo>…</mo> <mspace width="thickmathspace" /> <mspace width="thickmathspace" /> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} /n\mathbb {Z} \cong \mathbb {Z} /{p_{1}^{k_{1}}}\mathbb {Z} \;\times \;\mathbb {Z} /{p_{2}^{k_{2}}}\mathbb {Z} \;\times \;\mathbb {Z} /{p_{3}^{k_{3}}}\mathbb {Z} \dots \;\;}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2d56fd814626ebefe2d5c1705cb47ad7489e85e2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:43.477ex; height:3.509ex;" alt="{\displaystyle \mathbb {Z} /n\mathbb {Z} \cong \mathbb {Z} /{p_{1}^{k_{1}}}\mathbb {Z} \;\times \;\mathbb {Z} /{p_{2}^{k_{2}}}\mathbb {Z} \;\times \;\mathbb {Z} /{p_{3}^{k_{3}}}\mathbb {Z} \dots \;\;}"></span></dd></dl> <p>Similarly, the group of units <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>×</mo> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bffe12a165220346c352fd4839b7c35dbaa08eb0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.978ex; height:2.843ex;" alt="{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}"></span> is the direct product of the groups corresponding to each of the prime power factors: </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }\cong (\mathbb {Z} /{p_{1}^{k_{1}}}\mathbb {Z} )^{\times }\times (\mathbb {Z} /{p_{2}^{k_{2}}}\mathbb {Z} )^{\times }\times (\mathbb {Z} /{p_{3}^{k_{3}}}\mathbb {Z} )^{\times }\dots \;.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>×</mo> </mrow> </msup> <mo>≅</mo> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <msubsup> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mrow> </msubsup> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>×</mo> </mrow> </msup> <mo>×</mo> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <msubsup> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mrow> </msubsup> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>×</mo> </mrow> </msup> <mo>×</mo> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <msubsup> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> </mrow> </msubsup> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>×</mo> </mrow> </msup> <mo>…</mo> <mspace width="thickmathspace" /> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }\cong (\mathbb {Z} /{p_{1}^{k_{1}}}\mathbb {Z} )^{\times }\times (\mathbb {Z} /{p_{2}^{k_{2}}}\mathbb {Z} )^{\times }\times (\mathbb {Z} /{p_{3}^{k_{3}}}\mathbb {Z} )^{\times }\dots \;.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e052e70cbdbbb58570bf74664055fc6fba49941d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:54.565ex; height:3.509ex;" alt="{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }\cong (\mathbb {Z} /{p_{1}^{k_{1}}}\mathbb {Z} )^{\times }\times (\mathbb {Z} /{p_{2}^{k_{2}}}\mathbb {Z} )^{\times }\times (\mathbb {Z} /{p_{3}^{k_{3}}}\mathbb {Z} )^{\times }\dots \;.}"></span></dd></dl> <p>For each odd prime power <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p^{k}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle p^{k}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e017c102135ab13bdf501dc1c1b5fd1840a97822" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.348ex; height:3.009ex;" alt="{\displaystyle p^{k}}"></span> the corresponding factor <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\mathbb {Z} /{p^{k}}\mathbb {Z} )^{\times }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <msup> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msup> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>×</mo> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (\mathbb {Z} /{p^{k}}\mathbb {Z} )^{\times }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a72b5d8f9c41be9d8c939fedce44dc0935849e74" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.841ex; height:3.176ex;" alt="{\displaystyle (\mathbb {Z} /{p^{k}}\mathbb {Z} )^{\times }}"></span> is the cyclic group of order <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varphi (p^{k})=p^{k}-p^{k-1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>φ</mi> <mo stretchy="false">(</mo> <msup> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msup> <mo stretchy="false">)</mo> <mo>=</mo> <msup> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msup> <mo>−</mo> <msup> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> <mo>−</mo> <mn>1</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \varphi (p^{k})=p^{k}-p^{k-1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/18a95c01ca56a0031cf111adb484df54253dea0d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.143ex; height:3.176ex;" alt="{\displaystyle \varphi (p^{k})=p^{k}-p^{k-1}}"></span>, which may further factor into cyclic groups of prime-power orders. For powers of 2 the factor <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\mathbb {Z} /{2^{k}}\mathbb {Z} )^{\times }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msup> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>×</mo> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (\mathbb {Z} /{2^{k}}\mathbb {Z} )^{\times }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/70afdc11bbe9e68411afdad0ab9b493aa4f60ecf" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.834ex; height:3.176ex;" alt="{\displaystyle (\mathbb {Z} /{2^{k}}\mathbb {Z} )^{\times }}"></span> is not cyclic unless <i>k</i> = 0, 1, 2, but factors into cyclic groups as described above. </p><p>The order of the group <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varphi (n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>φ</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \varphi (n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f067864064667dd5f8b2508b9cbf983d89788629" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.724ex; height:2.843ex;" alt="{\displaystyle \varphi (n)}"></span> is the product of the orders of the cyclic groups in the direct product. The <a href="/wiki/Exponent_of_a_group" class="mw-redirect" title="Exponent of a group">exponent</a> of the group, that is, the <a href="/wiki/Least_common_multiple" title="Least common multiple">least common multiple</a> of the orders in the cyclic groups, is given by the <a href="/wiki/Carmichael_function" title="Carmichael function">Carmichael function</a> <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda (n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>λ</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \lambda (n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8f06b26d7cb84392c1891a14c32c4dbe7e3f5e92" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.559ex; height:2.843ex;" alt="{\displaystyle \lambda (n)}"></span> (sequence <span class="nowrap external"><a href="//oeis.org/A002322" class="extiw" title="oeis:A002322">A002322</a></span> in the <a href="/wiki/On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>). In other words, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda (n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>λ</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \lambda (n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8f06b26d7cb84392c1891a14c32c4dbe7e3f5e92" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.559ex; height:2.843ex;" alt="{\displaystyle \lambda (n)}"></span> is the smallest number such that for each <i>a</i> coprime to <i>n</i>, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>λ</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </msup> <mo>≡</mo> <mn>1</mn> <mrow class="MJX-TeXAtom-ORD"> <mspace width="1em" /> <mo stretchy="false">(</mo> <mi>mod</mi> <mspace width="0.333em" /> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2e475506bcb72caae57599e0ccafa7efe023be9c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.026ex; height:3.343ex;" alt="{\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}}"></span> holds. It divides <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varphi (n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>φ</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \varphi (n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f067864064667dd5f8b2508b9cbf983d89788629" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.724ex; height:2.843ex;" alt="{\displaystyle \varphi (n)}"></span> and is equal to it if and only if the group is cyclic. </p> <div class="mw-heading mw-heading2"><h2 id="Subgroup_of_false_witnesses">Subgroup of false witnesses</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Multiplicative_group_of_integers_modulo_n&action=edit&section=7" title="Edit section: Subgroup of false witnesses"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>If <i>n</i> is composite, there exists a possibly proper subgroup of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} _{n}^{\times }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msubsup> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>×</mo> </mrow> </msubsup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} _{n}^{\times }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0fd1e30bc8d1c3de92bffc56c63e5370a52d640a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.061ex; height:2.843ex;" alt="{\displaystyle \mathbb {Z} _{n}^{\times }}"></span>, called the "group of false witnesses", comprising the solutions of the equation <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{n-1}=1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo>=</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x^{n-1}=1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/842b8ccb85799624ce1dba91e9618cca26488abf" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.91ex; height:2.676ex;" alt="{\displaystyle x^{n-1}=1}"></span>, the elements which, raised to the power <span class="nowrap"><i>n</i> − 1</span>, are congruent to 1 modulo <i>n</i>.<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> <a href="/wiki/Fermat%27s_Little_Theorem" class="mw-redirect" title="Fermat's Little Theorem">Fermat's Little Theorem</a> states that for <i>n = p</i> a prime, this group consists of all <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in \mathbb {Z} _{p}^{\times }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> <mo>∈</mo> <msubsup> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>p</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>×</mo> </mrow> </msubsup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x\in \mathbb {Z} _{p}^{\times }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/36207d9e1a4ee733ef2bd22c32809e82f0e12e1f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:7.231ex; height:3.176ex;" alt="{\displaystyle x\in \mathbb {Z} _{p}^{\times }}"></span>; thus for <i>n</i> composite, such residues <i>x</i> are "false positives" or "false witnesses" for the primality of <i>n</i>. The number <i>x =</i> 2 is most often used in this basic primality check, and <i>n =</i> <span class="nowrap">341 = 11 × 31</span> is notable since <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{341-1}\equiv 1\mod 341}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>341</mn> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo>≡</mo> <mn>1</mn> <mspace width="1em" /> <mi>mod</mi> <mspace width="thinmathspace" /> <mspace width="thinmathspace" /> <mn>341</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 2^{341-1}\equiv 1\mod 341}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/615bd9b4d37a21e94846a52ddc562fe554b3924b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:21.971ex; height:2.676ex;" alt="{\displaystyle 2^{341-1}\equiv 1\mod 341}"></span>, and <i>n =</i> 341 is the smallest composite number for which <i>x =</i> 2 is a false witness to primality. In fact, the false witnesses subgroup for 341 contains 100 elements, and is of index 3 inside the 300-element group <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} _{341}^{\times }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msubsup> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>341</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>×</mo> </mrow> </msubsup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} _{341}^{\times }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6baaf39046f2294303f1ae6a4f498e0743423dc1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.249ex; height:2.843ex;" alt="{\displaystyle \mathbb {Z} _{341}^{\times }}"></span>. </p> <div class="mw-heading mw-heading3"><h3 id="Examples">Examples</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Multiplicative_group_of_integers_modulo_n&action=edit&section=8" title="Edit section: Examples"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading4"><h4 id="n_=_9"><span id="n_.3D_9"></span><i>n</i> = 9</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Multiplicative_group_of_integers_modulo_n&action=edit&section=9" title="Edit section: n = 9"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The smallest example with a nontrivial subgroup of false witnesses is <span class="nowrap">9 = 3 × 3</span>. There are 6 residues coprime to 9: 1, 2, 4, 5, 7, 8. Since 8 is congruent to <span class="nowrap">−1 modulo 9</span>, it follows that 8<sup>8</sup> is congruent to 1 modulo 9. So 1 and 8 are false positives for the "primality" of 9 (since 9 is not actually prime). These are in fact the only ones, so the subgroup {1,8} is the subgroup of false witnesses. The same argument shows that <span class="nowrap"><i>n</i> − 1</span> is a "false witness" for any odd composite <i>n</i>. </p> <div class="mw-heading mw-heading4"><h4 id="n_=_91"><span id="n_.3D_91"></span><i>n</i> = 91</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Multiplicative_group_of_integers_modulo_n&action=edit&section=10" title="Edit section: n = 91"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>For <i>n</i> = 91 (= 7 × 13), there are <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varphi (91)=72}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>φ</mi> <mo stretchy="false">(</mo> <mn>91</mn> <mo stretchy="false">)</mo> <mo>=</mo> <mn>72</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \varphi (91)=72}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c1c115215565120a2acd360867139cb8ab1249cb" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.078ex; height:2.843ex;" alt="{\displaystyle \varphi (91)=72}"></span> residues coprime to 91, half of them (i.e., 36 of them) are false witnesses of 91, namely 1, 3, 4, 9, 10, 12, 16, 17, 22, 23, 25, 27, 29, 30, 36, 38, 40, 43, 48, 51, 53, 55, 61, 62, 64, 66, 68, 69, 74, 75, 79, 81, 82, 87, 88, and 90, since for these values of <i>x</i>, <i>x</i><sup>90</sup> is congruent to 1 mod 91. </p> <div class="mw-heading mw-heading4"><h4 id="n_=_561"><span id="n_.3D_561"></span><i>n</i> = 561</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Multiplicative_group_of_integers_modulo_n&action=edit&section=11" title="Edit section: n = 561"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p><i>n</i> = 561 (= 3 × 11 × 17) is a <a href="/wiki/Carmichael_number" title="Carmichael number">Carmichael number</a>, thus <i>s</i><sup>560</sup> is congruent to 1 modulo 561 for any integer <i>s</i> coprime to 561. The subgroup of false witnesses is, in this case, not proper; it is the entire group of multiplicative units modulo 561, which consists of 320 residues. </p> <div class="mw-heading mw-heading2"><h2 id="Examples_2">Examples</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Multiplicative_group_of_integers_modulo_n&action=edit&section=12" title="Edit section: Examples"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>This table shows the cyclic decomposition of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>×</mo> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bffe12a165220346c352fd4839b7c35dbaa08eb0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.978ex; height:2.843ex;" alt="{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}"></span> and a <a href="/wiki/Generating_set_of_a_group" title="Generating set of a group">generating set</a> for <i>n</i> ≤ 128. The decomposition and generating sets are not unique; for example, </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \displaystyle {\begin{aligned}(\mathbb {Z} /35\mathbb {Z} )^{\times }&\cong (\mathbb {Z} /5\mathbb {Z} )^{\times }\times (\mathbb {Z} /7\mathbb {Z} )^{\times }\cong \mathrm {C} _{4}\times \mathrm {C} _{6}\cong \mathrm {C} _{4}\times \mathrm {C} _{2}\times \mathrm {C} _{3}\cong \mathrm {C} _{2}\times \mathrm {C} _{12}\cong (\mathbb {Z} /4\mathbb {Z} )^{\times }\times (\mathbb {Z} /13\mathbb {Z} )^{\times }\\&\cong (\mathbb {Z} /52\mathbb {Z} )^{\times }\end{aligned}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mtable columnalign="right left right left right left right left right left right left" rowspacing="3pt" columnspacing="0em 2em 0em 2em 0em 2em 0em 2em 0em 2em 0em" displaystyle="true"> <mtr> <mtd> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>35</mn> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>×</mo> </mrow> </msup> </mtd> <mtd> <mi></mi> <mo>≅</mo> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>5</mn> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>×</mo> </mrow> </msup> <mo>×</mo> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>7</mn> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>×</mo> </mrow> </msup> <mo>≅</mo> <msub> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">C</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>4</mn> </mrow> </msub> <mo>×</mo> <msub> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">C</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>6</mn> </mrow> </msub> <mo>≅</mo> <msub> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">C</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>4</mn> </mrow> </msub> <mo>×</mo> <msub> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">C</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>×</mo> <msub> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">C</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo>≅</mo> <msub> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">C</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>×</mo> <msub> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">C</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>12</mn> </mrow> </msub> <mo>≅</mo> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>4</mn> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>×</mo> </mrow> </msup> <mo>×</mo> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>13</mn> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>×</mo> </mrow> </msup> </mtd> </mtr> <mtr> <mtd /> <mtd> <mi></mi> <mo>≅</mo> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>52</mn> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>×</mo> </mrow> </msup> </mtd> </mtr> </mtable> </mrow> </mstyle> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \displaystyle {\begin{aligned}(\mathbb {Z} /35\mathbb {Z} )^{\times }&\cong (\mathbb {Z} /5\mathbb {Z} )^{\times }\times (\mathbb {Z} /7\mathbb {Z} )^{\times }\cong \mathrm {C} _{4}\times \mathrm {C} _{6}\cong \mathrm {C} _{4}\times \mathrm {C} _{2}\times \mathrm {C} _{3}\cong \mathrm {C} _{2}\times \mathrm {C} _{12}\cong (\mathbb {Z} /4\mathbb {Z} )^{\times }\times (\mathbb {Z} /13\mathbb {Z} )^{\times }\\&\cong (\mathbb {Z} /52\mathbb {Z} )^{\times }\end{aligned}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/28c2a11fd904d332f1381a502e58f897b8e3717a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:99.288ex; height:6.176ex;" alt="{\displaystyle \displaystyle {\begin{aligned}(\mathbb {Z} /35\mathbb {Z} )^{\times }&\cong (\mathbb {Z} /5\mathbb {Z} )^{\times }\times (\mathbb {Z} /7\mathbb {Z} )^{\times }\cong \mathrm {C} _{4}\times \mathrm {C} _{6}\cong \mathrm {C} _{4}\times \mathrm {C} _{2}\times \mathrm {C} _{3}\cong \mathrm {C} _{2}\times \mathrm {C} _{12}\cong (\mathbb {Z} /4\mathbb {Z} )^{\times }\times (\mathbb {Z} /13\mathbb {Z} )^{\times }\\&\cong (\mathbb {Z} /52\mathbb {Z} )^{\times }\end{aligned}}}"></span> </p><p>(but <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \not \cong \mathrm {C} _{24}\cong \mathrm {C} _{8}\times \mathrm {C} _{3}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo>≇</mo> <msub> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">C</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>24</mn> </mrow> </msub> <mo>≅</mo> <msub> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">C</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>8</mn> </mrow> </msub> <mo>×</mo> <msub> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">C</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \not \cong \mathrm {C} _{24}\cong \mathrm {C} _{8}\times \mathrm {C} _{3}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fcc724ab4dcbd3c94a9f327667c408b5d0f2c442" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:17.411ex; height:2.509ex;" alt="{\displaystyle \not \cong \mathrm {C} _{24}\cong \mathrm {C} _{8}\times \mathrm {C} _{3}}"></span>). The table below lists the shortest decomposition (among those, the lexicographically first is chosen – this guarantees isomorphic groups are listed with the same decompositions). The generating set is also chosen to be as short as possible, and for <i>n</i> with primitive root, the smallest primitive root modulo <i>n</i> is listed. </p><p>For example, take <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\mathbb {Z} /20\mathbb {Z} )^{\times }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>20</mn> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>×</mo> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (\mathbb {Z} /20\mathbb {Z} )^{\times }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7d3b689cf39e6f188bd3bbba42d32ff64f5d4ce1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.908ex; height:2.843ex;" alt="{\displaystyle (\mathbb {Z} /20\mathbb {Z} )^{\times }}"></span>. Then <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varphi (20)=8}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>φ</mi> <mo stretchy="false">(</mo> <mn>20</mn> <mo stretchy="false">)</mo> <mo>=</mo> <mn>8</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \varphi (20)=8}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0da447e619c91b9a7c74666c1b1fa96a85a96913" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.915ex; height:2.843ex;" alt="{\displaystyle \varphi (20)=8}"></span> means that the order of the group is 8 (i.e., there are 8 numbers less than 20 and coprime to it); <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda (20)=4}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>λ</mi> <mo stretchy="false">(</mo> <mn>20</mn> <mo stretchy="false">)</mo> <mo>=</mo> <mn>4</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \lambda (20)=4}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ef94b10e6d0772347d1aea2bdc9a648ba4b55f19" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.75ex; height:2.843ex;" alt="{\displaystyle \lambda (20)=4}"></span> means the order of each element divides 4, that is, the fourth power of any number coprime to 20 is congruent to 1 (mod 20). The set {3,19} generates the group, which means that every element of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\mathbb {Z} /20\mathbb {Z} )^{\times }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>20</mn> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>×</mo> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (\mathbb {Z} /20\mathbb {Z} )^{\times }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7d3b689cf39e6f188bd3bbba42d32ff64f5d4ce1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.908ex; height:2.843ex;" alt="{\displaystyle (\mathbb {Z} /20\mathbb {Z} )^{\times }}"></span> is of the form <span class="nowrap">3<sup><i>a</i></sup> × 19<sup><i>b</i></sup></span> (where <i>a</i> is 0, 1, 2, or 3, because the element 3 has order 4, and similarly <i>b</i> is 0 or 1, because the element 19 has order 2). </p><p>Smallest primitive root mod <i>n</i> are (0 if no root exists) </p> <dl><dd>0, 1, 2, 3, 2, 5, 3, 0, 2, 3, 2, 0, 2, 3, 0, 0, 3, 5, 2, 0, 0, 7, 5, 0, 2, 7, 2, 0, 2, 0, 3, 0, 0, 3, 0, 0, 2, 3, 0, 0, 6, 0, 3, 0, 0, 5, 5, 0, 3, 3, 0, 0, 2, 5, 0, 0, 0, 3, 2, 0, 2, 3, 0, 0, 0, 0, 2, 0, 0, 0, 7, 0, 5, 5, 0, 0, 0, 0, 3, 0, 2, 7, 2, 0, 0, 3, 0, 0, 3, 0, ... (sequence <span class="nowrap external"><a href="//oeis.org/A046145" class="extiw" title="oeis:A046145">A046145</a></span> in the <a href="/wiki/On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>)</dd></dl> <p>Numbers of the elements in a minimal generating set of mod <i>n</i> are </p> <dl><dd>1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 1, 2, 2, 1, 1, 3, 1, 1, 1, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 3, 1, 2, 1, 2, 2, 1, 1, 3, 1, 1, 2, 2, 1, 1, 2, 3, 2, 1, 1, 3, 1, 1, 2, 2, 2, 2, 1, 2, 2, 2, 1, 3, 1, 1, 2, 2, 2, 2, 1, 3, 1, 1, 1, 3, 2, 1, 2, 3, 1, 2, ... (sequence <span class="nowrap external"><a href="//oeis.org/A046072" class="extiw" title="oeis:A046072">A046072</a></span> in the <a href="/wiki/On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>)</dd></dl> <div style="overflow:auto"> <table class="wikitable" style="text-align:center" cellpadding="2"> <caption>Group structure of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>×</mo> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bffe12a165220346c352fd4839b7c35dbaa08eb0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.978ex; height:2.843ex;" alt="{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}"></span> </caption> <tbody><tr> <th><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\;}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mspace width="thickmathspace" /> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n\;}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/60862463d06e48ec9a2fc5de5f9eb7895611fe03" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle n\;}"></span></th> <th><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>×</mo> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bffe12a165220346c352fd4839b7c35dbaa08eb0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.978ex; height:2.843ex;" alt="{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}"></span></th> <th><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varphi (n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>φ</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \varphi (n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f067864064667dd5f8b2508b9cbf983d89788629" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.724ex; height:2.843ex;" alt="{\displaystyle \varphi (n)}"></span></th> <th><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda (n)\;}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>λ</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mspace width="thickmathspace" /> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \lambda (n)\;}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9141ccf338dc2551525e425851347a0e2aaee536" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.204ex; height:2.843ex;" alt="{\displaystyle \lambda (n)\;}"></span></th> <th>Generating set </th> <td width="25" rowspan="33">  </td> <th><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\;}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mspace width="thickmathspace" /> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n\;}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/60862463d06e48ec9a2fc5de5f9eb7895611fe03" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle n\;}"></span></th> <th><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>×</mo> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bffe12a165220346c352fd4839b7c35dbaa08eb0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.978ex; height:2.843ex;" alt="{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}"></span></th> <th><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varphi (n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>φ</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \varphi (n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f067864064667dd5f8b2508b9cbf983d89788629" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.724ex; height:2.843ex;" alt="{\displaystyle \varphi (n)}"></span></th> <th><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda (n)\;}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>λ</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mspace width="thickmathspace" /> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \lambda (n)\;}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9141ccf338dc2551525e425851347a0e2aaee536" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.204ex; height:2.843ex;" alt="{\displaystyle \lambda (n)\;}"></span></th> <th>Generating set </th> <td width="25" rowspan="33">  </td> <th><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\;}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mspace width="thickmathspace" /> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n\;}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/60862463d06e48ec9a2fc5de5f9eb7895611fe03" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle n\;}"></span></th> <th><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>×</mo> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bffe12a165220346c352fd4839b7c35dbaa08eb0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.978ex; height:2.843ex;" alt="{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}"></span></th> <th><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varphi (n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>φ</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \varphi (n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f067864064667dd5f8b2508b9cbf983d89788629" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.724ex; height:2.843ex;" alt="{\displaystyle \varphi (n)}"></span></th> <th><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda (n)\;}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>λ</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mspace width="thickmathspace" /> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \lambda (n)\;}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9141ccf338dc2551525e425851347a0e2aaee536" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.204ex; height:2.843ex;" alt="{\displaystyle \lambda (n)\;}"></span></th> <th>Generating set </th> <td width="25" rowspan="33">  </td> <th><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\;}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mspace width="thickmathspace" /> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n\;}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/60862463d06e48ec9a2fc5de5f9eb7895611fe03" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle n\;}"></span></th> <th><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>×</mo> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bffe12a165220346c352fd4839b7c35dbaa08eb0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.978ex; height:2.843ex;" alt="{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}"></span></th> <th><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varphi (n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>φ</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \varphi (n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f067864064667dd5f8b2508b9cbf983d89788629" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.724ex; height:2.843ex;" alt="{\displaystyle \varphi (n)}"></span></th> <th><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda (n)\;}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>λ</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mspace width="thickmathspace" /> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \lambda (n)\;}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9141ccf338dc2551525e425851347a0e2aaee536" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.204ex; height:2.843ex;" alt="{\displaystyle \lambda (n)\;}"></span></th> <th>Generating set </th></tr> <tr> <th>1 </th> <td>C<sub>1</sub></td> <td>1</td> <td>1</td> <td>0 </td> <th>33 </th> <td>C<sub>2</sub>×C<sub>10</sub></td> <td>20</td> <td>10</td> <td>2, 10 </td> <th>65 </th> <td>C<sub>4</sub>×C<sub>12</sub></td> <td>48</td> <td>12</td> <td>2, 12 </td> <th>97 </th> <td>C<sub>96</sub></td> <td>96</td> <td>96</td> <td>5 </td></tr> <tr> <th>2 </th> <td>C<sub>1</sub></td> <td>1</td> <td>1</td> <td>1 </td> <th>34 </th> <td>C<sub>16</sub></td> <td>16</td> <td>16</td> <td>3 </td> <th>66 </th> <td>C<sub>2</sub>×C<sub>10</sub></td> <td>20</td> <td>10</td> <td>5, 7 </td> <th>98 </th> <td>C<sub>42</sub></td> <td>42</td> <td>42</td> <td>3 </td></tr> <tr> <th>3 </th> <td>C<sub>2</sub></td> <td>2</td> <td>2</td> <td>2 </td> <th>35 </th> <td>C<sub>2</sub>×C<sub>12</sub></td> <td>24</td> <td>12</td> <td>2, 6 </td> <th>67 </th> <td>C<sub>66</sub></td> <td>66</td> <td>66</td> <td>2 </td> <th>99 </th> <td>C<sub>2</sub>×C<sub>30</sub></td> <td>60</td> <td>30</td> <td>2, 5 </td></tr> <tr> <th>4 </th> <td>C<sub>2</sub></td> <td>2</td> <td>2</td> <td>3 </td> <th>36 </th> <td>C<sub>2</sub>×C<sub>6</sub></td> <td>12</td> <td>6</td> <td>5, 19 </td> <th>68 </th> <td>C<sub>2</sub>×C<sub>16</sub></td> <td>32</td> <td>16</td> <td>3, 67 </td> <th>100 </th> <td>C<sub>2</sub>×C<sub>20</sub></td> <td>40</td> <td>20</td> <td>3, 99 </td></tr> <tr> <th>5 </th> <td>C<sub>4</sub></td> <td>4</td> <td>4</td> <td>2 </td> <th>37 </th> <td>C<sub>36</sub></td> <td>36</td> <td>36</td> <td>2 </td> <th>69 </th> <td>C<sub>2</sub>×C<sub>22</sub></td> <td>44</td> <td>22</td> <td>2, 68 </td> <th>101 </th> <td>C<sub>100</sub></td> <td>100</td> <td>100</td> <td>2 </td></tr> <tr> <th>6 </th> <td>C<sub>2</sub></td> <td>2</td> <td>2</td> <td>5 </td> <th>38 </th> <td>C<sub>18</sub></td> <td>18</td> <td>18</td> <td>3 </td> <th>70 </th> <td>C<sub>2</sub>×C<sub>12</sub></td> <td>24</td> <td>12</td> <td>3, 69 </td> <th>102 </th> <td>C<sub>2</sub>×C<sub>16</sub></td> <td>32</td> <td>16</td> <td>5, 101 </td></tr> <tr> <th>7 </th> <td>C<sub>6</sub></td> <td>6</td> <td>6</td> <td>3 </td> <th>39 </th> <td>C<sub>2</sub>×C<sub>12</sub></td> <td>24</td> <td>12</td> <td>2, 38 </td> <th>71 </th> <td>C<sub>70</sub></td> <td>70</td> <td>70</td> <td>7 </td> <th>103 </th> <td>C<sub>102</sub></td> <td>102</td> <td>102</td> <td>5 </td></tr> <tr> <th>8 </th> <td>C<sub>2</sub>×C<sub>2</sub></td> <td>4</td> <td>2</td> <td>3, 5 </td> <th>40 </th> <td>C<sub>2</sub>×C<sub>2</sub>×C<sub>4</sub></td> <td>16</td> <td>4</td> <td>3, 11, 39 </td> <th>72 </th> <td>C<sub>2</sub>×C<sub>2</sub>×C<sub>6</sub></td> <td>24</td> <td>6</td> <td>5, 17, 19 </td> <th>104 </th> <td>C<sub>2</sub>×C<sub>2</sub>×C<sub>12</sub></td> <td>48</td> <td>12</td> <td>3, 5, 103 </td></tr> <tr> <th>9 </th> <td>C<sub>6</sub></td> <td>6</td> <td>6</td> <td>2 </td> <th>41 </th> <td>C<sub>40</sub></td> <td>40</td> <td>40</td> <td>6 </td> <th>73 </th> <td>C<sub>72</sub></td> <td>72</td> <td>72</td> <td>5 </td> <th>105 </th> <td>C<sub>2</sub>×C<sub>2</sub>×C<sub>12</sub></td> <td>48</td> <td>12</td> <td>2, 29, 41 </td></tr> <tr> <th>10 </th> <td>C<sub>4</sub></td> <td>4</td> <td>4</td> <td>3 </td> <th>42 </th> <td>C<sub>2</sub>×C<sub>6</sub></td> <td>12</td> <td>6</td> <td>5, 13 </td> <th>74 </th> <td>C<sub>36</sub></td> <td>36</td> <td>36</td> <td>5 </td> <th>106 </th> <td>C<sub>52</sub></td> <td>52</td> <td>52</td> <td>3 </td></tr> <tr> <th>11 </th> <td>C<sub>10</sub></td> <td>10</td> <td>10</td> <td>2 </td> <th>43 </th> <td>C<sub>42</sub></td> <td>42</td> <td>42</td> <td>3 </td> <th>75 </th> <td>C<sub>2</sub>×C<sub>20</sub></td> <td>40</td> <td>20</td> <td>2, 74 </td> <th>107 </th> <td>C<sub>106</sub></td> <td>106</td> <td>106</td> <td>2 </td></tr> <tr> <th>12 </th> <td>C<sub>2</sub>×C<sub>2</sub></td> <td>4</td> <td>2</td> <td>5, 7 </td> <th>44 </th> <td>C<sub>2</sub>×C<sub>10</sub></td> <td>20</td> <td>10</td> <td>3, 43 </td> <th>76 </th> <td>C<sub>2</sub>×C<sub>18</sub></td> <td>36</td> <td>18</td> <td>3, 37 </td> <th>108 </th> <td>C<sub>2</sub>×C<sub>18</sub></td> <td>36</td> <td>18</td> <td>5, 107 </td></tr> <tr> <th>13 </th> <td>C<sub>12</sub></td> <td>12</td> <td>12</td> <td>2 </td> <th>45 </th> <td>C<sub>2</sub>×C<sub>12</sub></td> <td>24</td> <td>12</td> <td>2, 44 </td> <th>77 </th> <td>C<sub>2</sub>×C<sub>30</sub></td> <td>60</td> <td>30</td> <td>2, 76 </td> <th>109 </th> <td>C<sub>108</sub></td> <td>108</td> <td>108</td> <td>6 </td></tr> <tr> <th>14 </th> <td>C<sub>6</sub></td> <td>6</td> <td>6</td> <td>3 </td> <th>46 </th> <td>C<sub>22</sub></td> <td>22</td> <td>22</td> <td>5 </td> <th>78 </th> <td>C<sub>2</sub>×C<sub>12</sub></td> <td>24</td> <td>12</td> <td>5, 7 </td> <th>110 </th> <td>C<sub>2</sub>×C<sub>20</sub></td> <td>40</td> <td>20</td> <td>3, 109 </td></tr> <tr> <th>15 </th> <td>C<sub>2</sub>×C<sub>4</sub></td> <td>8</td> <td>4</td> <td>2, 14 </td> <th>47 </th> <td>C<sub>46</sub></td> <td>46</td> <td>46</td> <td>5 </td> <th>79 </th> <td>C<sub>78</sub></td> <td>78</td> <td>78</td> <td>3 </td> <th>111 </th> <td>C<sub>2</sub>×C<sub>36</sub></td> <td>72</td> <td>36</td> <td>2, 110 </td></tr> <tr> <th>16 </th> <td>C<sub>2</sub>×C<sub>4</sub></td> <td>8</td> <td>4</td> <td>3, 15 </td> <th>48 </th> <td>C<sub>2</sub>×C<sub>2</sub>×C<sub>4</sub></td> <td>16</td> <td>4</td> <td>5, 7, 47 </td> <th>80 </th> <td>C<sub>2</sub>×C<sub>4</sub>×C<sub>4</sub></td> <td>32</td> <td>4</td> <td>3, 7, 79 </td> <th>112 </th> <td>C<sub>2</sub>×C<sub>2</sub>×C<sub>12</sub></td> <td>48</td> <td>12</td> <td>3, 5, 111 </td></tr> <tr> <th>17 </th> <td>C<sub>16</sub></td> <td>16</td> <td>16</td> <td>3 </td> <th>49 </th> <td>C<sub>42</sub></td> <td>42</td> <td>42</td> <td>3 </td> <th>81 </th> <td>C<sub>54</sub></td> <td>54</td> <td>54</td> <td>2 </td> <th>113 </th> <td>C<sub>112</sub></td> <td>112</td> <td>112</td> <td>3 </td></tr> <tr> <th>18 </th> <td>C<sub>6</sub></td> <td>6</td> <td>6</td> <td>5 </td> <th>50 </th> <td>C<sub>20</sub></td> <td>20</td> <td>20</td> <td>3 </td> <th>82 </th> <td>C<sub>40</sub></td> <td>40</td> <td>40</td> <td>7 </td> <th>114 </th> <td>C<sub>2</sub>×C<sub>18</sub></td> <td>36</td> <td>18</td> <td>5, 37 </td></tr> <tr> <th>19 </th> <td>C<sub>18</sub></td> <td>18</td> <td>18</td> <td>2 </td> <th>51 </th> <td>C<sub>2</sub>×C<sub>16</sub></td> <td>32</td> <td>16</td> <td>5, 50 </td> <th>83 </th> <td>C<sub>82</sub></td> <td>82</td> <td>82</td> <td>2 </td> <th>115 </th> <td>C<sub>2</sub>×C<sub>44</sub></td> <td>88</td> <td>44</td> <td>2, 114 </td></tr> <tr> <th>20 </th> <td>C<sub>2</sub>×C<sub>4</sub></td> <td>8</td> <td>4</td> <td>3, 19 </td> <th>52 </th> <td>C<sub>2</sub>×C<sub>12</sub></td> <td>24</td> <td>12</td> <td>7, 51 </td> <th>84 </th> <td>C<sub>2</sub>×C<sub>2</sub>×C<sub>6</sub></td> <td>24</td> <td>6</td> <td>5, 11, 13 </td> <th>116 </th> <td>C<sub>2</sub>×C<sub>28</sub></td> <td>56</td> <td>28</td> <td>3, 115 </td></tr> <tr> <th>21 </th> <td>C<sub>2</sub>×C<sub>6</sub></td> <td>12</td> <td>6</td> <td>2, 20 </td> <th>53 </th> <td>C<sub>52</sub></td> <td>52</td> <td>52</td> <td>2 </td> <th>85 </th> <td>C<sub>4</sub>×C<sub>16</sub></td> <td>64</td> <td>16</td> <td>2, 3 </td> <th>117 </th> <td>C<sub>6</sub>×C<sub>12</sub></td> <td>72</td> <td>12</td> <td>2, 17 </td></tr> <tr> <th>22 </th> <td>C<sub>10</sub></td> <td>10</td> <td>10</td> <td>7 </td> <th>54 </th> <td>C<sub>18</sub></td> <td>18</td> <td>18</td> <td>5 </td> <th>86 </th> <td>C<sub>42</sub></td> <td>42</td> <td>42</td> <td>3 </td> <th>118 </th> <td>C<sub>58</sub></td> <td>58</td> <td>58</td> <td>11 </td></tr> <tr> <th>23 </th> <td>C<sub>22</sub></td> <td>22</td> <td>22</td> <td>5 </td> <th>55 </th> <td>C<sub>2</sub>×C<sub>20</sub></td> <td>40</td> <td>20</td> <td>2, 21 </td> <th>87 </th> <td>C<sub>2</sub>×C<sub>28</sub></td> <td>56</td> <td>28</td> <td>2, 86 </td> <th>119 </th> <td>C<sub>2</sub>×C<sub>48</sub></td> <td>96</td> <td>48</td> <td>3, 118 </td></tr> <tr> <th>24 </th> <td>C<sub>2</sub>×C<sub>2</sub>×C<sub>2</sub></td> <td>8</td> <td>2</td> <td>5, 7, 13 </td> <th>56 </th> <td>C<sub>2</sub>×C<sub>2</sub>×C<sub>6</sub></td> <td>24</td> <td>6</td> <td>3, 13, 29 </td> <th>88 </th> <td>C<sub>2</sub>×C<sub>2</sub>×C<sub>10</sub></td> <td>40</td> <td>10</td> <td>3, 5, 7 </td> <th>120 </th> <td>C<sub>2</sub>×C<sub>2</sub>×C<sub>2</sub>×C<sub>4</sub></td> <td>32</td> <td>4</td> <td>7, 11, 19, 29 </td></tr> <tr> <th>25 </th> <td>C<sub>20</sub></td> <td>20</td> <td>20</td> <td>2 </td> <th>57 </th> <td>C<sub>2</sub>×C<sub>18</sub></td> <td>36</td> <td>18</td> <td>2, 20 </td> <th>89 </th> <td>C<sub>88</sub></td> <td>88</td> <td>88</td> <td>3 </td> <th>121 </th> <td>C<sub>110</sub></td> <td>110</td> <td>110</td> <td>2 </td></tr> <tr> <th>26 </th> <td>C<sub>12</sub></td> <td>12</td> <td>12</td> <td>7 </td> <th>58 </th> <td>C<sub>28</sub></td> <td>28</td> <td>28</td> <td>3 </td> <th>90 </th> <td>C<sub>2</sub>×C<sub>12</sub></td> <td>24</td> <td>12</td> <td>7, 11 </td> <th>122 </th> <td>C<sub>60</sub></td> <td>60</td> <td>60</td> <td>7 </td></tr> <tr> <th>27 </th> <td>C<sub>18</sub></td> <td>18</td> <td>18</td> <td>2 </td> <th>59 </th> <td>C<sub>58</sub></td> <td>58</td> <td>58</td> <td>2 </td> <th>91 </th> <td>C<sub>6</sub>×C<sub>12</sub></td> <td>72</td> <td>12</td> <td>2, 3 </td> <th>123 </th> <td>C<sub>2</sub>×C<sub>40</sub></td> <td>80</td> <td>40</td> <td>7, 83 </td></tr> <tr> <th>28 </th> <td>C<sub>2</sub>×C<sub>6</sub></td> <td>12</td> <td>6</td> <td>3, 13 </td> <th>60 </th> <td>C<sub>2</sub>×C<sub>2</sub>×C<sub>4</sub></td> <td>16</td> <td>4</td> <td>7, 11, 19 </td> <th>92 </th> <td>C<sub>2</sub>×C<sub>22</sub></td> <td>44</td> <td>22</td> <td>3, 91 </td> <th>124 </th> <td>C<sub>2</sub>×C<sub>30</sub></td> <td>60</td> <td>30</td> <td>3, 61 </td></tr> <tr> <th>29 </th> <td>C<sub>28</sub></td> <td>28</td> <td>28</td> <td>2 </td> <th>61 </th> <td>C<sub>60</sub></td> <td>60</td> <td>60</td> <td>2 </td> <th>93 </th> <td>C<sub>2</sub>×C<sub>30</sub></td> <td>60</td> <td>30</td> <td>11, 61 </td> <th>125 </th> <td>C<sub>100</sub></td> <td>100</td> <td>100</td> <td>2 </td></tr> <tr> <th>30 </th> <td>C<sub>2</sub>×C<sub>4</sub></td> <td>8</td> <td>4</td> <td>7, 11 </td> <th>62 </th> <td>C<sub>30</sub></td> <td>30</td> <td>30</td> <td>3 </td> <th>94 </th> <td>C<sub>46</sub></td> <td>46</td> <td>46</td> <td>5 </td> <th>126 </th> <td>C<sub>6</sub>×C<sub>6</sub></td> <td>36</td> <td>6</td> <td>5, 13 </td></tr> <tr> <th>31 </th> <td>C<sub>30</sub></td> <td>30</td> <td>30</td> <td>3 </td> <th>63 </th> <td>C<sub>6</sub>×C<sub>6</sub></td> <td>36</td> <td>6</td> <td>2, 5 </td> <th>95 </th> <td>C<sub>2</sub>×C<sub>36</sub></td> <td>72</td> <td>36</td> <td>2, 94 </td> <th>127 </th> <td>C<sub>126</sub></td> <td>126</td> <td>126</td> <td>3 </td></tr> <tr> <th>32 </th> <td>C<sub>2</sub>×C<sub>8</sub></td> <td>16</td> <td>8</td> <td>3, 31 </td> <th>64 </th> <td>C<sub>2</sub>×C<sub>16</sub></td> <td>32</td> <td>16</td> <td>3, 63 </td> <th>96 </th> <td>C<sub>2</sub>×C<sub>2</sub>×C<sub>8</sub></td> <td>32</td> <td>8</td> <td>5, 17, 31 </td> <th>128 </th> <td>C<sub>2</sub>×C<sub>32</sub></td> <td>64</td> <td>32</td> <td>3, 127 </td></tr></tbody></table> </div> <div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Multiplicative_group_of_integers_modulo_n&action=edit&section=13" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Lenstra_elliptic_curve_factorization" class="mw-redirect" title="Lenstra elliptic curve factorization">Lenstra elliptic curve factorization</a></li></ul> <div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Multiplicative_group_of_integers_modulo_n&action=edit&section=14" title="Edit section: Notes"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1239543626">.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist"> <div class="mw-references-wrap"><ol class="references"> <li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text"><span class="citation mathworld" id="Reference-Mathworld-Modulo_Multiplication_Group"><style data-mw-deduplicate="TemplateStyles:r1238218222">.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}</style><cite id="CITEREFWeisstein" class="citation web cs1"><a href="/wiki/Eric_W._Weisstein" title="Eric W. Weisstein">Weisstein, Eric W.</a> <a rel="nofollow" class="external text" href="https://mathworld.wolfram.com/ModuloMultiplicationGroup.html">"Modulo Multiplication Group"</a>. <i><a href="/wiki/MathWorld" title="MathWorld">MathWorld</a></i>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=MathWorld&rft.atitle=Modulo+Multiplication+Group&rft.au=Weisstein%2C+Eric+W.&rft_id=https%3A%2F%2Fmathworld.wolfram.com%2FModuloMultiplicationGroup.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3AMultiplicative+group+of+integers+modulo+n" class="Z3988"></span></span></span> </li> <li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://encyclopediaofmath.org/wiki/Primitive_root">"Primitive root - Encyclopedia of Mathematics"</a>. <i>encyclopediaofmath.org</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2024-07-06</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=encyclopediaofmath.org&rft.atitle=Primitive+root+-+Encyclopedia+of+Mathematics&rft_id=https%3A%2F%2Fencyclopediaofmath.org%2Fwiki%2FPrimitive_root&rfr_id=info%3Asid%2Fen.wikipedia.org%3AMultiplicative+group+of+integers+modulo+n" class="Z3988"></span></span> </li> <li id="cite_note-Vinogradov2003.pp=105-121-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-Vinogradov2003.pp=105-121_3-0">^</a></b></span> <span class="reference-text"><a href="#CITEREFVinogradov2003">Vinogradov 2003</a>, pp. 105–121, § VI PRIMITIVE ROOTS AND INDICES</span> </li> <li id="cite_note-FOOTNOTEGauss1986arts._52–56,_82–891-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-FOOTNOTEGauss1986arts._52–56,_82–891_4-0">^</a></b></span> <span class="reference-text"><a href="#CITEREFGauss1986">Gauss 1986</a>, arts. 52–56, 82–891.</span> </li> <li id="cite_note-FOOTNOTEVinogradov2003106-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-FOOTNOTEVinogradov2003106_5-0">^</a></b></span> <span class="reference-text"><a href="#CITEREFVinogradov2003">Vinogradov 2003</a>, p. 106.</span> </li> <li id="cite_note-FOOTNOTEGauss1986arts._90–91-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-FOOTNOTEGauss1986arts._90–91_6-0">^</a></b></span> <span class="reference-text"><a href="#CITEREFGauss1986">Gauss 1986</a>, arts. 90–91.</span> </li> <li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text">Riesel covers all of this. <a href="#CITEREFRiesel1994">Riesel 1994</a>, pp. 267–275.</span> </li> <li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFErdősPomerance1986" class="citation journal cs1"><a href="/wiki/Paul_Erd%C5%91s" title="Paul Erdős">Erdős, Paul</a>; <a href="/wiki/Carl_Pomerance" title="Carl Pomerance">Pomerance, Carl</a> (1986). <a rel="nofollow" class="external text" href="https://doi.org/10.1090%2Fs0025-5718-1986-0815848-x">"On the number of false witnesses for a composite number"</a>. <i><a href="/wiki/Mathematics_of_Computation" title="Mathematics of Computation">Mathematics of Computation</a></i>. <b>46</b> (173): 259–279. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1090%2Fs0025-5718-1986-0815848-x">10.1090/s0025-5718-1986-0815848-x</a></span>. <a href="/wiki/Zbl_(identifier)" class="mw-redirect" title="Zbl (identifier)">Zbl</a> <a rel="nofollow" class="external text" href="https://zbmath.org/?format=complete&q=an:0586.10003">0586.10003</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Mathematics+of+Computation&rft.atitle=On+the+number+of+false+witnesses+for+a+composite+number&rft.volume=46&rft.issue=173&rft.pages=259-279&rft.date=1986&rft_id=https%3A%2F%2Fzbmath.org%2F%3Fformat%3Dcomplete%26q%3Dan%3A0586.10003%23id-name%3DZbl&rft_id=info%3Adoi%2F10.1090%2Fs0025-5718-1986-0815848-x&rft.aulast=Erd%C5%91s&rft.aufirst=Paul&rft.au=Pomerance%2C+Carl&rft_id=https%3A%2F%2Fdoi.org%2F10.1090%252Fs0025-5718-1986-0815848-x&rfr_id=info%3Asid%2Fen.wikipedia.org%3AMultiplicative+group+of+integers+modulo+n" class="Z3988"></span></span> </li> </ol></div></div> <div class="mw-heading mw-heading2"><h2 id="References">References</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Multiplicative_group_of_integers_modulo_n&action=edit&section=15" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The <i><a href="/wiki/Disquisitiones_Arithmeticae" title="Disquisitiones Arithmeticae">Disquisitiones Arithmeticae</a></i> has been translated from Gauss's <a href="/wiki/Classical_Latin" title="Classical Latin">Ciceronian Latin</a> into <a href="/wiki/English_language" title="English language">English</a> and <a href="/wiki/German_language" title="German language">German</a>. The German edition includes all of his papers on number theory: all the proofs of <a href="/wiki/Quadratic_reciprocity" title="Quadratic reciprocity">quadratic reciprocity</a>, the determination of the sign of the <a href="/wiki/Gauss_sum" title="Gauss sum">Gauss sum</a>, the investigations into <a href="/wiki/Biquadratic_reciprocity" class="mw-redirect" title="Biquadratic reciprocity">biquadratic reciprocity</a>, and unpublished notes. </p> <ul><li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFGauss1986" class="citation cs2"><a href="/wiki/Carl_Friedrich_Gauss" title="Carl Friedrich Gauss">Gauss, Carl Friedrich</a> (1986), <i>Disquisitiones Arithmeticae (English translation, Second, corrected edition)</i>, translated by Clarke, Arthur A., New York: <a href="/wiki/Springer_Science%2BBusiness_Media" title="Springer Science+Business Media">Springer</a>, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-387-96254-2" title="Special:BookSources/978-0-387-96254-2"><bdi>978-0-387-96254-2</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Disquisitiones+Arithmeticae+%28English+translation%2C+Second%2C+corrected+edition%29&rft.place=New+York&rft.pub=Springer&rft.date=1986&rft.isbn=978-0-387-96254-2&rft.aulast=Gauss&rft.aufirst=Carl+Friedrich&rfr_id=info%3Asid%2Fen.wikipedia.org%3AMultiplicative+group+of+integers+modulo+n" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFGauss1965" class="citation cs2">Gauss, Carl Friedrich (1965), <i>Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (German translation, Second edition)</i>, translated by Maser, H., New York: Chelsea, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-8284-0191-3" title="Special:BookSources/978-0-8284-0191-3"><bdi>978-0-8284-0191-3</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Untersuchungen+uber+hohere+Arithmetik+%28Disquisitiones+Arithemeticae+%26+other+papers+on+number+theory%29+%28German+translation%2C+Second+edition%29&rft.place=New+York&rft.pub=Chelsea&rft.date=1965&rft.isbn=978-0-8284-0191-3&rft.aulast=Gauss&rft.aufirst=Carl+Friedrich&rfr_id=info%3Asid%2Fen.wikipedia.org%3AMultiplicative+group+of+integers+modulo+n" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFRiesel1994" class="citation cs2"><a href="/wiki/Hans_Riesel" title="Hans Riesel">Riesel, Hans</a> (1994), <i>Prime Numbers and Computer Methods for Factorization (second edition)</i>, Boston: Birkhäuser, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-8176-3743-9" title="Special:BookSources/978-0-8176-3743-9"><bdi>978-0-8176-3743-9</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Prime+Numbers+and+Computer+Methods+for+Factorization+%28second+edition%29&rft.place=Boston&rft.pub=Birkh%C3%A4user&rft.date=1994&rft.isbn=978-0-8176-3743-9&rft.aulast=Riesel&rft.aufirst=Hans&rfr_id=info%3Asid%2Fen.wikipedia.org%3AMultiplicative+group+of+integers+modulo+n" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFVinogradov2003" class="citation cs2"><a href="/wiki/Ivan_Matveyevich_Vinogradov" class="mw-redirect" title="Ivan Matveyevich Vinogradov">Vinogradov, I. M.</a> (2003), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=xlIfdGPM9t4C&pg=PA105">"§ VI Primitive roots and indices"</a>, <i>Elements of Number Theory</i>, Mineola, NY: Dover Publications, pp. 105–121, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-486-49530-9" title="Special:BookSources/978-0-486-49530-9"><bdi>978-0-486-49530-9</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=%C2%A7+VI+Primitive+roots+and+indices&rft.btitle=Elements+of+Number+Theory&rft.place=Mineola%2C+NY&rft.pages=105-121&rft.pub=Dover+Publications&rft.date=2003&rft.isbn=978-0-486-49530-9&rft.aulast=Vinogradov&rft.aufirst=I.+M.&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DxlIfdGPM9t4C%26pg%3DPA105&rfr_id=info%3Asid%2Fen.wikipedia.org%3AMultiplicative+group+of+integers+modulo+n" class="Z3988"></span></li></ul> <div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Multiplicative_group_of_integers_modulo_n&action=edit&section=16" title="Edit section: External links"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><span class="citation mathworld" id="Reference-Mathworld-Modulo_Multiplication_Group"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFWeisstein" class="citation web cs1"><a href="/wiki/Eric_W._Weisstein" title="Eric W. Weisstein">Weisstein, Eric W.</a> <a rel="nofollow" class="external text" href="https://mathworld.wolfram.com/ModuloMultiplicationGroup.html">"Modulo Multiplication Group"</a>. <i><a href="/wiki/MathWorld" title="MathWorld">MathWorld</a></i>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=MathWorld&rft.atitle=Modulo+Multiplication+Group&rft.au=Weisstein%2C+Eric+W.&rft_id=https%3A%2F%2Fmathworld.wolfram.com%2FModuloMultiplicationGroup.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3AMultiplicative+group+of+integers+modulo+n" class="Z3988"></span></span></li> <li><span class="citation mathworld" id="Reference-Mathworld-Primitive_Root"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFWeisstein" class="citation web cs1"><a href="/wiki/Eric_W._Weisstein" title="Eric W. Weisstein">Weisstein, Eric W.</a> <a rel="nofollow" class="external text" href="https://mathworld.wolfram.com/PrimitiveRoot.html">"Primitive Root"</a>. <i><a href="/wiki/MathWorld" title="MathWorld">MathWorld</a></i>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=MathWorld&rft.atitle=Primitive+Root&rft.au=Weisstein%2C+Eric+W.&rft_id=https%3A%2F%2Fmathworld.wolfram.com%2FPrimitiveRoot.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3AMultiplicative+group+of+integers+modulo+n" class="Z3988"></span></span></li> <li><a rel="nofollow" class="external text" href="http://hobbes.la.asu.edu/groups/groups.html">Web-based tool to interactively compute group tables</a> by John Jones</li> <li><abbr title="On-Line Encyclopedia of Integer Sequences">OEIS</abbr> <a rel="nofollow" class="external text" href="https://oeis.org/A033948">sequence A033948 (Numbers that have a primitive root (the multiplicative group modulo n is cyclic))</a></li> <li>Numbers n such that the multiplicative group modulo n is the direct product of k cyclic groups: <ul><li>k = 2 <abbr title="On-Line Encyclopedia of Integer Sequences">OEIS</abbr> <a rel="nofollow" class="external text" href="https://oeis.org/A272592">sequence A272592 (2 cyclic groups)</a></li> <li>k = 3 <abbr title="On-Line Encyclopedia of Integer Sequences">OEIS</abbr> <a rel="nofollow" class="external text" href="https://oeis.org/A272593">sequence A272593 (3 cyclic groups)</a></li> <li>k = 4 <abbr title="On-Line Encyclopedia of Integer Sequences">OEIS</abbr> <a rel="nofollow" class="external text" href="https://oeis.org/A272594">sequence A272594 (4 cyclic groups)</a></li></ul></li> <li><abbr title="On-Line Encyclopedia of Integer Sequences">OEIS</abbr> <a rel="nofollow" class="external text" href="https://oeis.org/A272590">sequence A272590 (The smallest number m such that the multiplicative group modulo m is the direct product of n cyclic groups)</a></li></ul>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=Multiplicative_group_of_integers_modulo_n&oldid=1249898660">https://en.wikipedia.org/w/index.php?title=Multiplicative_group_of_integers_modulo_n&oldid=1249898660</a>"</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Help:Category" title="Help:Category">Categories</a>: <ul><li><a href="/wiki/Category:Finite_groups" title="Category:Finite groups">Finite groups</a></li><li><a href="/wiki/Category:Modular_arithmetic" title="Category:Modular arithmetic">Modular arithmetic</a></li><li><a href="/wiki/Category:Multiplication" title="Category:Multiplication">Multiplication</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_matches_Wikidata" title="Category:Short description matches Wikidata">Short description matches Wikidata</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> This page was last edited on 7 October 2024, at 12:13<span class="anonymous-show"> (UTC)</span>.</li> <li id="footer-info-copyright">Text is available under the <a href="/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License" title="Wikipedia:Text of the Creative Commons Attribution-ShareAlike 4.0 International License">Creative Commons Attribution-ShareAlike 4.0 License</a>; additional terms may apply. By using this site, you agree to the <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use" class="extiw" title="foundation:Special:MyLanguage/Policy:Terms of Use">Terms of Use</a> and <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy" class="extiw" title="foundation:Special:MyLanguage/Policy:Privacy policy">Privacy Policy</a>. Wikipedia® is a registered trademark of the <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Privacy policy</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:About">About Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:General_disclaimer">Disclaimers</a></li> <li id="footer-places-contact"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code of Conduct</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Developers</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/en.wikipedia.org">Statistics</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Cookie statement</a></li> <li id="footer-places-mobileview"><a href="//en.m.wikipedia.org/w/index.php?title=Multiplicative_group_of_integers_modulo_n&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" loading="lazy"></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/w/resources/assets/poweredby_mediawiki.svg" alt="Powered by MediaWiki" width="88" height="31" loading="lazy"></a></li> </ul> </footer> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-5cd4cd96d5-mhvqc","wgBackendResponseTime":139,"wgPageParseReport":{"limitreport":{"cputime":"0.460","walltime":"0.762","ppvisitednodes":{"value":2436,"limit":1000000},"postexpandincludesize":{"value":53509,"limit":2097152},"templateargumentsize":{"value":3572,"limit":2097152},"expansiondepth":{"value":12,"limit":100},"expensivefunctioncount":{"value":2,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":68047,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 447.164 1 -total"," 33.93% 151.719 1 Template:Reflist"," 30.62% 136.900 3 Template:MathWorld"," 24.88% 111.275 1 Template:Group_theory_sidebar"," 24.42% 109.208 1 Template:Sidebar_with_collapsible_lists"," 16.11% 72.046 1 Template:Short_description"," 10.57% 47.280 2 Template:Pagetype"," 8.53% 38.141 2 Template:Sidebar"," 8.25% 36.880 3 Template:Hlist"," 7.93% 35.471 3 Template:Sfn"]},"scribunto":{"limitreport-timeusage":{"value":"0.239","limit":"10.000"},"limitreport-memusage":{"value":6816058,"limit":52428800},"limitreport-logs":"anchor_id_list = table#1 {\n [\"CITEREFErdősPomerance1986\"] = 1,\n [\"CITEREFGauss1965\"] = 1,\n [\"CITEREFGauss1986\"] = 1,\n [\"CITEREFRiesel1994\"] = 1,\n [\"CITEREFVinogradov2003\"] = 1,\n}\ntemplate_list = table#1 {\n [\"Citation\"] = 4,\n [\"Cite journal\"] = 1,\n [\"Cite web\"] = 1,\n [\"DISPLAYTITLE:Multiplicative group of integers modulo ''n''\"] = 1,\n [\"Group theory sidebar\"] = 1,\n [\"Harvnb\"] = 2,\n [\"Main article\"] = 1,\n [\"Math\"] = 1,\n [\"MathWorld\"] = 3,\n [\"Nowrap\"] = 23,\n [\"OEIS\"] = 4,\n [\"OEIS el\"] = 5,\n [\"Reflist\"] = 1,\n [\"Sfn\"] = 3,\n [\"Short description\"] = 1,\n}\narticle_whitelist = table#1 {\n}\n"},"cachereport":{"origin":"mw-api-int.codfw.canary-54459f6c5c-fq5ns","timestamp":"20241127005307","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Multiplicative group of integers modulo n","url":"https:\/\/en.wikipedia.org\/wiki\/Multiplicative_group_of_integers_modulo_n","sameAs":"http:\/\/www.wikidata.org\/entity\/Q1169249","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q1169249","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2004-11-21T22:25:24Z","dateModified":"2024-10-07T12:13:02Z","image":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/5\/5f\/Cyclic_group.svg","headline":"group of units of the ring of integers modulo n"}</script> </body> </html>

CINXE.COM

Multiplicative group of integers modulo n - Wikipedia