CINXE.COM

<!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>Coprime integers - 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":"2155ddf1-da36-4ba4-9bac-e90da328489b","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Coprime_integers","wgTitle":"Coprime integers","wgCurRevisionId":1252719665,"wgRevisionId":1252719665,"wgArticleId":6556,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Articles with short description","Short description is different from Wikidata","Number theory"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Coprime_integers","wgRelevantArticleId":6556,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgRedirectedFrom":"Coprime","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":20000,"wgInternalRedirectTargetUrl":"/wiki/Coprime_integers","wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":false,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q104752","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.cite.styles":"ready","ext.math.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["mediawiki.action.view.redirect","ext.cite.ux-enhancements","mediawiki.page.media","ext.scribunto.logs","site","mediawiki.page.ready","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%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 name="viewport" content="width=1120"> <meta property="og:title" content="Coprime integers - 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/Coprime_integers"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Coprime_integers&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/Coprime_integers"> <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-Coprime_integers rootpage-Coprime_integers 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=Coprime+integers" 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=Coprime+integers" 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=Coprime+integers" 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=Coprime+integers" 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-Notation_and_testing" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Notation_and_testing"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Notation and testing</span> </div> </a> <ul id="toc-Notation_and_testing-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Properties" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Properties"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Properties</span> </div> </a> <ul id="toc-Properties-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Coprimality_in_sets" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Coprimality_in_sets"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Coprimality in sets</span> </div> </a> <ul id="toc-Coprimality_in_sets-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Coprimality_in_ring_ideals" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Coprimality_in_ring_ideals"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Coprimality in ring ideals</span> </div> </a> <ul id="toc-Coprimality_in_ring_ideals-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Probability_of_coprimality" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Probability_of_coprimality"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Probability of coprimality</span> </div> </a> <ul id="toc-Probability_of_coprimality-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Generating_all_coprime_pairs" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Generating_all_coprime_pairs"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>Generating all coprime pairs</span> </div> </a> <ul id="toc-Generating_all_coprime_pairs-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Applications" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Applications"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>Applications</span> </div> </a> <ul id="toc-Applications-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Generalizations" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Generalizations"> <div class="vector-toc-text"> <span class="vector-toc-numb">8</span> <span>Generalizations</span> </div> </a> <ul id="toc-Generalizations-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">9</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">10</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">11</span> <span>References</span> </div> </a> <ul id="toc-References-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Further_reading" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Further_reading"> <div class="vector-toc-text"> <span class="vector-toc-numb">12</span> <span>Further reading</span> </div> </a> <ul id="toc-Further_reading-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"><span class="mw-page-title-main">Coprime integers</span></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 53 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-53" 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">53 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-ar mw-list-item"><a href="https://ar.wikipedia.org/wiki/%D8%B9%D8%AF%D8%AF%D8%A7%D9%86_%D8%A3%D9%88%D9%84%D9%8A%D8%A7%D9%86_%D9%81%D9%8A%D9%85%D8%A7_%D8%A8%D9%8A%D9%86%D9%87%D9%85%D8%A7" title="عددان أوليان فيما بينهما – Arabic" lang="ar" hreflang="ar" data-title="عددان أوليان فيما بينهما" data-language-autonym="العربية" data-language-local-name="Arabic" class="interlanguage-link-target"><span>العربية</span></a></li><li class="interlanguage-link interwiki-ast mw-list-item"><a href="https://ast.wikipedia.org/wiki/N%C3%BAmberos_coprimos" title="Númberos coprimos – Asturian" lang="ast" hreflang="ast" data-title="Númberos coprimos" data-language-autonym="Asturianu" data-language-local-name="Asturian" class="interlanguage-link-target"><span>Asturianu</span></a></li><li class="interlanguage-link interwiki-bn mw-list-item"><a href="https://bn.wikipedia.org/wiki/%E0%A6%B8%E0%A6%B9-%E0%A6%AE%E0%A7%8C%E0%A6%B2%E0%A6%BF%E0%A6%95" title="সহ-মৌলিক – Bangla" lang="bn" hreflang="bn" data-title="সহ-মৌলিক" data-language-autonym="বাংলা" data-language-local-name="Bangla" class="interlanguage-link-target"><span>বাংলা</span></a></li><li class="interlanguage-link interwiki-bg mw-list-item"><a href="https://bg.wikipedia.org/wiki/%D0%92%D0%B7%D0%B0%D0%B8%D0%BC%D0%BD%D0%BE_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D0%B8_%D1%87%D0%B8%D1%81%D0%BB%D0%B0" title="Взаимно прости числа – Bulgarian" lang="bg" hreflang="bg" data-title="Взаимно прости числа" data-language-autonym="Български" data-language-local-name="Bulgarian" class="interlanguage-link-target"><span>Български</span></a></li><li class="interlanguage-link interwiki-bs mw-list-item"><a href="https://bs.wikipedia.org/wiki/Uzajamno_prosti_brojevi" title="Uzajamno prosti brojevi – Bosnian" lang="bs" hreflang="bs" data-title="Uzajamno prosti brojevi" data-language-autonym="Bosanski" data-language-local-name="Bosnian" class="interlanguage-link-target"><span>Bosanski</span></a></li><li class="interlanguage-link interwiki-ca mw-list-item"><a href="https://ca.wikipedia.org/wiki/Nombres_coprimers" title="Nombres coprimers – Catalan" lang="ca" hreflang="ca" data-title="Nombres coprimers" data-language-autonym="Català" data-language-local-name="Catalan" class="interlanguage-link-target"><span>Català</span></a></li><li class="interlanguage-link interwiki-cs mw-list-item"><a href="https://cs.wikipedia.org/wiki/Nesoud%C4%9Bln%C3%A1_%C4%8D%C3%ADsla" title="Nesoudělná čísla – Czech" lang="cs" hreflang="cs" data-title="Nesoudělná čísla" data-language-autonym="Čeština" data-language-local-name="Czech" class="interlanguage-link-target"><span>Čeština</span></a></li><li class="interlanguage-link interwiki-da mw-list-item"><a href="https://da.wikipedia.org/wiki/Indbyrdes_primisk" title="Indbyrdes primisk – Danish" lang="da" hreflang="da" data-title="Indbyrdes primisk" data-language-autonym="Dansk" data-language-local-name="Danish" class="interlanguage-link-target"><span>Dansk</span></a></li><li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Teilerfremdheit" title="Teilerfremdheit – German" lang="de" hreflang="de" data-title="Teilerfremdheit" data-language-autonym="Deutsch" data-language-local-name="German" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-et mw-list-item"><a href="https://et.wikipedia.org/wiki/%C3%9Chisteguriteta_arvud" title="Ühisteguriteta arvud – Estonian" lang="et" hreflang="et" data-title="Ühisteguriteta arvud" data-language-autonym="Eesti" data-language-local-name="Estonian" class="interlanguage-link-target"><span>Eesti</span></a></li><li class="interlanguage-link interwiki-el mw-list-item"><a href="https://el.wikipedia.org/wiki/%CE%A3%CF%87%CE%B5%CF%84%CE%B9%CE%BA%CE%AC_%CF%80%CF%81%CF%8E%CF%84%CE%BF%CE%B9" title="Σχετικά πρώτοι – Greek" lang="el" hreflang="el" data-title="Σχετικά πρώτοι" data-language-autonym="Ελληνικά" data-language-local-name="Greek" class="interlanguage-link-target"><span>Ελληνικά</span></a></li><li class="interlanguage-link interwiki-eml mw-list-item"><a href="https://eml.wikipedia.org/wiki/Int%C4%93r_copr%C3%ACm" title="Intēr coprìm – Emiliano-Romagnolo" lang="egl" hreflang="egl" data-title="Intēr coprìm" data-language-autonym="Emiliàn e rumagnòl" data-language-local-name="Emiliano-Romagnolo" class="interlanguage-link-target"><span>Emiliàn e rumagnòl</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/N%C3%BAmeros_coprimos" title="Números coprimos – Spanish" lang="es" hreflang="es" data-title="Números coprimos" 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-eo mw-list-item"><a href="https://eo.wikipedia.org/wiki/Reciproka_primeco" title="Reciproka primeco – Esperanto" lang="eo" hreflang="eo" data-title="Reciproka primeco" data-language-autonym="Esperanto" data-language-local-name="Esperanto" class="interlanguage-link-target"><span>Esperanto</span></a></li><li class="interlanguage-link interwiki-eu mw-list-item"><a href="https://eu.wikipedia.org/wiki/Zenbaki_elkarrekiko_lehenak" title="Zenbaki elkarrekiko lehenak – Basque" lang="eu" hreflang="eu" data-title="Zenbaki elkarrekiko lehenak" data-language-autonym="Euskara" data-language-local-name="Basque" class="interlanguage-link-target"><span>Euskara</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D8%A7%D8%B9%D8%AF%D8%A7%D8%AF_%D9%85%D8%AA%D8%A8%D8%A7%DB%8C%D9%86" title="اعداد متباین – Persian" lang="fa" hreflang="fa" data-title="اعداد متباین" data-language-autonym="فارسی" data-language-local-name="Persian" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/Nombres_premiers_entre_eux" title="Nombres premiers entre eux – French" lang="fr" hreflang="fr" data-title="Nombres premiers entre eux" data-language-autonym="Français" data-language-local-name="French" class="interlanguage-link-target"><span>Français</span></a></li><li class="interlanguage-link interwiki-gl mw-list-item"><a href="https://gl.wikipedia.org/wiki/N%C3%BAmeros_primos_entre_si" title="Números primos entre si – Galician" lang="gl" hreflang="gl" data-title="Números primos entre si" data-language-autonym="Galego" data-language-local-name="Galician" class="interlanguage-link-target"><span>Galego</span></a></li><li class="interlanguage-link interwiki-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/%EC%84%9C%EB%A1%9C%EC%86%8C_%EC%95%84%EC%9D%B4%EB%94%94%EC%96%BC" title="서로소 아이디얼 – Korean" lang="ko" hreflang="ko" data-title="서로소 아이디얼" data-language-autonym="한국어" data-language-local-name="Korean" class="interlanguage-link-target"><span>한국어</span></a></li><li class="interlanguage-link interwiki-hy mw-list-item"><a href="https://hy.wikipedia.org/wiki/%D5%93%D5%B8%D5%AD%D5%A1%D5%A4%D5%A1%D6%80%D5%B1_%D5%BA%D5%A1%D6%80%D5%A6_%D5%A9%D5%BE%D5%A5%D6%80" title="Փոխադարձ պարզ թվեր – Armenian" lang="hy" hreflang="hy" data-title="Փոխադարձ պարզ թվեր" data-language-autonym="Հայերեն" data-language-local-name="Armenian" class="interlanguage-link-target"><span>Հայերեն</span></a></li><li class="interlanguage-link interwiki-id mw-list-item"><a href="https://id.wikipedia.org/wiki/Koprima_(bilangan)" title="Koprima (bilangan) – Indonesian" lang="id" hreflang="id" data-title="Koprima (bilangan)" data-language-autonym="Bahasa Indonesia" data-language-local-name="Indonesian" class="interlanguage-link-target"><span>Bahasa Indonesia</span></a></li><li class="interlanguage-link interwiki-is mw-list-item"><a href="https://is.wikipedia.org/wiki/%C3%93sam%C3%BE%C3%A1tta" title="Ósamþátta – Icelandic" lang="is" hreflang="is" data-title="Ósamþátta" data-language-autonym="Íslenska" data-language-local-name="Icelandic" class="interlanguage-link-target"><span>Íslenska</span></a></li><li class="interlanguage-link interwiki-it mw-list-item"><a href="https://it.wikipedia.org/wiki/Interi_coprimi" title="Interi coprimi – Italian" lang="it" hreflang="it" data-title="Interi coprimi" data-language-autonym="Italiano" data-language-local-name="Italian" class="interlanguage-link-target"><span>Italiano</span></a></li><li class="interlanguage-link interwiki-he mw-list-item"><a href="https://he.wikipedia.org/wiki/%D7%9E%D7%A1%D7%A4%D7%A8%D7%99%D7%9D_%D7%96%D7%A8%D7%99%D7%9D" 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-kk mw-list-item"><a href="https://kk.wikipedia.org/wiki/%D3%A8%D0%B7%D0%B0%D1%80%D0%B0_%D0%B6%D0%B0%D0%B9_%D1%81%D0%B0%D0%BD%D0%B4%D0%B0%D1%80" title="Өзара жай сандар – Kazakh" lang="kk" hreflang="kk" data-title="Өзара жай сандар" data-language-autonym="Қазақша" data-language-local-name="Kazakh" class="interlanguage-link-target"><span>Қазақша</span></a></li><li class="interlanguage-link interwiki-lv mw-list-item"><a href="https://lv.wikipedia.org/wiki/Savstarp%C4%93ji_pirmskait%C4%BCi" title="Savstarpēji pirmskaitļi – Latvian" lang="lv" hreflang="lv" data-title="Savstarpēji pirmskaitļi" data-language-autonym="Latviešu" data-language-local-name="Latvian" class="interlanguage-link-target"><span>Latviešu</span></a></li><li class="interlanguage-link interwiki-hu mw-list-item"><a href="https://hu.wikipedia.org/wiki/Relat%C3%ADv_pr%C3%ADmek" title="Relatív prímek – Hungarian" lang="hu" hreflang="hu" data-title="Relatív prímek" data-language-autonym="Magyar" data-language-local-name="Hungarian" class="interlanguage-link-target"><span>Magyar</span></a></li><li class="interlanguage-link interwiki-mk mw-list-item"><a href="https://mk.wikipedia.org/wiki/%D0%97%D0%B0%D0%B5%D0%BC%D0%BD%D0%BE_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D0%B8_%D0%B1%D1%80%D0%BE%D0%B5%D0%B2%D0%B8" title="Заемно прости броеви – Macedonian" lang="mk" hreflang="mk" data-title="Заемно прости броеви" data-language-autonym="Македонски" data-language-local-name="Macedonian" class="interlanguage-link-target"><span>Македонски</span></a></li><li class="interlanguage-link interwiki-ml mw-list-item"><a href="https://ml.wikipedia.org/wiki/%E0%B4%B8%E0%B4%B9-%E0%B4%85%E0%B4%AD%E0%B4%BE%E0%B4%9C%E0%B5%8D%E0%B4%AF%E0%B4%82" title="സഹ-അഭാജ്യം – Malayalam" lang="ml" hreflang="ml" data-title="സഹ-അഭാജ്യം" data-language-autonym="മലയാളം" data-language-local-name="Malayalam" class="interlanguage-link-target"><span>മലയാളം</span></a></li><li class="interlanguage-link interwiki-mn mw-list-item"><a href="https://mn.wikipedia.org/wiki/%D0%A5%D0%B0%D1%80%D0%B8%D0%BB%D1%86%D0%B0%D0%BD_%D0%B0%D0%BD%D1%85%D0%BD%D1%8B_%D1%82%D0%BE%D0%BE%D0%BD%D1%83%D1%83%D0%B4" title="Харилцан анхны тоонууд – Mongolian" lang="mn" hreflang="mn" data-title="Харилцан анхны тоонууд" data-language-autonym="Монгол" data-language-local-name="Mongolian" class="interlanguage-link-target"><span>Монгол</span></a></li><li class="interlanguage-link interwiki-nl mw-list-item"><a href="https://nl.wikipedia.org/wiki/Relatief_priem" title="Relatief priem – Dutch" lang="nl" hreflang="nl" data-title="Relatief priem" data-language-autonym="Nederlands" data-language-local-name="Dutch" class="interlanguage-link-target"><span>Nederlands</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E4%BA%92%E3%81%84%E3%81%AB%E7%B4%A0_(%E6%95%B4%E6%95%B0%E8%AB%96)" title="互いに素 (整数論) – Japanese" lang="ja" hreflang="ja" data-title="互いに素 (整数論)" data-language-autonym="日本語" data-language-local-name="Japanese" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-no mw-list-item"><a href="https://no.wikipedia.org/wiki/Relativt_primisk" title="Relativt primisk – Norwegian Bokmål" lang="nb" hreflang="nb" data-title="Relativt primisk" data-language-autonym="Norsk bokmål" data-language-local-name="Norwegian Bokmål" class="interlanguage-link-target"><span>Norsk bokmål</span></a></li><li class="interlanguage-link interwiki-nds mw-list-item"><a href="https://nds.wikipedia.org/wiki/Relativ_prim" title="Relativ prim – Low German" lang="nds" hreflang="nds" data-title="Relativ prim" data-language-autonym="Plattdüütsch" data-language-local-name="Low German" class="interlanguage-link-target"><span>Plattdüütsch</span></a></li><li class="interlanguage-link interwiki-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/Liczby_wzgl%C4%99dnie_pierwsze" title="Liczby względnie pierwsze – Polish" lang="pl" hreflang="pl" data-title="Liczby względnie pierwsze" data-language-autonym="Polski" data-language-local-name="Polish" class="interlanguage-link-target"><span>Polski</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/N%C3%BAmeros_primos_entre_si" title="Números primos entre si – Portuguese" lang="pt" hreflang="pt" data-title="Números primos entre si" data-language-autonym="Português" data-language-local-name="Portuguese" class="interlanguage-link-target"><span>Português</span></a></li><li class="interlanguage-link interwiki-ro mw-list-item"><a href="https://ro.wikipedia.org/wiki/Numere_prime_%C3%AEntre_ele" title="Numere prime între ele – Romanian" lang="ro" hreflang="ro" data-title="Numere prime între ele" data-language-autonym="Română" data-language-local-name="Romanian" class="interlanguage-link-target"><span>Română</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%92%D0%B7%D0%B0%D0%B8%D0%BC%D0%BD%D0%BE_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D1%8B%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%B0" 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-simple mw-list-item"><a href="https://simple.wikipedia.org/wiki/Coprime" title="Coprime – Simple English" lang="en-simple" hreflang="en-simple" data-title="Coprime" data-language-autonym="Simple English" data-language-local-name="Simple English" class="interlanguage-link-target"><span>Simple English</span></a></li><li class="interlanguage-link interwiki-sk mw-list-item"><a href="https://sk.wikipedia.org/wiki/Nes%C3%BAdelite%C4%BEnos%C5%A5" title="Nesúdeliteľnosť – Slovak" lang="sk" hreflang="sk" data-title="Nesúdeliteľnosť" data-language-autonym="Slovenčina" data-language-local-name="Slovak" class="interlanguage-link-target"><span>Slovenčina</span></a></li><li class="interlanguage-link interwiki-sl mw-list-item"><a href="https://sl.wikipedia.org/wiki/Tuje_%C5%A1tevilo" title="Tuje število – Slovenian" lang="sl" hreflang="sl" data-title="Tuje število" data-language-autonym="Slovenščina" data-language-local-name="Slovenian" class="interlanguage-link-target"><span>Slovenščina</span></a></li><li class="interlanguage-link interwiki-sr mw-list-item"><a href="https://sr.wikipedia.org/wiki/%D0%A3%D0%B7%D0%B0%D1%98%D0%B0%D0%BC%D0%BD%D0%BE_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D0%B8_%D0%B1%D1%80%D0%BE%D1%98%D0%B5%D0%B2%D0%B8" title="Узајамно прости бројеви – Serbian" lang="sr" hreflang="sr" data-title="Узајамно прости бројеви" data-language-autonym="Српски / srpski" data-language-local-name="Serbian" class="interlanguage-link-target"><span>Српски / srpski</span></a></li><li class="interlanguage-link interwiki-sh mw-list-item"><a href="https://sh.wikipedia.org/wiki/Uzajamno_prosti_brojevi" title="Uzajamno prosti brojevi – Serbo-Croatian" lang="sh" hreflang="sh" data-title="Uzajamno prosti brojevi" data-language-autonym="Srpskohrvatski / српскохрватски" data-language-local-name="Serbo-Croatian" class="interlanguage-link-target"><span>Srpskohrvatski / српскохрватски</span></a></li><li class="interlanguage-link interwiki-fi mw-list-item"><a href="https://fi.wikipedia.org/wiki/Kesken%C3%A4%C3%A4n_jaottomat_luvut" title="Keskenään jaottomat luvut – Finnish" lang="fi" hreflang="fi" data-title="Keskenään jaottomat luvut" data-language-autonym="Suomi" data-language-local-name="Finnish" class="interlanguage-link-target"><span>Suomi</span></a></li><li class="interlanguage-link interwiki-sv mw-list-item"><a href="https://sv.wikipedia.org/wiki/Relativt_prima" title="Relativt prima – Swedish" lang="sv" hreflang="sv" data-title="Relativt prima" data-language-autonym="Svenska" data-language-local-name="Swedish" class="interlanguage-link-target"><span>Svenska</span></a></li><li class="interlanguage-link interwiki-ta mw-list-item"><a href="https://ta.wikipedia.org/wiki/%E0%AE%9A%E0%AE%BE%E0%AE%B0%E0%AF%8D%E0%AE%AA%E0%AE%95%E0%AE%BE_%E0%AE%AE%E0%AF%81%E0%AE%B4%E0%AF%81%E0%AE%8E%E0%AE%A3%E0%AF%8D%E0%AE%95%E0%AE%B3%E0%AF%8D" title="சார்பகா முழுஎண்கள் – Tamil" lang="ta" hreflang="ta" data-title="சார்பகா முழுஎண்கள்" data-language-autonym="தமிழ்" data-language-local-name="Tamil" class="interlanguage-link-target"><span>தமிழ்</span></a></li><li class="interlanguage-link interwiki-th mw-list-item"><a href="https://th.wikipedia.org/wiki/%E0%B8%88%E0%B8%B3%E0%B8%99%E0%B8%A7%E0%B8%99%E0%B9%80%E0%B8%89%E0%B8%9E%E0%B8%B2%E0%B8%B0%E0%B8%AA%E0%B8%B1%E0%B8%A1%E0%B8%9E%E0%B8%B1%E0%B8%97%E0%B8%98%E0%B9%8C" title="จำนวนเฉพาะสัมพัทธ์ – Thai" lang="th" hreflang="th" data-title="จำนวนเฉพาะสัมพัทธ์" data-language-autonym="ไทย" data-language-local-name="Thai" class="interlanguage-link-target"><span>ไทย</span></a></li><li class="interlanguage-link interwiki-tg mw-list-item"><a href="https://tg.wikipedia.org/wiki/%D0%90%D0%B4%D0%B0%D0%B4%D2%B3%D0%BE%D0%B8_%D0%B1%D0%B0%D0%B9%D0%BD%D0%B0%D0%BD_%D1%81%D0%BE%D0%B4%D0%B0" title="Ададҳои байнан сода – Tajik" lang="tg" hreflang="tg" data-title="Ададҳои байнан сода" data-language-autonym="Тоҷикӣ" data-language-local-name="Tajik" class="interlanguage-link-target"><span>Тоҷикӣ</span></a></li><li class="interlanguage-link interwiki-tr mw-list-item"><a href="https://tr.wikipedia.org/wiki/Aralar%C4%B1nda_asal" title="Aralarında asal – Turkish" lang="tr" hreflang="tr" data-title="Aralarında asal" data-language-autonym="Türkçe" data-language-local-name="Turkish" class="interlanguage-link-target"><span>Türkçe</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%92%D0%B7%D0%B0%D1%94%D0%BC%D0%BD%D0%BE_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D1%96_%D1%87%D0%B8%D1%81%D0%BB%D0%B0" title="Взаємно прості числа – Ukrainian" lang="uk" hreflang="uk" data-title="Взаємно прості числа" 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/S%E1%BB%91_nguy%C3%AAn_t%E1%BB%91_c%C3%B9ng_nhau" title="Số nguyên tố cùng nhau – Vietnamese" lang="vi" hreflang="vi" data-title="Số nguyên tố cùng nhau" 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-yue mw-list-item"><a href="https://zh-yue.wikipedia.org/wiki/%E7%9B%B8%E5%B0%8D%E8%B3%AA%E6%95%B8" title="相對質數 – Cantonese" lang="yue" hreflang="yue" data-title="相對質數" data-language-autonym="粵語" data-language-local-name="Cantonese" class="interlanguage-link-target"><span>粵語</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E4%BA%92%E8%B3%AA" title="互質 – Chinese" lang="zh" hreflang="zh" data-title="互質" 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/Q104752#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/Coprime_integers" 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:Coprime_integers" 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/Coprime_integers"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Coprime_integers&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=Coprime_integers&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/Coprime_integers"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Coprime_integers&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=Coprime_integers&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/Coprime_integers" 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/Coprime_integers" 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=Coprime_integers&oldid=1252719665" 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=Coprime_integers&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=Coprime_integers&id=1252719665&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%2FCoprime_integers"><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%2FCoprime_integers"><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=Coprime_integers&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=Coprime_integers&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 class="wb-otherproject-link wb-otherproject-commons mw-list-item"><a href="https://commons.wikimedia.org/wiki/Category:Coprime_integers" hreflang="en"><span>Wikimedia Commons</span></a></li><li class="wb-otherproject-link wb-otherproject-wikifunctions mw-list-item"><a href="https://www.wikifunctions.org/wiki/Z13701" hreflang="en"><span>Wikifunctions</span></a></li><li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q104752" 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"><span class="mw-redirectedfrom">(Redirected from <a href="/w/index.php?title=Coprime&redirect=no" class="mw-redirect" title="Coprime">Coprime</a>)</span></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">Two numbers without shared prime factors</div> <p>In <a href="/wiki/Number_theory" title="Number theory">number theory</a>, two <a href="/wiki/Integer" title="Integer">integers</a> <span class="texhtml mvar" style="font-style:italic;">a</span> and <span class="texhtml mvar" style="font-style:italic;">b</span> are <b>coprime</b>, <b>relatively prime</b> or <b>mutually prime</b> if the only positive integer that is a <a href="/wiki/Divisor" title="Divisor">divisor</a> of both of them is 1.<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> Consequently, any <a href="/wiki/Prime_number" title="Prime number">prime number</a> that divides <span class="texhtml mvar" style="font-style:italic;">a</span> does not divide <span class="texhtml mvar" style="font-style:italic;">b</span>, and vice versa. This is equivalent to their <a href="/wiki/Greatest_common_divisor" title="Greatest common divisor">greatest common divisor</a> (GCD) being 1.<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> One says also <span class="texhtml mvar" style="font-style:italic;">a</span> <i>is prime to</i> <span class="texhtml mvar" style="font-style:italic;">b</span> or <span class="texhtml mvar" style="font-style:italic;">a</span> <i>is coprime with</i> <span class="texhtml mvar" style="font-style:italic;">b</span>. </p><p>The numbers 8 and 9 are coprime, despite the fact that neither—considered individually—is a prime number, since 1 is their only common divisor. On the other hand, 6 and 9 are not coprime, because they are both divisible by 3. The numerator and denominator of a <a href="/wiki/Reduced_fraction" class="mw-redirect" title="Reduced fraction">reduced fraction</a> are coprime, by definition. </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Notation_and_testing">Notation and testing</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Coprime_integers&action=edit&section=1" title="Edit section: Notation and testing"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>When the integers <span class="texhtml mvar" style="font-style:italic;">a</span> and <span class="texhtml mvar" style="font-style:italic;">b</span> are coprime, the standard way of expressing this fact in mathematical notation is to indicate that their greatest common divisor is one, by the formula <span class="texhtml">gcd(<i>a</i>, <i>b</i>) = 1</span> or <span class="texhtml">(<i>a</i>, <i>b</i>) = 1</span>. In their 1989 textbook <i><a href="/wiki/Concrete_Mathematics" title="Concrete Mathematics">Concrete Mathematics</a></i>, <a href="/wiki/Ronald_Graham" title="Ronald Graham">Ronald Graham</a>, <a href="/wiki/Donald_Knuth" title="Donald Knuth">Donald Knuth</a>, and <a href="/wiki/Oren_Patashnik" title="Oren Patashnik">Oren Patashnik</a> proposed an alternative 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 a\perp b}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>a</mi> <mo>⊥</mo> <mi>b</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a\perp b}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/32b55cea2fe988b733476e92cb40e44fb8b2a24d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.326ex; height:2.176ex;" alt="{\displaystyle a\perp b}"></span> to indicate that <span class="texhtml mvar" style="font-style:italic;">a</span> and <span class="texhtml mvar" style="font-style:italic;">b</span> are relatively prime and that the term "prime" be used instead of coprime (as in <span class="texhtml mvar" style="font-style:italic;">a</span> is <i>prime</i> to <span class="texhtml mvar" style="font-style:italic;">b</span>).<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> </p><p>A fast way to determine whether two numbers are coprime is given by the <a href="/wiki/Euclidean_algorithm" title="Euclidean algorithm">Euclidean algorithm</a> and its faster variants such as <a href="/wiki/Binary_GCD_algorithm" title="Binary GCD algorithm">binary GCD algorithm</a> or <a href="/wiki/Lehmer%27s_GCD_algorithm" title="Lehmer's GCD algorithm">Lehmer's GCD algorithm</a>. </p><p>The number of integers coprime with a positive integer <span class="texhtml mvar" style="font-style:italic;">n</span>, between 1 and <span class="texhtml mvar" style="font-style:italic;">n</span>, is given by <a href="/wiki/Euler%27s_totient_function" title="Euler's totient function">Euler's totient function</a>, also known as Euler's phi function, <span class="texhtml"><i>φ</i>(<i>n</i>)</span>. </p><p>A <a href="/wiki/Set_(mathematics)" title="Set (mathematics)">set</a> of integers can also be called coprime if its elements share no common positive factor except 1. A stronger condition on a set of integers is pairwise coprime, which means that <span class="texhtml mvar" style="font-style:italic;">a</span> and <span class="texhtml mvar" style="font-style:italic;">b</span> are coprime for every pair <span class="texhtml">(<i>a</i>, <i>b</i>)</span> of different integers in the set. The set <span class="texhtml">{2, 3, 4} </span> is coprime, but it is not pairwise coprime since 2 and 4 are not relatively prime. </p> <div class="mw-heading mw-heading2"><h2 id="Properties">Properties</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Coprime_integers&action=edit&section=2" title="Edit section: Properties"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The numbers 1 and −1 are the only integers coprime with every integer, and they are the only integers that are coprime with 0. </p><p>A number of conditions are equivalent to <span class="texhtml mvar" style="font-style:italic;">a</span> and <span class="texhtml mvar" style="font-style:italic;">b</span> being coprime: </p> <ul><li>No <a href="/wiki/Prime_number" title="Prime number">prime number</a> divides both <span class="texhtml mvar" style="font-style:italic;">a</span> and <span class="texhtml mvar" style="font-style:italic;">b</span>.</li> <li>There exist integers <span class="texhtml mvar" style="font-style:italic;">x, y</span> such that <span class="texhtml"><i>ax</i> + <i>by</i> = 1</span> (see <a href="/wiki/B%C3%A9zout%27s_identity" title="Bézout's identity">Bézout's identity</a>).</li> <li>The integer <span class="texhtml mvar" style="font-style:italic;">b</span> has a <a href="/wiki/Modular_multiplicative_inverse" title="Modular multiplicative inverse">multiplicative inverse</a> modulo <span class="texhtml mvar" style="font-style:italic;">a</span>, meaning that there exists an integer <span class="texhtml mvar" style="font-style:italic;">y</span> such that <span class="texhtml"><i>by</i> ≡ 1 (mod <i>a</i>)</span>. In ring-theoretic language, <span class="texhtml mvar" style="font-style:italic;">b</span> is a <a href="/wiki/Unit_(ring_theory)" title="Unit (ring theory)">unit</a> in the <a href="/wiki/Ring_(mathematics)" title="Ring (mathematics)">ring</a> <span class="nowrap">⁠<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} /a\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>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} /a\mathbb {Z} }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ddba73f51996a13e21c913194d8a38320a37c288" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.493ex; height:2.843ex;" alt="{\displaystyle \mathbb {Z} /a\mathbb {Z} }"></span>⁠</span> of <a href="/wiki/Modular_arithmetic" title="Modular arithmetic">integers modulo</a> <span class="texhtml mvar" style="font-style:italic;">a</span>.</li> <li>Every pair of <a href="/wiki/Congruence_relation" title="Congruence relation">congruence relations</a> for an unknown integer <span class="texhtml mvar" style="font-style:italic;">x</span>, of the form <span class="texhtml"><i>x</i> ≡ <i>k</i> (mod <i>a</i>)</span> and <span class="texhtml"><i>x</i> ≡ <i>m</i> (mod <i>b</i>)</span>, has a solution (<a href="/wiki/Chinese_remainder_theorem" title="Chinese remainder theorem">Chinese remainder theorem</a>); in fact the solutions are described by a single congruence relation modulo <span class="texhtml mvar" style="font-style:italic;">ab</span>.</li> <li>The <a href="/wiki/Least_common_multiple" title="Least common multiple">least common multiple</a> of <span class="texhtml mvar" style="font-style:italic;">a</span> and <span class="texhtml mvar" style="font-style:italic;">b</span> is equal to their product <span class="texhtml mvar" style="font-style:italic;">ab</span>, i.e. <span class="texhtml">lcm(<i>a</i>, <i>b</i>) = <i>ab</i></span>.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup></li></ul> <p>As a consequence of the third point, if <span class="texhtml mvar" style="font-style:italic;">a</span> and <span class="texhtml mvar" style="font-style:italic;">b</span> are coprime and <span class="texhtml"><i>br</i> ≡ <i>bs</i> (mod <i>a</i>)</span>, then <span class="texhtml"><i>r</i> ≡ <i>s</i> (mod <i>a</i>)</span>.<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> That is, we may "divide by <span class="texhtml mvar" style="font-style:italic;">b</span>" when working modulo <span class="texhtml mvar" style="font-style:italic;">a</span>. Furthermore, if <span class="texhtml"><i>b</i><sub>1</sub>, <i>b</i><sub>2</sub></span> are both coprime with <span class="texhtml mvar" style="font-style:italic;">a</span>, then so is their product <span class="texhtml"><i>b</i><sub>1</sub><i>b</i><sub>2</sub></span> (i.e., modulo <span class="texhtml mvar" style="font-style:italic;">a</span> it is a product of invertible elements, and therefore invertible);<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> this also follows from the first point by <a href="/wiki/Euclid%27s_lemma" title="Euclid's lemma">Euclid's lemma</a>, which states that if a prime number <span class="texhtml mvar" style="font-style:italic;">p</span> divides a product <span class="texhtml mvar" style="font-style:italic;">bc</span>, then <span class="texhtml mvar" style="font-style:italic;">p</span> divides at least one of the factors <span class="texhtml mvar" style="font-style:italic;">b, c</span>. </p><p>As a consequence of the first point, if <span class="texhtml mvar" style="font-style:italic;">a</span> and <span class="texhtml mvar" style="font-style:italic;">b</span> are coprime, then so are any powers <span class="texhtml mvar" style="font-style:italic;">a<sup>k</sup></span> and <span class="texhtml mvar" style="font-style:italic;">b<sup>m</sup></span>. </p><p>If <span class="texhtml mvar" style="font-style:italic;">a</span> and <span class="texhtml mvar" style="font-style:italic;">b</span> are coprime and <span class="texhtml mvar" style="font-style:italic;">a</span> divides the product <span class="texhtml mvar" style="font-style:italic;">bc</span>, then <span class="texhtml mvar" style="font-style:italic;">a</span> divides <span class="texhtml mvar" style="font-style:italic;">c</span>.<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> This can be viewed as a generalization of Euclid's lemma. </p> <figure class="mw-halign-right" typeof="mw:File/Thumb"><a href="/wiki/File:Coprime-lattice.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/5/55/Coprime-lattice.svg/300px-Coprime-lattice.svg.png" decoding="async" width="300" height="156" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/5/55/Coprime-lattice.svg/450px-Coprime-lattice.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/5/55/Coprime-lattice.svg/600px-Coprime-lattice.svg.png 2x" data-file-width="635" data-file-height="330" /></a><figcaption>Figure 1. The numbers 4 and 9 are coprime. Therefore, the diagonal of a 4 × 9 lattice does not intersect any other <a href="/wiki/Square_lattice" title="Square lattice">lattice points</a></figcaption></figure> <p>The two integers <span class="texhtml mvar" style="font-style:italic;">a</span> and <span class="texhtml mvar" style="font-style:italic;">b</span> are coprime if and only if the point with coordinates <span class="texhtml">(<i>a</i>, <i>b</i>)</span> in a <a href="/wiki/Cartesian_coordinate_system" title="Cartesian coordinate system">Cartesian coordinate system</a> would be "visible" via an unobstructed line of sight from the origin <span class="texhtml">(0, 0)</span>, in the sense that there is no point with integer coordinates anywhere on the line segment between the origin and <span class="texhtml">(<i>a</i>, <i>b</i>)</span>. (See figure 1.) </p><p>In a sense that can be made precise, the <a href="/wiki/Probability" title="Probability">probability</a> that two randomly chosen integers are coprime is <span class="texhtml">6/<i>π</i><sup>2</sup></span>, which is about 61% (see <a href="#Probability_of_coprimality">§ Probability of coprimality</a>, below). </p><p>Two <a href="/wiki/Natural_number" title="Natural number">natural numbers</a> <span class="texhtml mvar" style="font-style:italic;">a</span> and <span class="texhtml mvar" style="font-style:italic;">b</span> are coprime if and only if the numbers <span class="texhtml">2<sup><i>a</i></sup> – 1</span> and <span class="texhtml">2<sup><i>b</i></sup> – 1</span> are coprime.<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> As a generalization of this, following easily from the <a href="/wiki/Euclidean_algorithm" title="Euclidean algorithm">Euclidean algorithm</a> in <a href="/wiki/Radix" title="Radix">base</a> <span class="texhtml"><i>n</i> > 1</span>: </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 \gcd \left(n^{a}-1,n^{b}-1\right)=n^{\gcd(a,b)}-1.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo movablelimits="true" form="prefix">gcd</mo> <mrow> <mo>(</mo> <mrow> <msup> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>a</mi> </mrow> </msup> <mo>−</mo> <mn>1</mn> <mo>,</mo> <msup> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>b</mi> </mrow> </msup> <mo>−</mo> <mn>1</mn> </mrow> <mo>)</mo> </mrow> <mo>=</mo> <msup> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mo movablelimits="true" form="prefix">gcd</mo> <mo stretchy="false">(</mo> <mi>a</mi> <mo>,</mo> <mi>b</mi> <mo stretchy="false">)</mo> </mrow> </msup> <mo>−</mo> <mn>1.</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \gcd \left(n^{a}-1,n^{b}-1\right)=n^{\gcd(a,b)}-1.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f959ad4ba8dc24b0beca66c78d262b73f02af813" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:35.026ex; height:3.509ex;" alt="{\displaystyle \gcd \left(n^{a}-1,n^{b}-1\right)=n^{\gcd(a,b)}-1.}"></span></dd></dl> <div class="mw-heading mw-heading2"><h2 id="Coprimality_in_sets">Coprimality in sets</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Coprime_integers&action=edit&section=3" title="Edit section: Coprimality in sets"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A <a href="/wiki/Set_(mathematics)" title="Set (mathematics)">set</a> of integers <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 S=\{a_{1},a_{2},\dots ,a_{n}\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>S</mi> <mo>=</mo> <mo fence="false" stretchy="false">{</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle S=\{a_{1},a_{2},\dots ,a_{n}\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d633d4cd568ca0488548070ee67fd15564c67bac" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.151ex; height:2.843ex;" alt="{\displaystyle S=\{a_{1},a_{2},\dots ,a_{n}\}}"></span> can also be called <i>coprime</i> or <i>setwise coprime</i> if the <a href="/wiki/Greatest_common_divisor" title="Greatest common divisor">greatest common divisor</a> of all the elements of the set is 1. For example, the integers 6, 10, 15 are coprime because 1 is the only positive integer that divides all of them. </p><p>If every pair in a set of integers is coprime, then the set is said to be <i>pairwise coprime</i> (or <i>pairwise relatively prime</i>, <i>mutually coprime</i> or <i>mutually relatively prime</i>). Pairwise coprimality is a stronger condition than setwise coprimality; every pairwise coprime finite set is also setwise coprime, but the reverse is not true. For example, the integers 4, 5, 6 are (setwise) coprime (because the only positive integer dividing <i>all</i> of them is 1), but they are not <i>pairwise</i> coprime (because <span class="texhtml">gcd(4, 6) = 2</span>). </p><p>The concept of pairwise coprimality is important as a hypothesis in many results in number theory, such as the <a href="/wiki/Chinese_remainder_theorem" title="Chinese remainder theorem">Chinese remainder theorem</a>. </p><p>It is possible for an <a href="/wiki/Infinite_set" title="Infinite set">infinite set</a> of integers to be pairwise coprime. Notable examples include the set of all prime numbers, the set of elements in <a href="/wiki/Sylvester%27s_sequence" title="Sylvester's sequence">Sylvester's sequence</a>, and the set of all <a href="/wiki/Fermat_numbers" class="mw-redirect" title="Fermat numbers">Fermat numbers</a>. </p> <div class="mw-heading mw-heading2"><h2 id="Coprimality_in_ring_ideals">Coprimality in ring ideals</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Coprime_integers&action=edit&section=4" title="Edit section: Coprimality in ring ideals"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Two <a href="/wiki/Ring_ideal" class="mw-redirect" title="Ring ideal">ideals</a> <span class="texhtml mvar" style="font-style:italic;">A</span> and <span class="texhtml mvar" style="font-style:italic;">B</span> in a <a href="/wiki/Commutative_ring" title="Commutative ring">commutative ring</a> <span class="texhtml mvar" style="font-style:italic;">R</span> are called coprime (or <i>comaximal</i>) 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 A+B=R.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>A</mi> <mo>+</mo> <mi>B</mi> <mo>=</mo> <mi>R</mi> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle A+B=R.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/93cf1d6f9870cf2c640386f3fc8ab88e4df40f84" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:11.857ex; height:2.343ex;" alt="{\displaystyle A+B=R.}"></span> This generalizes <a href="/wiki/B%C3%A9zout%27s_identity" title="Bézout's identity">Bézout's identity</a>: with this definition, two <a href="/wiki/Principal_ideal" title="Principal ideal">principal ideals</a> (<span class="texhtml mvar" style="font-style:italic;">a</span>) and (<span class="texhtml mvar" style="font-style:italic;">b</span>) in the ring of integers <span class="nowrap">⁠<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>⁠</span> are coprime if and only if <span class="texhtml mvar" style="font-style:italic;">a</span> and <span class="texhtml mvar" style="font-style:italic;">b</span> are coprime. If the ideals <span class="texhtml mvar" style="font-style:italic;">A</span> and <span class="texhtml mvar" style="font-style:italic;">B</span> of <span class="texhtml mvar" style="font-style:italic;">R</span> are coprime, 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 AB=A\cap B;}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>A</mi> <mi>B</mi> <mo>=</mo> <mi>A</mi> <mo>∩</mo> <mi>B</mi> <mo>;</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle AB=A\cap B;}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b9a28cc8b3a1ed8f77eae10368f7c56cb9b9e4ed" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.342ex; height:2.509ex;" alt="{\displaystyle AB=A\cap B;}"></span> furthermore, if <span class="texhtml mvar" style="font-style:italic;">C</span> is a third ideal such that <span class="texhtml mvar" style="font-style:italic;">A</span> contains <span class="texhtml mvar" style="font-style:italic;">BC</span>, then <span class="texhtml mvar" style="font-style:italic;">A</span> contains <span class="texhtml mvar" style="font-style:italic;">C</span>. The <a href="/wiki/Chinese_remainder_theorem" title="Chinese remainder theorem">Chinese remainder theorem</a> can be generalized to any commutative ring, using coprime ideals. </p> <div class="mw-heading mw-heading2"><h2 id="Probability_of_coprimality">Probability of coprimality</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Coprime_integers&action=edit&section=5" title="Edit section: Probability of coprimality"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Given two randomly chosen integers <span class="texhtml mvar" style="font-style:italic;">a</span> and <span class="texhtml mvar" style="font-style:italic;">b</span>, it is reasonable to ask how likely it is that <span class="texhtml mvar" style="font-style:italic;">a</span> and <span class="texhtml mvar" style="font-style:italic;">b</span> are coprime. In this determination, it is convenient to use the characterization that <span class="texhtml mvar" style="font-style:italic;">a</span> and <span class="texhtml mvar" style="font-style:italic;">b</span> are coprime if and only if no prime number divides both of them (see <a href="/wiki/Fundamental_theorem_of_arithmetic" title="Fundamental theorem of arithmetic">Fundamental theorem of arithmetic</a>). </p><p>Informally, the probability that any number is divisible by a prime (or in fact any integer) <span class="texhtml mvar" style="font-style:italic;">p</span> is <span class="nowrap">⁠<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 {\tfrac {1}{p}};}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mfrac> <mn>1</mn> <mi>p</mi> </mfrac> </mstyle> </mrow> <mo>;</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\tfrac {1}{p}};}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c27dfa186027e6ad28104fa36f6051faf44a6cd2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:2.31ex; height:3.676ex;" alt="{\displaystyle {\tfrac {1}{p}};}"></span>⁠</span> for example, every 7th integer is divisible by 7. Hence the probability that two numbers are both divisible by <span class="texhtml mvar" style="font-style:italic;">p</span> is <span class="nowrap">⁠<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 {\tfrac {1}{p^{2}}},}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mfrac> <mn>1</mn> <msup> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </mfrac> </mstyle> </mrow> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\tfrac {1}{p^{2}}},}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/49adb1c30fa3e820968e92c90d0a65f8f429ac09" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:3.141ex; height:4.176ex;" alt="{\displaystyle {\tfrac {1}{p^{2}}},}"></span>⁠</span> and the probability that at least one of them is not is <span class="nowrap">⁠<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-{\tfrac {1}{p^{2}}}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>1</mn> <mo>−</mo> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mfrac> <mn>1</mn> <msup> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </mfrac> </mstyle> </mrow> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 1-{\tfrac {1}{p^{2}}}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/05c35d24582249548462b5cff77ca1651d3ca76e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:7.144ex; height:4.176ex;" alt="{\displaystyle 1-{\tfrac {1}{p^{2}}}.}"></span>⁠</span> Any finite collection of divisibility events associated to distinct primes is mutually independent. For example, in the case of two events, a number is divisible by primes <span class="texhtml mvar" style="font-style:italic;">p</span> and <span class="texhtml mvar" style="font-style:italic;">q</span> if and only if it is divisible by <span class="texhtml mvar" style="font-style:italic;">pq</span>; the latter event has probability <span class="nowrap">⁠<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 {\tfrac {1}{pq}}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mfrac> <mn>1</mn> <mrow> <mi>p</mi> <mi>q</mi> </mrow> </mfrac> </mstyle> </mrow> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\tfrac {1}{pq}}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5b3844b7ac3f423ed00898ecab9ef4ea2cfaee23" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:3.066ex; height:3.676ex;" alt="{\displaystyle {\tfrac {1}{pq}}.}"></span>⁠</span> If one makes the heuristic assumption that such reasoning can be extended to infinitely many divisibility events, one is led to guess that the probability that two numbers are coprime is given by a product over all primes, </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 \prod _{{\text{prime }}p}\left(1-{\frac {1}{p^{2}}}\right)=\left(\prod _{{\text{prime }}p}{\frac {1}{1-p^{-2}}}\right)^{-1}={\frac {1}{\zeta (2)}}={\frac {6}{\pi ^{2}}}\approx 0.607927102\approx 61\%.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <munder> <mo>∏</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mtext>prime </mtext> </mrow> <mi>p</mi> </mrow> </munder> <mrow> <mo>(</mo> <mrow> <mn>1</mn> <mo>−</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <msup> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </mfrac> </mrow> </mrow> <mo>)</mo> </mrow> <mo>=</mo> <msup> <mrow> <mo>(</mo> <mrow> <munder> <mo>∏</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mtext>prime </mtext> </mrow> <mi>p</mi> </mrow> </munder> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <mrow> <mn>1</mn> <mo>−</mo> <msup> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>2</mn> </mrow> </msup> </mrow> </mfrac> </mrow> </mrow> <mo>)</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <mrow> <mi>ζ</mi> <mo stretchy="false">(</mo> <mn>2</mn> <mo stretchy="false">)</mo> </mrow> </mfrac> </mrow> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>6</mn> <msup> <mi>π</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </mfrac> </mrow> <mo>≈</mo> <mn>0.607927102</mn> <mo>≈</mo> <mn>61</mn> <mi mathvariant="normal">%</mi> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \prod _{{\text{prime }}p}\left(1-{\frac {1}{p^{2}}}\right)=\left(\prod _{{\text{prime }}p}{\frac {1}{1-p^{-2}}}\right)^{-1}={\frac {1}{\zeta (2)}}={\frac {6}{\pi ^{2}}}\approx 0.607927102\approx 61\%.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d3235f824d17b2a7f462456e39edf14461842e33" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:77.457ex; height:8.176ex;" alt="{\displaystyle \prod _{{\text{prime }}p}\left(1-{\frac {1}{p^{2}}}\right)=\left(\prod _{{\text{prime }}p}{\frac {1}{1-p^{-2}}}\right)^{-1}={\frac {1}{\zeta (2)}}={\frac {6}{\pi ^{2}}}\approx 0.607927102\approx 61\%.}"></span></dd></dl> <p>Here <span class="texhtml mvar" style="font-style:italic;">ζ</span> refers to the <a href="/wiki/Riemann_zeta_function" title="Riemann zeta function">Riemann zeta function</a>, the identity relating the product over primes to <span class="texhtml"><i>ζ</i>(2)</span> is an example of an <a href="/wiki/Euler_product" title="Euler product">Euler product</a>, and the evaluation of <span class="texhtml"><i>ζ</i>(2)</span> as <span class="texhtml"><i>π</i><sup>2</sup>/6</span> is the <a href="/wiki/Basel_problem" title="Basel problem">Basel problem</a>, solved by <a href="/wiki/Leonhard_Euler" title="Leonhard Euler">Leonhard Euler</a> in 1735. </p><p>There is no way to choose a positive integer at random so that each positive integer occurs with equal probability, but statements about "randomly chosen integers" such as the ones above can be formalized by using the notion of <i><a href="/wiki/Natural_density" title="Natural density">natural density</a></i>. For each positive integer <span class="texhtml mvar" style="font-style:italic;">N</span>, let <span class="texhtml mvar" style="font-style:italic;">P<sub>N</sub></span> be the probability that two randomly chosen numbers 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 \{1,2,\ldots ,N\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">{</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo>,</mo> <mo>…</mo> <mo>,</mo> <mi>N</mi> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \{1,2,\ldots ,N\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/18d7b4ef5cabdf43044424420855eeaf363f0c09" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.926ex; height:2.843ex;" alt="{\displaystyle \{1,2,\ldots ,N\}}"></span> are coprime. Although <span class="texhtml mvar" style="font-style:italic;">P<sub>N</sub></span> will never equal <span class="texhtml">6/<i>π</i><sup>2</sup></span> exactly, with work<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> one can show that in the limit as <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\to \infty ,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> <mo stretchy="false">→</mo> <mi mathvariant="normal">∞</mi> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle N\to \infty ,}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/071a87e26bf1c08e37234ca32087f6c88fe66612" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.648ex; height:2.509ex;" alt="{\displaystyle N\to \infty ,}"></span> the probability <span class="texhtml mvar" style="font-style:italic;">P<sub>N</sub></span> approaches <span class="texhtml">6/<i>π</i><sup>2</sup></span>. </p><p>More generally, the probability of <span class="texhtml mvar" style="font-style:italic;">k</span> randomly chosen integers being setwise coprime is <span class="nowrap">⁠<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 {\tfrac {1}{\zeta (k)}}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mfrac> <mn>1</mn> <mrow> <mi>ζ</mi> <mo stretchy="false">(</mo> <mi>k</mi> <mo stretchy="false">)</mo> </mrow> </mfrac> </mstyle> </mrow> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\tfrac {1}{\zeta (k)}}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f34435a74a3e39594c3808ed084a36c04e22985c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:4.393ex; height:4.176ex;" alt="{\displaystyle {\tfrac {1}{\zeta (k)}}.}"></span>⁠</span> </p> <div class="mw-heading mw-heading2"><h2 id="Generating_all_coprime_pairs">Generating all coprime pairs</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Coprime_integers&action=edit&section=6" title="Edit section: Generating all coprime pairs"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure typeof="mw:File/Thumb"><a href="/wiki/File:Coprime8.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/2/26/Coprime8.svg/300px-Coprime8.svg.png" decoding="async" width="300" height="301" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/2/26/Coprime8.svg/450px-Coprime8.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/2/26/Coprime8.svg/600px-Coprime8.svg.png 2x" data-file-width="450" data-file-height="451" /></a><figcaption>The <a href="/wiki/Rooted_tree" class="mw-redirect" title="Rooted tree">tree rooted</a> at (2, 1). The root (2, 1) is marked red, its three children are shown in orange, third generation is yellow, and so on in the rainbow order.</figcaption></figure> <p>All pairs of positive coprime numbers <span class="texhtml">(<i>m</i>, <i>n</i>)</span> (with <span class="texhtml"><i>m</i> > <i>n</i></span>) can be arranged in two disjoint complete <a href="/wiki/Ternary_tree" title="Ternary tree">ternary trees</a>, one tree starting from <span class="texhtml">(2, 1)</span> (for even–odd and odd–even pairs),<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> and the other tree starting from <span class="texhtml">(3, 1)</span> (for odd–odd pairs).<sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> The children of each vertex <span class="texhtml">(<i>m</i>, <i>n</i>)</span> are generated as follows: </p> <ul><li>Branch 1: <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 (2m-n,m)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mn>2</mn> <mi>m</mi> <mo>−</mo> <mi>n</mi> <mo>,</mo> <mi>m</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (2m-n,m)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2cdcf49df3787a641f10801acc5e3cc2d53065fe" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.322ex; height:2.843ex;" alt="{\displaystyle (2m-n,m)}"></span></li> <li>Branch 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 (2m+n,m)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mn>2</mn> <mi>m</mi> <mo>+</mo> <mi>n</mi> <mo>,</mo> <mi>m</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (2m+n,m)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1844599974cb8b09ab645e5b15af8ab43450de80" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.322ex; height:2.843ex;" alt="{\displaystyle (2m+n,m)}"></span></li> <li>Branch 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 (m+2n,n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>m</mi> <mo>+</mo> <mn>2</mn> <mi>n</mi> <mo>,</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (m+2n,n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/223746ae0c1800e511ca525b077c2fbb61e64196" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.676ex; height:2.843ex;" alt="{\displaystyle (m+2n,n)}"></span></li></ul> <p>This scheme is exhaustive and non-redundant with no invalid members. This can be proved by remarking 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 (a,b)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>a</mi> <mo>,</mo> <mi>b</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (a,b)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d7e5710198f33b00695903460983021e75860e2c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.071ex; height:2.843ex;" alt="{\displaystyle (a,b)}"></span> is a coprime pair with <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>b,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>a</mi> <mo>></mo> <mi>b</mi> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a>b,}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d6d8ca5031f98a774d037e63bfc4296c44d41d6e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.973ex; height:2.509ex;" alt="{\displaystyle a>b,}"></span> then </p> <ul><li>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 a>3b,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>a</mi> <mo>></mo> <mn>3</mn> <mi>b</mi> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a>3b,}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fb305803bc43966f201697266e6fea2df4908651" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.135ex; height:2.509ex;" alt="{\displaystyle a>3b,}"></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 (a,b)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>a</mi> <mo>,</mo> <mi>b</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (a,b)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d7e5710198f33b00695903460983021e75860e2c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.071ex; height:2.843ex;" alt="{\displaystyle (a,b)}"></span> is a child 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 (m,n)=(a-2b,b)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>m</mi> <mo>,</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mo stretchy="false">(</mo> <mi>a</mi> <mo>−</mo> <mn>2</mn> <mi>b</mi> <mo>,</mo> <mi>b</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (m,n)=(a-2b,b)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/48296a4a12ba0ab87b56016bcb3606ec27fce823" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.448ex; height:2.843ex;" alt="{\displaystyle (m,n)=(a-2b,b)}"></span> along branch 3;</li> <li>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 2b<a<3b,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>2</mn> <mi>b</mi> <mo><</mo> <mi>a</mi> <mo><</mo> <mn>3</mn> <mi>b</mi> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 2b<a<3b,}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4316284f9f44e2429b79f6154bd489e87d5badab" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.394ex; height:2.509ex;" alt="{\displaystyle 2b<a<3b,}"></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 (a,b)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>a</mi> <mo>,</mo> <mi>b</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (a,b)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d7e5710198f33b00695903460983021e75860e2c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.071ex; height:2.843ex;" alt="{\displaystyle (a,b)}"></span> is a child 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 (m,n)=(b,a-2b)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>m</mi> <mo>,</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mo stretchy="false">(</mo> <mi>b</mi> <mo>,</mo> <mi>a</mi> <mo>−</mo> <mn>2</mn> <mi>b</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (m,n)=(b,a-2b)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1531d69ebe0379243a2f886b8e631a9c962dfdf2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.448ex; height:2.843ex;" alt="{\displaystyle (m,n)=(b,a-2b)}"></span> along branch 2;</li> <li>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 b<a<2b,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>b</mi> <mo><</mo> <mi>a</mi> <mo><</mo> <mn>2</mn> <mi>b</mi> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle b<a<2b,}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/25a82de670f7773626a0a3cba711484050f001cb" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.231ex; height:2.509ex;" alt="{\displaystyle b<a<2b,}"></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 (a,b)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>a</mi> <mo>,</mo> <mi>b</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (a,b)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d7e5710198f33b00695903460983021e75860e2c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.071ex; height:2.843ex;" alt="{\displaystyle (a,b)}"></span> is a child 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 (m,n)=(b,2b-a)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>m</mi> <mo>,</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mo stretchy="false">(</mo> <mi>b</mi> <mo>,</mo> <mn>2</mn> <mi>b</mi> <mo>−</mo> <mi>a</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (m,n)=(b,2b-a)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b467fd184e24dcfadcea4236af86d3a12ee9eb3f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.448ex; height:2.843ex;" alt="{\displaystyle (m,n)=(b,2b-a)}"></span> along branch 1.</li></ul> <p>In all cases <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 (m,n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>m</mi> <mo>,</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (m,n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/274d4857135a7d28a94ba9ee8135779615084d43" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.278ex; height:2.843ex;" alt="{\displaystyle (m,n)}"></span> is a "smaller" coprime pair with <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 m>n.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>m</mi> <mo>></mo> <mi>n</mi> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle m>n.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/982733f442459689d943182858c50d3942aaa764" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.18ex; height:1.843ex;" alt="{\displaystyle m>n.}"></span> This process of "computing the father" can stop only if either <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=2b}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>a</mi> <mo>=</mo> <mn>2</mn> <mi>b</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a=2b}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/14d4845a1fcfa12abf34e6ebb325b09b4603d4a9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.488ex; height:2.176ex;" alt="{\displaystyle a=2b}"></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 a=3b.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>a</mi> <mo>=</mo> <mn>3</mn> <mi>b</mi> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a=3b.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/42611687b3456c2c52d3c44cc74de767ffc55041" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.135ex; height:2.176ex;" alt="{\displaystyle a=3b.}"></span> In these cases, coprimality, implies that the pair is either <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,1)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mn>2</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (2,1)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f035f80fd643b702206b4e4f9ed87d458a5826af" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.168ex; height:2.843ex;" alt="{\displaystyle (2,1)}"></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 (3,1).}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mn>3</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (3,1).}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fafc3944b2efa11d4e9f813a4bb7332c83ad0b4e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.815ex; height:2.843ex;" alt="{\displaystyle (3,1).}"></span> </p><p>Another (much simpler) way to generate a tree of positive coprime pairs <span class="texhtml">(<i>m</i>, <i>n</i>)</span> (with <span class="texhtml"><i>m</i> > <i>n</i></span>) is by means of two generators <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 f:(m,n)\rightarrow (m+n,n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> <mo>:</mo> <mo stretchy="false">(</mo> <mi>m</mi> <mo>,</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo stretchy="false">→</mo> <mo stretchy="false">(</mo> <mi>m</mi> <mo>+</mo> <mi>n</mi> <mo>,</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f:(m,n)\rightarrow (m+n,n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/61a726658f8168a2be7d9ba692c3db9801fef875" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.622ex; height:2.843ex;" alt="{\displaystyle f:(m,n)\rightarrow (m+n,n)}"></span> and <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:(m,n)\rightarrow (m+n,m)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>g</mi> <mo>:</mo> <mo stretchy="false">(</mo> <mi>m</mi> <mo>,</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo stretchy="false">→</mo> <mo stretchy="false">(</mo> <mi>m</mi> <mo>+</mo> <mi>n</mi> <mo>,</mo> <mi>m</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle g:(m,n)\rightarrow (m+n,m)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4e9591d2c729479e95d595d0ddbed42f9ae473bb" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.105ex; height:2.843ex;" alt="{\displaystyle g:(m,n)\rightarrow (m+n,m)}"></span>, starting with the root <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,1)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mn>2</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (2,1)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f035f80fd643b702206b4e4f9ed87d458a5826af" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.168ex; height:2.843ex;" alt="{\displaystyle (2,1)}"></span>. The resulting binary tree, the <a href="/wiki/Calkin%E2%80%93Wilf_tree" title="Calkin–Wilf tree">Calkin–Wilf tree</a>, is exhaustive and non-redundant, which can be seen as follows. Given a coprime pair one recursively applies <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 f^{-1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>f</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f^{-1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3e5cfa2f5c08d6fe7d046b73faa6e3f213acc802" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.653ex; height:3.009ex;" alt="{\displaystyle f^{-1}}"></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 g^{-1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>g</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle g^{-1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8ae77eeb0200a3b0e26ff4b251fb845ca1b385c3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.451ex; height:3.009ex;" alt="{\displaystyle g^{-1}}"></span> depending on which of them yields a positive coprime pair with <span class="texhtml"><i>m</i> > <i>n</i></span>. Since only one does, the tree is non-redundant. Since by this procedure one is bound to arrive at the root, the tree is exhaustive. </p> <div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Coprime_integers&action=edit&section=7" title="Edit section: Applications"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>In machine design, an even, uniform <a href="/wiki/Gear" title="Gear">gear</a> wear is achieved by choosing the tooth counts of the two gears meshing together to be relatively prime. When a 1:1 <a href="/wiki/Gear_train" title="Gear train">gear ratio</a> is desired, a gear relatively prime to the two equal-size gears may be inserted between them. </p><p>In pre-computer <a href="/wiki/Cryptography" title="Cryptography">cryptography</a>, some <a href="/wiki/Vernam_cipher" class="mw-redirect" title="Vernam cipher">Vernam cipher</a> machines combined several loops of key tape of different lengths. Many <a href="/wiki/Rotor_machine" title="Rotor machine">rotor machines</a> combine rotors of different numbers of teeth. Such combinations work best when the entire set of lengths are pairwise coprime.<sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-13" class="reference"><a href="#cite_note-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-14" class="reference"><a href="#cite_note-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-15" class="reference"><a href="#cite_note-15"><span class="cite-bracket">[</span>15<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Generalizations">Generalizations</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Coprime_integers&action=edit&section=8" title="Edit section: Generalizations"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>This concept can be extended to other algebraic structures than <span class="nowrap">⁠<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> <mo>;</mo> </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/237089e243508123c48781cce997626d9c012e7c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.197ex; height:2.509ex;" alt="{\displaystyle \mathbb {Z} ;}"></span>⁠</span> for example, <a href="/wiki/Polynomial" title="Polynomial">polynomials</a> whose <a href="/wiki/Polynomial_greatest_common_divisor" title="Polynomial greatest common divisor">greatest common divisor</a> is 1 are called <a href="/wiki/Coprime_polynomials" class="mw-redirect" title="Coprime polynomials">coprime polynomials</a>. </p> <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=Coprime_integers&action=edit&section=9" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1235681985">.mw-parser-output .side-box{margin:4px 0;box-sizing:border-box;border:1px solid #aaa;font-size:88%;line-height:1.25em;background-color:var(--background-color-interactive-subtle,#f8f9fa);display:flow-root}.mw-parser-output .side-box-abovebelow,.mw-parser-output .side-box-text{padding:0.25em 0.9em}.mw-parser-output .side-box-image{padding:2px 0 2px 0.9em;text-align:center}.mw-parser-output .side-box-imageright{padding:2px 0.9em 2px 0;text-align:center}@media(min-width:500px){.mw-parser-output .side-box-flex{display:flex;align-items:center}.mw-parser-output .side-box-text{flex:1;min-width:0}}@media(min-width:720px){.mw-parser-output .side-box{width:238px}.mw-parser-output .side-box-right{clear:right;float:right;margin-left:1em}.mw-parser-output .side-box-left{margin-right:1em}}</style><style data-mw-deduplicate="TemplateStyles:r1237033735">@media print{body.ns-0 .mw-parser-output .sistersitebox{display:none!important}}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}</style><div class="side-box side-box-right plainlinks sistersitebox"><style data-mw-deduplicate="TemplateStyles:r1126788409">.mw-parser-output .plainlist ol,.mw-parser-output .plainlist ul{line-height:inherit;list-style:none;margin:0;padding:0}.mw-parser-output .plainlist ol li,.mw-parser-output .plainlist ul li{margin-bottom:0}</style> <div class="side-box-flex"> <div class="side-box-image"><span class="noviewer" typeof="mw:File"><span><img alt="" src="//upload.wikimedia.org/wikipedia/commons/thumb/9/99/Wiktionary-logo-en-v2.svg/40px-Wiktionary-logo-en-v2.svg.png" decoding="async" width="40" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/9/99/Wiktionary-logo-en-v2.svg/60px-Wiktionary-logo-en-v2.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/9/99/Wiktionary-logo-en-v2.svg/80px-Wiktionary-logo-en-v2.svg.png 2x" data-file-width="512" data-file-height="512" /></span></span></div> <div class="side-box-text plainlist">Look up <i><b><a href="https://en.wiktionary.org/wiki/coprime" class="extiw" title="wiktionary:coprime">coprime</a></b></i> in Wiktionary, the free dictionary.</div></div> </div> <ul><li><a href="/wiki/Euclid%27s_orchard" title="Euclid's orchard">Euclid's orchard</a></li> <li><a href="/wiki/Superpartient_number" class="mw-redirect" title="Superpartient number">Superpartient number</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=Coprime_integers&action=edit&section=10" 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 mw-references-columns"><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"><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="CITEREFEaton1872" class="citation book cs1">Eaton, James S. (1872). <a rel="nofollow" class="external text" href="https://archive.org/details/atreatiseonarit05eatogoog"><i>A Treatise on Arithmetic</i></a>. Boston: Thompson, Bigelow & Brown. p. 49<span class="reference-accessdate">. Retrieved <span class="nowrap">10 January</span> 2022</span>. <q>Two numbers are <i>mutually</i> prime when no whole number but <i>one</i> will divide each of them</q></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=A+Treatise+on+Arithmetic&rft.place=Boston&rft.pages=49&rft.pub=Thompson%2C+Bigelow+%26+Brown&rft.date=1872&rft.aulast=Eaton&rft.aufirst=James+S.&rft_id=https%3A%2F%2Farchive.org%2Fdetails%2Fatreatiseonarit05eatogoog&rfr_id=info%3Asid%2Fen.wikipedia.org%3ACoprime+integers" class="Z3988"></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"><a href="#CITEREFHardyWright2008">Hardy & Wright 2008</a>, p. 6</span> </li> <li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFGrahamKnuthPatashnik1989" class="citation cs2">Graham, R. L.; Knuth, D. E.; Patashnik, O. (1989), <i><a href="/wiki/Concrete_Mathematics" title="Concrete Mathematics">Concrete Mathematics</a> / A Foundation for Computer Science</i>, Addison-Wesley, p. 115, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-201-14236-8" title="Special:BookSources/0-201-14236-8"><bdi>0-201-14236-8</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Concrete+Mathematics+%2F+A+Foundation+for+Computer+Science&rft.pages=115&rft.pub=Addison-Wesley&rft.date=1989&rft.isbn=0-201-14236-8&rft.aulast=Graham&rft.aufirst=R.+L.&rft.au=Knuth%2C+D.+E.&rft.au=Patashnik%2C+O.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ACoprime+integers" class="Z3988"></span></span> </li> <li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><a href="#CITEREFOre1988">Ore 1988</a>, p. 47</span> </li> <li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><a href="#CITEREFNivenZuckerman1966">Niven & Zuckerman 1966</a>, p. 22, Theorem 2.3(b)</span> </li> <li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><a href="#CITEREFNivenZuckerman1966">Niven & Zuckerman 1966</a>, p. 6, Theorem 1.8</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"><a href="#CITEREFNivenZuckerman1966">Niven & Zuckerman 1966</a>, p.7, Theorem 1.10</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"><a href="#CITEREFRosen1992">Rosen 1992</a>, p. 140</span> </li> <li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text">This theorem was proved by <a href="/wiki/Ernesto_Ces%C3%A0ro" title="Ernesto Cesàro">Ernesto Cesàro</a> in 1881. For a proof, see <a href="#CITEREFHardyWright2008">Hardy & Wright 2008</a>, Theorem 332</span> </li> <li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFSaundersRandall1994" class="citation cs2">Saunders, Robert & Randall, Trevor (July 1994), "The family tree of the Pythagorean triplets revisited", <i>Mathematical Gazette</i>, <b>78</b>: 190–193, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F3618576">10.2307/3618576</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Mathematical+Gazette&rft.atitle=The+family+tree+of+the+Pythagorean+triplets+revisited&rft.volume=78&rft.pages=190-193&rft.date=1994-07&rft_id=info%3Adoi%2F10.2307%2F3618576&rft.aulast=Saunders&rft.aufirst=Robert&rft.au=Randall%2C+Trevor&rfr_id=info%3Asid%2Fen.wikipedia.org%3ACoprime+integers" class="Z3988"></span>.</span> </li> <li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFMitchell2001" class="citation cs2">Mitchell, Douglas W. (July 2001), "An alternative characterisation of all primitive Pythagorean triples", <i>Mathematical Gazette</i>, <b>85</b>: 273–275, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F3622017">10.2307/3622017</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Mathematical+Gazette&rft.atitle=An+alternative+characterisation+of+all+primitive+Pythagorean+triples&rft.volume=85&rft.pages=273-275&rft.date=2001-07&rft_id=info%3Adoi%2F10.2307%2F3622017&rft.aulast=Mitchell&rft.aufirst=Douglas+W.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ACoprime+integers" class="Z3988"></span>.</span> </li> <li id="cite_note-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-12">^</a></b></span> <span class="reference-text"> Klaus Pommerening. <a rel="nofollow" class="external text" href="https://www.staff.uni-mainz.de/pommeren/Cryptology/Classic/4_Cylinder/LongPeriods.html">"Cryptology: Key Generators with Long Periods"</a>.</span> </li> <li id="cite_note-13"><span class="mw-cite-backlink"><b><a href="#cite_ref-13">^</a></b></span> <span class="reference-text"> David Mowry. <a rel="nofollow" class="external text" href="https://www.nsa.gov/Portals/70/documents/about/cryptologic-heritage/historical-figures-publications/publications/wwii/german_cipher.pdf">"German Cipher Machines of World War II"</a>. 2014. p. 16; p. 22.</span> </li> <li id="cite_note-14"><span class="mw-cite-backlink"><b><a href="#cite_ref-14">^</a></b></span> <span class="reference-text"> Dirk Rijmenants. <a rel="nofollow" class="external text" href="https://www.ciphermachinesandcryptology.com/en/onetimepad.htm">"Origins of One-time pad"</a>.</span> </li> <li id="cite_note-15"><span class="mw-cite-backlink"><b><a href="#cite_ref-15">^</a></b></span> <span class="reference-text"> Gustavus J. Simmons. <a rel="nofollow" class="external text" href="https://www.britannica.com/topic/Vernam-Vigenere-cipher">"Vernam-Vigenère cipher"</a>.</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=Coprime_integers&action=edit&section=11" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFHardyWright2008" class="citation cs2"><a href="/wiki/G._H._Hardy" title="G. H. Hardy">Hardy, G.H.</a>; <a href="/wiki/E._M._Wright" title="E. M. Wright">Wright, E.M.</a> (2008), <i>An Introduction to the Theory of Numbers</i> (6th ed.), <a href="/wiki/Oxford_University_Press" title="Oxford University Press">Oxford University Press</a>, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-19-921986-5" title="Special:BookSources/978-0-19-921986-5"><bdi>978-0-19-921986-5</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=An+Introduction+to+the+Theory+of+Numbers&rft.edition=6th&rft.pub=Oxford+University+Press&rft.date=2008&rft.isbn=978-0-19-921986-5&rft.aulast=Hardy&rft.aufirst=G.H.&rft.au=Wright%2C+E.M.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ACoprime+integers" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFNivenZuckerman1966" class="citation cs2">Niven, Ivan; Zuckerman, Herbert S. (1966), <i>An Introduction to the Theory of Numbers</i> (2nd ed.), John Wiley & Sons</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=An+Introduction+to+the+Theory+of+Numbers&rft.edition=2nd&rft.pub=John+Wiley+%26+Sons&rft.date=1966&rft.aulast=Niven&rft.aufirst=Ivan&rft.au=Zuckerman%2C+Herbert+S.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ACoprime+integers" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFOre1988" class="citation cs2">Ore, Oystein (1988) [1948], <i>Number Theory and Its History</i>, Dover, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-486-65620-5" title="Special:BookSources/978-0-486-65620-5"><bdi>978-0-486-65620-5</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Number+Theory+and+Its+History&rft.pub=Dover&rft.date=1988&rft.isbn=978-0-486-65620-5&rft.aulast=Ore&rft.aufirst=Oystein&rfr_id=info%3Asid%2Fen.wikipedia.org%3ACoprime+integers" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFRosen1992" class="citation cs2">Rosen, Kenneth H. (1992), <i>Elementary Number Theory and its Applications</i> (3rd ed.), Addison-Wesley, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-201-57889-8" title="Special:BookSources/978-0-201-57889-8"><bdi>978-0-201-57889-8</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Elementary+Number+Theory+and+its+Applications&rft.edition=3rd&rft.pub=Addison-Wesley&rft.date=1992&rft.isbn=978-0-201-57889-8&rft.aulast=Rosen&rft.aufirst=Kenneth+H.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ACoprime+integers" class="Z3988"></span></li></ul> <div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Coprime_integers&action=edit&section=12" title="Edit section: Further reading"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFLord2008" class="citation cs2">Lord, Nick (March 2008), "A uniform construction of some infinite coprime sequences", <i>Mathematical Gazette</i>, <b>92</b>: 66–70</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Mathematical+Gazette&rft.atitle=A+uniform+construction+of+some+infinite+coprime+sequences&rft.volume=92&rft.pages=66-70&rft.date=2008-03&rft.aulast=Lord&rft.aufirst=Nick&rfr_id=info%3Asid%2Fen.wikipedia.org%3ACoprime+integers" class="Z3988"></span>.</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=Coprime_integers&oldid=1252719665">https://en.wikipedia.org/w/index.php?title=Coprime_integers&oldid=1252719665</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">Category</a>: <ul><li><a href="/wiki/Category:Number_theory" title="Category:Number theory">Number theory</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_is_different_from_Wikidata" title="Category:Short description is different from Wikidata">Short description is different from 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 22 October 2024, at 17:20<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=Coprime_integers&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.canary-78796dc7ff-fngt4","wgBackendResponseTime":159,"wgPageParseReport":{"limitreport":{"cputime":"0.392","walltime":"0.532","ppvisitednodes":{"value":3452,"limit":1000000},"postexpandincludesize":{"value":29654,"limit":2097152},"templateargumentsize":{"value":3692,"limit":2097152},"expansiondepth":{"value":9,"limit":100},"expensivefunctioncount":{"value":1,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":33233,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 383.938 1 -total"," 43.29% 166.200 1 Template:Reflist"," 23.57% 90.494 1 Template:Cite_book"," 19.82% 76.089 1 Template:Short_description"," 13.00% 49.929 2 Template:Pagetype"," 11.43% 43.871 8 Template:Citation"," 10.26% 39.395 7 Template:Harvnb"," 9.93% 38.126 35 Template:Math"," 8.87% 34.038 1 Template:Wiktionary"," 8.34% 32.036 1 Template:Sister_project"]},"scribunto":{"limitreport-timeusage":{"value":"0.198","limit":"10.000"},"limitreport-memusage":{"value":7149357,"limit":52428800},"limitreport-logs":"anchor_id_list = table#1 {\n [\"CITEREFEaton1872\"] = 1,\n [\"CITEREFGrahamKnuthPatashnik1989\"] = 1,\n [\"CITEREFHardyWright2008\"] = 1,\n [\"CITEREFLord2008\"] = 1,\n [\"CITEREFMitchell2001\"] = 1,\n [\"CITEREFNivenZuckerman1966\"] = 1,\n [\"CITEREFOre1988\"] = 1,\n [\"CITEREFRosen1992\"] = 1,\n [\"CITEREFSaundersRandall1994\"] = 1,\n}\ntemplate_list = table#1 {\n [\"Citation\"] = 8,\n [\"Cite book\"] = 1,\n [\"Harvnb\"] = 7,\n [\"Math\"] = 35,\n [\"Mvar\"] = 89,\n [\"Reflist\"] = 1,\n [\"Short description\"] = 1,\n [\"Slink\"] = 1,\n [\"Sub\"] = 3,\n [\"Tmath\"] = 8,\n [\"Wiktionary\"] = 1,\n}\narticle_whitelist = table#1 {\n}\n"},"cachereport":{"origin":"mw-web.codfw.main-6b7f745dd4-8h7r2","timestamp":"20241125133430","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Coprime integers","url":"https:\/\/en.wikipedia.org\/wiki\/Coprime_integers","sameAs":"http:\/\/www.wikidata.org\/entity\/Q104752","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q104752","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":"2001-09-26T22:47:21Z","dateModified":"2024-10-22T17:20:14Z","headline":"two numbers whose only common factor is 1"}</script> </body> </html>