CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-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-sticky-header-enabled vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Euler pseudoprime - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-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-sticky-header-enabled 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":"ae868b15-1e50-4155-80da-897985aef406","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Euler_pseudoprime","wgTitle":"Euler pseudoprime","wgCurRevisionId":1257754025,"wgRevisionId":1257754025,"wgArticleId":225261,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Articles with short description","Short description matches Wikidata","Pseudoprimes"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Euler_pseudoprime","wgRelevantArticleId":225261,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}}, "wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":10000,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q356653","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready", "user.options":"loading","ext.math.styles":"ready","ext.cite.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","jquery.makeCollapsible.styles":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","site","mediawiki.page.ready","jquery.makeCollapsible","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions", "wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=en&modules=ext.cite.styles%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cext.wikimediamessages.styles%7Cjquery.makeCollapsible.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.17"> <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="Euler pseudoprime - 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/Euler_pseudoprime"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Euler_pseudoprime&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/Euler_pseudoprime"> <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-Euler_pseudoprime rootpage-Euler_pseudoprime 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" title="Main menu" > <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><li id="n-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages"><span>Special pages</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/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=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=Euler+pseudoprime" 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=Euler+pseudoprime" 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/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=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=Euler+pseudoprime" 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=Euler+pseudoprime" 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-Relation_to_Euler–Jacobi_pseudoprimes" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Relation_to_Euler–Jacobi_pseudoprimes"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Relation to Euler–Jacobi pseudoprimes</span> </div> </a> <ul id="toc-Relation_to_Euler–Jacobi_pseudoprimes-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Implementation_in_Lua" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Implementation_in_Lua"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Implementation in Lua</span> </div> </a> <ul id="toc-Implementation_in_Lua-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Examples" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Examples"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Examples</span> </div> </a> <ul id="toc-Examples-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Least_Euler_pseudoprime_to_base_n" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Least_Euler_pseudoprime_to_base_n"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Least Euler pseudoprime to base <i>n</i></span> </div> </a> <ul id="toc-Least_Euler_pseudoprime_to_base_n-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">5</span> <span>See also</span> </div> </a> <ul id="toc-See_also-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">6</span> <span>References</span> </div> </a> <ul id="toc-References-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" title="Table of Contents" > <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">Euler pseudoprime</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 5 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-5" 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">5 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Eulersche_Pseudoprimzahl" title="Eulersche Pseudoprimzahl – German" lang="de" hreflang="de" data-title="Eulersche Pseudoprimzahl" data-language-autonym="Deutsch" data-language-local-name="German" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/N%C3%BAmero_pseudoprimo_de_Euler" title="Número pseudoprimo de Euler – Spanish" lang="es" hreflang="es" data-title="Número pseudoprimo de Euler" 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-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/Nombre_pseudo-premier_d%27Euler" title="Nombre pseudo-premier d'Euler – French" lang="fr" hreflang="fr" data-title="Nombre pseudo-premier d'Euler" 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-it mw-list-item"><a href="https://it.wikipedia.org/wiki/Pseudoprimo_di_Eulero" title="Pseudoprimo di Eulero – Italian" lang="it" hreflang="it" data-title="Pseudoprimo di Eulero" data-language-autonym="Italiano" data-language-local-name="Italian" class="interlanguage-link-target"><span>Italiano</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E6%AC%A7%E6%8B%89%E4%BC%AA%E7%B4%A0%E6%95%B0" 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/Q356653#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/Euler_pseudoprime" 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:Euler_pseudoprime" 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/Euler_pseudoprime"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Euler_pseudoprime&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=Euler_pseudoprime&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/Euler_pseudoprime"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Euler_pseudoprime&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=Euler_pseudoprime&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/Euler_pseudoprime" 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/Euler_pseudoprime" 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="//en.wikipedia.org/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Euler_pseudoprime&oldid=1257754025" 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=Euler_pseudoprime&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=Euler_pseudoprime&id=1257754025&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%2FEuler_pseudoprime"><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%2FEuler_pseudoprime"><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=Euler_pseudoprime&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=Euler_pseudoprime&printable=yes" title="Printable version of this page [p]" accesskey="p"><span>Printable version</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> In other projects </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q356653" title="Structured data on this page hosted by Wikidata [g]" accesskey="g"><span>Wikidata item</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Appearance</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">hide</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">From Wikipedia, the free encyclopedia</div> </div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><div class="shortdescription nomobile noexcerpt noprint searchaux" style="display:none">Odd composite number which passes the given congruence</div> <p>In <a href="/wiki/Mathematics" title="Mathematics">mathematics</a>, an <a href="/wiki/Odd_number" class="mw-redirect" title="Odd number">odd</a> <a href="/wiki/Composite_number" title="Composite number">composite</a> <a href="/wiki/Integer" title="Integer">integer</a> <i>n</i> is called an <b>Euler pseudoprime</b> to base <i>a</i>, if <i>a</i> and <i>n</i> are <a href="/wiki/Coprime" class="mw-redirect" title="Coprime">coprime</a>, and </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 a^{(n-1)/2}\equiv \pm 1{\pmod {n}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">(</mo> <mi>n</mi> <mo>−</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>2</mn> </mrow> </msup> <mo>≡</mo> <mo>±</mo> <mn>1</mn> <mrow class="MJX-TeXAtom-ORD"> <mspace width="1em" /> <mo stretchy="false">(</mo> <mi>mod</mi> <mspace width="0.333em" /> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a^{(n-1)/2}\equiv \pm 1{\pmod {n}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1cff79763c8950b703cb3daf38151a80b6905dc0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.62ex; height:3.343ex;" alt="{\displaystyle a^{(n-1)/2}\equiv \pm 1{\pmod {n}}}"></span></dd></dl> <p>(where <i>mod</i> refers to the <a href="/wiki/Modular_arithmetic" title="Modular arithmetic">modulo</a> operation). </p><p>The motivation for this definition is the fact that all <a href="/wiki/Prime_number" title="Prime number">prime numbers</a> <i>p</i> satisfy the above equation which can be deduced from <a href="/wiki/Fermat%27s_little_theorem" title="Fermat's little theorem">Fermat's little theorem</a>. Fermat's theorem asserts that if <i>p</i> is prime, and coprime to <i>a</i>, then <i>a</i><sup><i>p</i>−1</sup> ≡ 1 (mod <i>p</i>). Suppose that <i>p</i>>2 is prime, then <i>p</i> can be expressed as 2<i>q</i> + 1 where <i>q</i> is an integer. Thus, <i>a</i><sup>(2<i>q</i>+1) − 1</sup> ≡ 1 (mod <i>p</i>), which means that <i>a</i><sup>2<i>q</i></sup> − 1 ≡ 0 (mod <i>p</i>). This can be factored as (<i>a</i><sup><i>q</i></sup> − 1)(<i>a</i><sup><i>q</i></sup> + 1) ≡ 0 (mod <i>p</i>), which is equivalent to <i>a</i><sup>(<i>p</i>−1)/2</sup> ≡ ±1 (mod <i>p</i>). </p><p>The equation can be tested rather quickly, which can be used for probabilistic <a href="/wiki/Prime_testing" class="mw-redirect" title="Prime testing">primality testing</a>. These tests are twice as strong as tests based on Fermat's little theorem. </p><p>Every Euler <a href="/wiki/Pseudoprime" title="Pseudoprime">pseudoprime</a> is also a <a href="/wiki/Fermat_pseudoprime" title="Fermat pseudoprime">Fermat pseudoprime</a>. It is not possible to produce a definite test of primality based on whether a <a href="/wiki/Number" title="Number">number</a> is an Euler pseudoprime because there exist <i>absolute Euler pseudoprimes</i>, numbers which are Euler pseudoprimes to every base relatively prime to themselves. The absolute Euler pseudoprimes are a <a href="/wiki/Subset" title="Subset">subset</a> of the absolute Fermat pseudoprimes, or <a href="/wiki/Carmichael_number" title="Carmichael number">Carmichael numbers</a>, and the smallest absolute Euler pseudoprime is <a href="/wiki/1729_(number)" title="1729 (number)">1729</a> = 7×13×19 (sequence <span class="nowrap external"><a href="//oeis.org/A033181" class="extiw" title="oeis:A033181">A033181</a></span> in the <a href="/wiki/On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>). </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Relation_to_Euler–Jacobi_pseudoprimes"><span id="Relation_to_Euler.E2.80.93Jacobi_pseudoprimes"></span>Relation to Euler–Jacobi pseudoprimes</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Euler_pseudoprime&action=edit&section=1" title="Edit section: Relation to Euler–Jacobi pseudoprimes"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1236090951">.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}</style><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="/wiki/Euler%E2%80%93Jacobi_pseudoprime" title="Euler–Jacobi pseudoprime">Euler–Jacobi pseudoprime</a></div> <p>A slightly stronger test uses the <a href="/wiki/Jacobi_symbol" title="Jacobi symbol">Jacobi symbol</a> to predict which of the two results will be found. The resultant <a href="/wiki/Euler-Jacobi_pseudoprime" class="mw-redirect" title="Euler-Jacobi pseudoprime">Euler-Jacobi probable prime</a> test verifies that </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 a^{(n-1)/2}\equiv \left({\frac {a}{n}}\right)\neq 0{\pmod {n}}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">(</mo> <mi>n</mi> <mo>−</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>2</mn> </mrow> </msup> <mo>≡</mo> <mrow> <mo>(</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mi>a</mi> <mi>n</mi> </mfrac> </mrow> <mo>)</mo> </mrow> <mo>≠</mo> <mn>0</mn> <mrow class="MJX-TeXAtom-ORD"> <mspace width="1em" /> <mo stretchy="false">(</mo> <mi>mod</mi> <mspace width="0.333em" /> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a^{(n-1)/2}\equiv \left({\frac {a}{n}}\right)\neq 0{\pmod {n}}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/281aec6bf8db5cf5951662eeec254ae219224b61" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:31.563ex; height:4.843ex;" alt="{\displaystyle a^{(n-1)/2}\equiv \left({\frac {a}{n}}\right)\neq 0{\pmod {n}}.}"></span></dd></dl> <p>As with the basic Euler test, <i>a</i> and <i>n</i> are required to be comprime, but that test is included in the computation of the Jacobi symbol (<i>a</i>/<i>n</i>), whose value equals 0 if the values are <i>not</i> coprime. This slightly stronger test is called simply an Euler probable prime test by some authors. See, for example, page 115 of the book by Koblitz listed below, page 90 of the book by Riesel, or page 1003 of.<sup id="cite_ref-PSW_1-0" class="reference"><a href="#cite_note-PSW-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> </p><p>As an example of this test's increased strength, 341 is an Euler pseudoprime to the base 2, but not an Euler-Jacobi pseudoprime. Even more significantly, there are no absolute Euler–Jacobi pseudoprimes.<sup id="cite_ref-PSW_1-1" class="reference"><a href="#cite_note-PSW-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 1004">: 1004 </span></sup> </p><p>A <a href="/wiki/Strong_pseudoprime" title="Strong pseudoprime">strong probable prime</a> test is even stronger than the Euler-Jacobi test but takes the same computational effort. Because of this, prime-testing software is usually based on the strong test. </p> <div class="mw-heading mw-heading2"><h2 id="Implementation_in_Lua">Implementation in <a href="/wiki/Lua_(programming_language)" title="Lua (programming language)">Lua</a></h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Euler_pseudoprime&action=edit&section=2" title="Edit section: Implementation in Lua"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <pre><b>function</b> EulerTest(k) a = 2 <b>if</b> k == 1 <b>then return false</b> <b>elseif</b> k == 2 <b>then return true</b> <b>else</b> m = <a href="/wiki/Modular_exponentiation#Implementation_in_Lua" title="Modular exponentiation">modPow(a,(k-1)/2,k)</a> <b>if</b> (m == 1) or (m == k-1) <b>then</b> <b>return true</b> <b>else</b> <b>return false</b> <b>end</b> <b>end</b> <b>end</b> </pre> <div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Euler_pseudoprime&action=edit&section=3" title="Edit section: Examples"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <table class="wikitable"> <tbody><tr> <th><i>n</i> </th> <th>Euler pseudoprimes to base <i>n</i> </th></tr> <tr> <td>1 </td> <td>All odd composite numbers: 9, 15, 21, 25, 27, 33, 35, 39, 45, 49, 51, 55, 57, 63, 65, 69, 75, 77, 81, 85, 87, 91, 93, 95, 99, ... </td></tr> <tr> <td>2 </td> <td>341, 561, 1105, 1729, 1905, 2047, 2465, 3277, 4033, 4681, 5461, 6601, 8321, 8481, ... </td></tr> <tr> <td>3 </td> <td>121, 703, 1541, 1729, 1891, 2465, 2821, 3281, 4961, 7381, 8401, 8911, ... </td></tr> <tr> <td>4 </td> <td>341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911, ... </td></tr> <tr> <td>5 </td> <td>217, 781, 1541, 1729, 5461, 5611, 6601, 7449, 7813, ... </td></tr> <tr> <td>6 </td> <td>185, 217, 301, 481, 1111, 1261, 1333, 1729, 2465, 2701, 3421, 3565, 3589, 3913, 5713, 6533, 8365, ... </td></tr> <tr> <td>7 </td> <td>25, 325, 703, 817, 1825, 2101, 2353, 2465, 3277, 4525, 6697, 8321, ... </td></tr> <tr> <td>8 </td> <td>9, 21, 65, 105, 133, 273, 341, 481, 511, 561, 585, 1001, 1105, 1281, 1417, 1541, 1661, 1729, 1905, 2047, 2465, 2501, 3201, 3277, 3641, 4033, 4097, 4641, 4681, 4921, 5461, 6305, 6533, 6601, 7161, 8321, 8481, 9265, 9709, ... </td></tr> <tr> <td>9 </td> <td>91, 121, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, 4961, 5551, 6601, 7381, 8401, 8911, ... </td></tr> <tr> <td>10 </td> <td>9, 33, 91, 481, 657, 1233, 1729, 2821, 2981, 4187, 5461, 6533, 6541, 6601, 7777, 8149, 8401, ... </td></tr> <tr> <td>11 </td> <td>133, 305, 481, 645, 793, 1729, 2047, 2257, 2465, 4577, 4921, 5041, 5185, 8113, ... </td></tr> <tr> <td>12 </td> <td>65, 91, 133, 145, 247, 377, 385, 1649, 1729, 2041, 2233, 2465, 2821, 3553, 6305, 8911, 9073, ... </td></tr> <tr> <td>13 </td> <td>21, 85, 105, 561, 1099, 1785, 2465, 5149, 5185, 7107, 8841, 8911, 9577, 9637, ... </td></tr> <tr> <td>14 </td> <td>15, 65, 481, 781, 793, 841, 985, 1541, 2257, 2465, 2561, 2743, 3277, 5185, 5713, 6533, 6541, 7171, 7449, 7585, 8321, 9073, ... </td></tr> <tr> <td>15 </td> <td>341, 1477, 1541, 1687, 1729, 1921, 3277, 6541, 9073, ... </td></tr> <tr> <td>16 </td> <td>15, 85, 91, 341, 435, 451, 561, 645, 703, 1105, 1247, 1271, 1387, 1581, 1695, 1729, 1891, 1905, 2047, 2071, 2465, 2701, 2821, 3133, 3277, 3367, 3683, 4033, 4369, 4371, 4681, 4795, 4859, 5461, 5551, 6601, 6643, 7957, 8321, 8481, 8695, 8911, 9061, 9131, 9211, 9605, 9919, ... </td></tr> <tr> <td>17 </td> <td>9, 91, 145, 781, 1111, 1305, 1729, 2149, 2821, 4033, 4187, 5365, 5833, 6697, 7171, ... </td></tr> <tr> <td>18 </td> <td>25, 49, 65, 133, 325, 343, 425, 1105, 1225, 1369, 1387, 1729, 1921, 2149, 2465, 2977, 4577, 5725, 5833, 5941, 6305, 6517, 6601, 7345, ... </td></tr> <tr> <td>19 </td> <td>9, 45, 49, 169, 343, 561, 889, 905, 1105, 1661, 1849, 2353, 2465, 2701, 3201, 4033, 4681, 5461, 5713, 6541, 6697, 7957, 8145, 8281, 8401, 9997, ... </td></tr> <tr> <td>20 </td> <td>21, 57, 133, 671, 889, 1281, 1653, 1729, 1891, 2059, 2413, 2761, 3201, 5461, 5473, 5713, 5833, 6601, 6817, 7999, ... </td></tr> <tr> <td>21 </td> <td>65, 221, 703, 793, 1045, 1105, 2465, 3781, 5185, 5473, 6541, 7363, 8965, 9061, ... </td></tr> <tr> <td>22 </td> <td>21, 69, 91, 105, 161, 169, 345, 485, 1183, 1247, 1541, 1729, 2041, 2047, 2413, 2465, 2821, 3241, 3801, 5551, 7665, 9453, ... </td></tr> <tr> <td>23 </td> <td>33, 169, 265, 341, 385, 481, 553, 1065, 1271, 1729, 2321, 2465, 2701, 2821, 3097, 4033, 4081, 4345, 4371, 4681, 5149, 6533, 6541, 7189, 7957, 8321, 8651, 8745, 8911, 9805, ... </td></tr> <tr> <td>24 </td> <td>25, 175, 553, 805, 949, 1541, 1729, 1825, 1975, 2413, 2465, 2701, 3781, 4537, 6931, 7501, 9085, 9361, ... </td></tr> <tr> <td>25 </td> <td>217, 561, 781, 1541, 1729, 1891, 2821, 4123, 5461, 5611, 5731, 6601, 7449, 7813, 8029, 8911, 9881, ... </td></tr> <tr> <td>26 </td> <td>9, 25, 27, 45, 133, 217, 225, 475, 561, 589, 703, 925, 1065, 2465, 3325, 3385, 3565, 3825, 4741, 4921, 5041, 5425, 6697, 8029, 9073, ... </td></tr> <tr> <td>27 </td> <td>65, 121, 133, 259, 341, 365, 481, 703, 1001, 1541, 1649, 1729, 1891, 2465, 2821, 2981, 2993, 3281, 4033, 4745, 4921, 4961, 5461, 6305, 6533, 7381, 7585, 8321, 8401, 8911, 9809, 9841, 9881, ... </td></tr> <tr> <td>28 </td> <td>9, 27, 145, 261, 361, 529, 785, 1305, 1431, 2041, 2413, 2465, 3201, 3277, 4553, 4699, 5149, 7065, 8321, 8401, 9841, ... </td></tr> <tr> <td>29 </td> <td>15, 21, 91, 105, 341, 469, 481, 793, 871, 1729, 1897, 2105, 2257, 2821, 4371, 4411, 5149, 5185, 5473, 5565, 6097, 7161, 8321, 8401, 8421, 8841, ... </td></tr> <tr> <td>30 </td> <td>49, 133, 217, 341, 403, 469, 589, 637, 871, 901, 931, 1273, 1537, 1729, 2059, 2077, 2821, 3097, 3277, 4081, 4097, 5729, 6031, 6061, 6097, 6409, 6817, 7657, 8023, 8029, 8401, 9881, ... </td></tr></tbody></table> <div class="mw-heading mw-heading2"><h2 id="Least_Euler_pseudoprime_to_base_n">Least Euler pseudoprime to base <i>n</i></h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Euler_pseudoprime&action=edit&section=4" title="Edit section: Least Euler pseudoprime to base n"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <table class="wikitable"> <tbody><tr> <td><i>n</i> </td> <td>Least EPSP </td> <td><i>n</i> </td> <td>Least EPSP </td> <td><i>n</i> </td> <td>Least EPSP </td> <td><i>n</i> </td> <td>Least EPSP </td></tr> <tr> <td>1 </td> <td>9 </td> <td>33 </td> <td>545 </td> <td>65 </td> <td>33 </td> <td>97 </td> <td>21 </td></tr> <tr> <td>2 </td> <td>341 </td> <td>34 </td> <td>21 </td> <td>66 </td> <td>65 </td> <td>98 </td> <td>9 </td></tr> <tr> <td>3 </td> <td>121 </td> <td>35 </td> <td>9 </td> <td>67 </td> <td>33 </td> <td>99 </td> <td>25 </td></tr> <tr> <td>4 </td> <td>341 </td> <td>36 </td> <td>35 </td> <td>68 </td> <td>25 </td> <td>100 </td> <td>9 </td></tr> <tr> <td>5 </td> <td>217 </td> <td>37 </td> <td>9 </td> <td>69 </td> <td>35 </td> <td>101 </td> <td>25 </td></tr> <tr> <td>6 </td> <td>185 </td> <td>38 </td> <td>39 </td> <td>70 </td> <td>69 </td> <td>102 </td> <td>133 </td></tr> <tr> <td>7 </td> <td>25 </td> <td>39 </td> <td>133 </td> <td>71 </td> <td>9 </td> <td>103 </td> <td>51 </td></tr> <tr> <td>8 </td> <td>9 </td> <td>40 </td> <td>39 </td> <td>72 </td> <td>85 </td> <td>104 </td> <td>15 </td></tr> <tr> <td>9 </td> <td>91 </td> <td>41 </td> <td>21 </td> <td>73 </td> <td>9 </td> <td>105 </td> <td>451 </td></tr> <tr> <td>10 </td> <td>9 </td> <td>42 </td> <td>451 </td> <td>74 </td> <td>15 </td> <td>106 </td> <td>15 </td></tr> <tr> <td>11 </td> <td>133 </td> <td>43 </td> <td>21 </td> <td>75 </td> <td>91 </td> <td>107 </td> <td>9 </td></tr> <tr> <td>12 </td> <td>65 </td> <td>44 </td> <td>9 </td> <td>76 </td> <td>15 </td> <td>108 </td> <td>91 </td></tr> <tr> <td>13 </td> <td>21 </td> <td>45 </td> <td>133 </td> <td>77 </td> <td>39 </td> <td>109 </td> <td>9 </td></tr> <tr> <td>14 </td> <td>15 </td> <td>46 </td> <td>9 </td> <td>78 </td> <td>77 </td> <td>110 </td> <td>111 </td></tr> <tr> <td>15 </td> <td>341 </td> <td>47 </td> <td>65 </td> <td>79 </td> <td>39 </td> <td>111 </td> <td>55 </td></tr> <tr> <td>16 </td> <td>15 </td> <td>48 </td> <td>49 </td> <td>80 </td> <td>9 </td> <td>112 </td> <td>65 </td></tr> <tr> <td>17 </td> <td>9 </td> <td>49 </td> <td>25 </td> <td>81 </td> <td>91 </td> <td>113 </td> <td>21 </td></tr> <tr> <td>18 </td> <td>25 </td> <td>50 </td> <td>21 </td> <td>82 </td> <td>9 </td> <td>114 </td> <td>115 </td></tr> <tr> <td>19 </td> <td>9 </td> <td>51 </td> <td>25 </td> <td>83 </td> <td>21 </td> <td>115 </td> <td>57 </td></tr> <tr> <td>20 </td> <td>21 </td> <td>52 </td> <td>51 </td> <td>84 </td> <td>85 </td> <td>116 </td> <td>9 </td></tr> <tr> <td>21 </td> <td>65 </td> <td>53 </td> <td>9 </td> <td>85 </td> <td>21 </td> <td>117 </td> <td>49 </td></tr> <tr> <td>22 </td> <td>21 </td> <td>54 </td> <td>55 </td> <td>86 </td> <td>65 </td> <td>118 </td> <td>9 </td></tr> <tr> <td>23 </td> <td>33 </td> <td>55 </td> <td>9 </td> <td>87 </td> <td>133 </td> <td>119 </td> <td>15 </td></tr> <tr> <td>24 </td> <td>25 </td> <td>56 </td> <td>33 </td> <td>88 </td> <td>87 </td> <td>120 </td> <td>77 </td></tr> <tr> <td>25 </td> <td>217 </td> <td>57 </td> <td>25 </td> <td>89 </td> <td>9 </td> <td>121 </td> <td>15 </td></tr> <tr> <td>26 </td> <td>9 </td> <td>58 </td> <td>57 </td> <td>90 </td> <td>91 </td> <td>122 </td> <td>33 </td></tr> <tr> <td>27 </td> <td>65 </td> <td>59 </td> <td>15 </td> <td>91 </td> <td>9 </td> <td>123 </td> <td>85 </td></tr> <tr> <td>28 </td> <td>9 </td> <td>60 </td> <td>341 </td> <td>92 </td> <td>21 </td> <td>124 </td> <td>25 </td></tr> <tr> <td>29 </td> <td>15 </td> <td>61 </td> <td>15 </td> <td>93 </td> <td>25 </td> <td>125 </td> <td>9 </td></tr> <tr> <td>30 </td> <td>49 </td> <td>62 </td> <td>9 </td> <td>94 </td> <td>57 </td> <td>126 </td> <td>25 </td></tr> <tr> <td>31 </td> <td>15 </td> <td>63 </td> <td>341 </td> <td>95 </td> <td>141 </td> <td>127 </td> <td>9 </td></tr> <tr> <td>32 </td> <td>25 </td> <td>64 </td> <td>9 </td> <td>96 </td> <td>65 </td> <td>128 </td> <td>49 </td></tr></tbody></table> <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=Euler_pseudoprime&action=edit&section=5" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Probable_prime" title="Probable prime">Probable prime</a></li></ul> <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=Euler_pseudoprime&action=edit&section=6" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1239543626">.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist"> <div class="mw-references-wrap"><ol class="references"> <li id="cite_note-PSW-1"><span class="mw-cite-backlink">^ <a href="#cite_ref-PSW_1-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-PSW_1-1"><sup><i><b>b</b></i></sup></a></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="CITEREFCarl_PomeranceJohn_L._SelfridgeSamuel_S._Wagstaff,_Jr.1980" class="citation journal cs1"><a href="/wiki/Carl_Pomerance" title="Carl Pomerance">Carl Pomerance</a>; <a href="/wiki/John_L._Selfridge" class="mw-redirect" title="John L. Selfridge">John L. Selfridge</a>; <a href="/wiki/Samuel_S._Wagstaff,_Jr." class="mw-redirect" title="Samuel S. Wagstaff, Jr.">Samuel S. Wagstaff, Jr.</a> (July 1980). <a rel="nofollow" class="external text" href="//math.dartmouth.edu/~carlp/PDF/paper25.pdf">"The pseudoprimes to 25·10<sup>9</sup>"</a> <span class="cs1-format">(PDF)</span>. <i>Mathematics of Computation</i>. <b>35</b> (151): <span class="nowrap">1003–</span>1026. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1090%2FS0025-5718-1980-0572872-7">10.1090/S0025-5718-1980-0572872-7</a></span>. <a href="/wiki/JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2006210">2006210</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Mathematics+of+Computation&rft.atitle=The+pseudoprimes+to+25%C2%B710%3Csup%3E9%3C%2Fsup%3E&rft.volume=35&rft.issue=151&rft.pages=%3Cspan+class%3D%22nowrap%22%3E1003-%3C%2Fspan%3E1026&rft.date=1980-07&rft_id=info%3Adoi%2F10.1090%2FS0025-5718-1980-0572872-7&rft_id=https%3A%2F%2Fwww.jstor.org%2Fstable%2F2006210%23id-name%3DJSTOR&rft.au=Carl+Pomerance&rft.au=John+L.+Selfridge&rft.au=Samuel+S.+Wagstaff%2C+Jr.&rft_id=%2F%2Fmath.dartmouth.edu%2F~carlp%2FPDF%2Fpaper25.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AEuler+pseudoprime" class="Z3988"></span></span> </li> </ol></div></div> <ul><li>M. Koblitz, "A Course in Number Theory and Cryptography", Springer-Verlag, 1987.</li> <li>H. Riesel, "Prime numbers and computer methods of factorisation", Birkhäuser, Boston, Mass., 1985.</li></ul> <div class="navbox-styles"><style data-mw-deduplicate="TemplateStyles:r1129693374">.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}</style><style data-mw-deduplicate="TemplateStyles:r1236075235">.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}</style></div><div role="navigation" class="navbox" aria-labelledby="Classes_of_natural_numbers743" style="padding:3px"><table class="nowraplinks mw-collapsible mw-collapsed navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><style data-mw-deduplicate="TemplateStyles:r1239400231">.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}</style><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Classes_of_natural_numbers" title="Template:Classes of natural numbers"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Classes_of_natural_numbers" title="Template talk:Classes of natural numbers"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Classes_of_natural_numbers" title="Special:EditPage/Template:Classes of natural numbers"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Classes_of_natural_numbers743" style="font-size:114%;margin:0 4em">Classes of <a href="/wiki/Natural_number" title="Natural number">natural numbers</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Powers_and_related_numbers743" style="font-size:114%;margin:0 4em"><a href="/wiki/Exponentiation" title="Exponentiation">Powers</a> and related numbers</div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Achilles_number" title="Achilles number">Achilles</a></li> <li><a href="/wiki/Power_of_two" title="Power of two">Power of 2</a></li> <li><a href="/wiki/Power_of_three" title="Power of three">Power of 3</a></li> <li><a href="/wiki/Power_of_10" title="Power of 10">Power of 10</a></li> <li><a href="/wiki/Square_number" title="Square number">Square</a></li> <li><a href="/wiki/Cube_(algebra)" title="Cube (algebra)">Cube</a></li> <li><a href="/wiki/Fourth_power" title="Fourth power">Fourth power</a></li> <li><a href="/wiki/Fifth_power_(algebra)" title="Fifth power (algebra)">Fifth power</a></li> <li><a href="/wiki/Sixth_power" title="Sixth power">Sixth power</a></li> <li><a href="/wiki/Seventh_power" title="Seventh power">Seventh power</a></li> <li><a href="/wiki/Eighth_power" title="Eighth power">Eighth power</a></li> <li><a href="/wiki/Perfect_power" title="Perfect power">Perfect power</a></li> <li><a href="/wiki/Powerful_number" title="Powerful number">Powerful</a></li> <li><a href="/wiki/Prime_power" title="Prime power">Prime power</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Of_the_form_a_×_2b_±_1743" style="font-size:114%;margin:0 4em">Of the form <i>a</i> × 2<sup><i>b</i></sup> ± 1</div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Cullen_number" title="Cullen number">Cullen</a></li> <li><a href="/wiki/Double_Mersenne_number" title="Double Mersenne number">Double Mersenne</a></li> <li><a href="/wiki/Fermat_number" title="Fermat number">Fermat</a></li> <li><a href="/wiki/Mersenne_prime" title="Mersenne prime">Mersenne</a></li> <li><a href="/wiki/Proth_number" class="mw-redirect" title="Proth number">Proth</a></li> <li><a href="/wiki/Thabit_number" title="Thabit number">Thabit</a></li> <li><a href="/wiki/Woodall_number" title="Woodall number">Woodall</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Other_polynomial_numbers743" style="font-size:114%;margin:0 4em">Other polynomial numbers</div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Hilbert_number" title="Hilbert number">Hilbert</a></li> <li><a href="/wiki/Idoneal_number" title="Idoneal number">Idoneal</a></li> <li><a href="/wiki/Leyland_number" title="Leyland number">Leyland</a></li> <li><a href="/wiki/Loeschian_number" class="mw-redirect" title="Loeschian number">Loeschian</a></li> <li><a href="/wiki/Lucky_numbers_of_Euler" title="Lucky numbers of Euler">Lucky numbers of Euler</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Recursively_defined_numbers743" style="font-size:114%;margin:0 4em"><a href="/wiki/Recursion" title="Recursion">Recursively</a> defined numbers</div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Fibonacci_sequence" title="Fibonacci sequence">Fibonacci</a></li> <li><a href="/wiki/Jacobsthal_number" title="Jacobsthal number">Jacobsthal</a></li> <li><a href="/wiki/Leonardo_number" title="Leonardo number">Leonardo</a></li> <li><a href="/wiki/Lucas_number" title="Lucas number">Lucas</a></li> <li><a href="/wiki/Supergolden_ratio#Narayana_sequence" title="Supergolden ratio">Narayana</a></li> <li><a href="/wiki/Padovan_sequence" title="Padovan sequence">Padovan</a></li> <li><a href="/wiki/Pell_number" title="Pell number">Pell</a></li> <li><a href="/wiki/Perrin_number" title="Perrin number">Perrin</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Possessing_a_specific_set_of_other_numbers743" style="font-size:114%;margin:0 4em">Possessing a specific set of other numbers</div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Amenable_number" title="Amenable number">Amenable</a></li> <li><a href="/wiki/Congruent_number" title="Congruent number">Congruent</a></li> <li><a href="/wiki/Kn%C3%B6del_number" title="Knödel number">Knödel</a></li> <li><a href="/wiki/Riesel_number" title="Riesel number">Riesel</a></li> <li><a href="/wiki/Sierpi%C5%84ski_number" title="Sierpiński number">Sierpiński</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Expressible_via_specific_sums743" style="font-size:114%;margin:0 4em">Expressible via specific sums</div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Nonhypotenuse_number" title="Nonhypotenuse number">Nonhypotenuse</a></li> <li><a href="/wiki/Polite_number" title="Polite number">Polite</a></li> <li><a href="/wiki/Practical_number" title="Practical number">Practical</a></li> <li><a href="/wiki/Primary_pseudoperfect_number" title="Primary pseudoperfect number">Primary pseudoperfect</a></li> <li><a href="/wiki/Ulam_number" title="Ulam number">Ulam</a></li> <li><a href="/wiki/Wolstenholme_number" title="Wolstenholme number">Wolstenholme</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Figurate_numbers743" style="font-size:114%;margin:0 4em"><a href="/wiki/Figurate_number" title="Figurate number">Figurate numbers</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Plane_(mathematics)" title="Plane (mathematics)">2-dimensional</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Centered_polygonal_number" title="Centered polygonal number">centered</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Centered_triangular_number" title="Centered triangular number">Centered triangular</a></li> <li><a href="/wiki/Centered_square_number" title="Centered square number">Centered square</a></li> <li><a href="/wiki/Centered_pentagonal_number" title="Centered pentagonal number">Centered pentagonal</a></li> <li><a href="/wiki/Centered_hexagonal_number" title="Centered hexagonal number">Centered hexagonal</a></li> <li><a href="/wiki/Centered_heptagonal_number" title="Centered heptagonal number">Centered heptagonal</a></li> <li><a href="/wiki/Centered_octagonal_number" title="Centered octagonal number">Centered octagonal</a></li> <li><a href="/wiki/Centered_nonagonal_number" title="Centered nonagonal number">Centered nonagonal</a></li> <li><a href="/wiki/Centered_decagonal_number" title="Centered decagonal number">Centered decagonal</a></li> <li><a href="/wiki/Star_number" title="Star number">Star</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Polygonal_number" title="Polygonal number">non-centered</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Triangular_number" title="Triangular number">Triangular</a></li> <li><a href="/wiki/Square_number" title="Square number">Square</a></li> <li><a href="/wiki/Square_triangular_number" title="Square triangular number">Square triangular</a></li> <li><a href="/wiki/Pentagonal_number" title="Pentagonal number">Pentagonal</a></li> <li><a href="/wiki/Hexagonal_number" title="Hexagonal number">Hexagonal</a></li> <li><a href="/wiki/Heptagonal_number" title="Heptagonal number">Heptagonal</a></li> <li><a href="/wiki/Octagonal_number" title="Octagonal number">Octagonal</a></li> <li><a href="/wiki/Nonagonal_number" title="Nonagonal number">Nonagonal</a></li> <li><a href="/wiki/Decagonal_number" title="Decagonal number">Decagonal</a></li> <li><a href="/wiki/Dodecagonal_number" title="Dodecagonal number">Dodecagonal</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Three-dimensional_space" title="Three-dimensional space">3-dimensional</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Centered_polyhedral_number" title="Centered polyhedral number">centered</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Centered_tetrahedral_number" title="Centered tetrahedral number">Centered tetrahedral</a></li> <li><a href="/wiki/Centered_cube_number" title="Centered cube number">Centered cube</a></li> <li><a href="/wiki/Centered_octahedral_number" title="Centered octahedral number">Centered octahedral</a></li> <li><a href="/wiki/Centered_dodecahedral_number" title="Centered dodecahedral number">Centered dodecahedral</a></li> <li><a href="/wiki/Centered_icosahedral_number" title="Centered icosahedral number">Centered icosahedral</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Polyhedral_number" class="mw-redirect" title="Polyhedral number">non-centered</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Tetrahedral_number" title="Tetrahedral number">Tetrahedral</a></li> <li><a href="/wiki/Cube_(algebra)" title="Cube (algebra)">Cubic</a></li> <li><a href="/wiki/Octahedral_number" title="Octahedral number">Octahedral</a></li> <li><a href="/wiki/Dodecahedral_number" title="Dodecahedral number">Dodecahedral</a></li> <li><a href="/wiki/Icosahedral_number" title="Icosahedral number">Icosahedral</a></li> <li><a href="/wiki/Stella_octangula_number" title="Stella octangula number">Stella octangula</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Pyramidal_number" title="Pyramidal number">pyramidal</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Square_pyramidal_number" title="Square pyramidal number">Square pyramidal</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Four-dimensional_space" title="Four-dimensional space">4-dimensional</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%">non-centered</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Pentatope_number" title="Pentatope number">Pentatope</a></li> <li><a href="/wiki/Squared_triangular_number" title="Squared triangular number">Squared triangular</a></li> <li><a href="/wiki/Fourth_power" title="Fourth power">Tesseractic</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Combinatorial_numbers743" style="font-size:114%;margin:0 4em">Combinatorial numbers</div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Bell_number" title="Bell number">Bell</a></li> <li><a href="/wiki/Cake_number" title="Cake number">Cake</a></li> <li><a href="/wiki/Catalan_number" title="Catalan number">Catalan</a></li> <li><a href="/wiki/Dedekind_number" title="Dedekind number">Dedekind</a></li> <li><a href="/wiki/Delannoy_number" title="Delannoy number">Delannoy</a></li> <li><a href="/wiki/Euler_number" class="mw-redirect" title="Euler number">Euler</a></li> <li><a href="/wiki/Eulerian_number" title="Eulerian number">Eulerian</a></li> <li><a href="/wiki/Fuss%E2%80%93Catalan_number" title="Fuss–Catalan number">Fuss–Catalan</a></li> <li><a href="/wiki/Lah_number" title="Lah number">Lah</a></li> <li><a href="/wiki/Lazy_caterer%27s_sequence" title="Lazy caterer's sequence">Lazy caterer's sequence</a></li> <li><a href="/wiki/Lobb_number" title="Lobb number">Lobb</a></li> <li><a href="/wiki/Motzkin_number" title="Motzkin number">Motzkin</a></li> <li><a href="/wiki/Narayana_number" title="Narayana number">Narayana</a></li> <li><a href="/wiki/Ordered_Bell_number" title="Ordered Bell number">Ordered Bell</a></li> <li><a href="/wiki/Schr%C3%B6der_number" title="Schröder number">Schröder</a></li> <li><a href="/wiki/Schr%C3%B6der%E2%80%93Hipparchus_number" title="Schröder–Hipparchus number">Schröder–Hipparchus</a></li> <li><a href="/wiki/Stirling_numbers_of_the_first_kind" title="Stirling numbers of the first kind">Stirling first</a></li> <li><a href="/wiki/Stirling_numbers_of_the_second_kind" title="Stirling numbers of the second kind">Stirling second</a></li> <li><a href="/wiki/Telephone_number_(mathematics)" title="Telephone number (mathematics)">Telephone number</a></li> <li><a href="/wiki/Wedderburn%E2%80%93Etherington_number" title="Wedderburn–Etherington number">Wedderburn–Etherington</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Primes743" style="font-size:114%;margin:0 4em"><a href="/wiki/Prime_number" title="Prime number">Primes</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Wieferich_prime#Wieferich_numbers" title="Wieferich prime">Wieferich</a></li> <li><a href="/wiki/Wall%E2%80%93Sun%E2%80%93Sun_prime" title="Wall–Sun–Sun prime">Wall–Sun–Sun</a></li> <li><a href="/wiki/Wolstenholme_prime" title="Wolstenholme prime">Wolstenholme prime</a></li> <li><a href="/wiki/Wilson_prime#Wilson_numbers" title="Wilson prime">Wilson</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Pseudoprimes743" style="font-size:114%;margin:0 4em"><a href="/wiki/Pseudoprime" title="Pseudoprime">Pseudoprimes</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Carmichael_number" title="Carmichael number">Carmichael number</a></li> <li><a href="/wiki/Catalan_pseudoprime" title="Catalan pseudoprime">Catalan pseudoprime</a></li> <li><a href="/wiki/Elliptic_pseudoprime" title="Elliptic pseudoprime">Elliptic pseudoprime</a></li> <li><a class="mw-selflink selflink">Euler pseudoprime</a></li> <li><a href="/wiki/Euler%E2%80%93Jacobi_pseudoprime" title="Euler–Jacobi pseudoprime">Euler–Jacobi pseudoprime</a></li> <li><a href="/wiki/Fermat_pseudoprime" title="Fermat pseudoprime">Fermat pseudoprime</a></li> <li><a href="/wiki/Frobenius_pseudoprime" title="Frobenius pseudoprime">Frobenius pseudoprime</a></li> <li><a href="/wiki/Lucas_pseudoprime" title="Lucas pseudoprime">Lucas pseudoprime</a></li> <li><a href="/wiki/Lucas%E2%80%93Carmichael_number" title="Lucas–Carmichael number">Lucas–Carmichael number</a></li> <li><a href="/wiki/Perrin_number#Perrin_primality_test" title="Perrin number">Perrin pseudoprime</a></li> <li><a href="/wiki/Somer%E2%80%93Lucas_pseudoprime" title="Somer–Lucas pseudoprime">Somer–Lucas pseudoprime</a></li> <li><a href="/wiki/Strong_pseudoprime" title="Strong pseudoprime">Strong pseudoprime</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Arithmetic_functions_and_dynamics743" style="font-size:114%;margin:0 4em"><a href="/wiki/Arithmetic_function" title="Arithmetic function">Arithmetic functions</a> and <a href="/wiki/Arithmetic_dynamics" title="Arithmetic dynamics">dynamics</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Divisor_function" title="Divisor function">Divisor functions</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Abundant_number" title="Abundant number">Abundant</a></li> <li><a href="/wiki/Almost_perfect_number" title="Almost perfect number">Almost perfect</a></li> <li><a href="/wiki/Arithmetic_number" title="Arithmetic number">Arithmetic</a></li> <li><a href="/wiki/Betrothed_numbers" title="Betrothed numbers">Betrothed</a></li> <li><a href="/wiki/Colossally_abundant_number" title="Colossally abundant number">Colossally abundant</a></li> <li><a href="/wiki/Deficient_number" title="Deficient number">Deficient</a></li> <li><a href="/wiki/Descartes_number" title="Descartes number">Descartes</a></li> <li><a href="/wiki/Hemiperfect_number" title="Hemiperfect number">Hemiperfect</a></li> <li><a href="/wiki/Highly_abundant_number" title="Highly abundant number">Highly abundant</a></li> <li><a href="/wiki/Highly_composite_number" title="Highly composite number">Highly composite</a></li> <li><a href="/wiki/Hyperperfect_number" title="Hyperperfect number">Hyperperfect</a></li> <li><a href="/wiki/Multiply_perfect_number" title="Multiply perfect number">Multiply perfect</a></li> <li><a href="/wiki/Perfect_number" title="Perfect number">Perfect</a></li> <li><a href="/wiki/Practical_number" title="Practical number">Practical</a></li> <li><a href="/wiki/Primitive_abundant_number" title="Primitive abundant number">Primitive abundant</a></li> <li><a href="/wiki/Quasiperfect_number" title="Quasiperfect number">Quasiperfect</a></li> <li><a href="/wiki/Refactorable_number" title="Refactorable number">Refactorable</a></li> <li><a href="/wiki/Semiperfect_number" title="Semiperfect number">Semiperfect</a></li> <li><a href="/wiki/Sublime_number" title="Sublime number">Sublime</a></li> <li><a href="/wiki/Superabundant_number" title="Superabundant number">Superabundant</a></li> <li><a href="/wiki/Superior_highly_composite_number" title="Superior highly composite number">Superior highly composite</a></li> <li><a href="/wiki/Superperfect_number" title="Superperfect number">Superperfect</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Prime_omega_function" title="Prime omega function">Prime omega functions</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Almost_prime" title="Almost prime">Almost prime</a></li> <li><a href="/wiki/Semiprime" title="Semiprime">Semiprime</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Euler%27s_totient_function" title="Euler's totient function">Euler's totient function</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Highly_cototient_number" title="Highly cototient number">Highly cototient</a></li> <li><a href="/wiki/Highly_totient_number" title="Highly totient number">Highly totient</a></li> <li><a href="/wiki/Noncototient" title="Noncototient">Noncototient</a></li> <li><a href="/wiki/Nontotient" title="Nontotient">Nontotient</a></li> <li><a href="/wiki/Perfect_totient_number" title="Perfect totient number">Perfect totient</a></li> <li><a href="/wiki/Sparsely_totient_number" title="Sparsely totient number">Sparsely totient</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Aliquot_sequence" title="Aliquot sequence">Aliquot sequences</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Amicable_numbers" title="Amicable numbers">Amicable</a></li> <li><a href="/wiki/Perfect_number" title="Perfect number">Perfect</a></li> <li><a href="/wiki/Sociable_numbers" class="mw-redirect" title="Sociable numbers">Sociable</a></li> <li><a href="/wiki/Untouchable_number" title="Untouchable number">Untouchable</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Primorial" title="Primorial">Primorial</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Euclid_number" title="Euclid number">Euclid</a></li> <li><a href="/wiki/Fortunate_number" title="Fortunate number">Fortunate</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Other_prime_factor_or_divisor_related_numbers743" style="font-size:114%;margin:0 4em">Other <a href="/wiki/Prime_factor" class="mw-redirect" title="Prime factor">prime factor</a> or <a href="/wiki/Divisor" title="Divisor">divisor</a> related numbers</div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Blum_integer" title="Blum integer">Blum</a></li> <li><a href="/wiki/Cyclic_number_(group_theory)" title="Cyclic number (group theory)">Cyclic</a></li> <li><a href="/wiki/Erd%C5%91s%E2%80%93Nicolas_number" title="Erdős–Nicolas number">Erdős–Nicolas</a></li> <li><a href="/wiki/Erd%C5%91s%E2%80%93Woods_number" title="Erdős–Woods number">Erdős–Woods</a></li> <li><a href="/wiki/Friendly_number" title="Friendly number">Friendly</a></li> <li><a href="/wiki/Giuga_number" title="Giuga number">Giuga</a></li> <li><a href="/wiki/Harmonic_divisor_number" title="Harmonic divisor number">Harmonic divisor</a></li> <li><a href="/wiki/Jordan%E2%80%93P%C3%B3lya_number" title="Jordan–Pólya number">Jordan–Pólya</a></li> <li><a href="/wiki/Lucas%E2%80%93Carmichael_number" title="Lucas–Carmichael number">Lucas–Carmichael</a></li> <li><a href="/wiki/Pronic_number" title="Pronic number">Pronic</a></li> <li><a href="/wiki/Regular_number" title="Regular number">Regular</a></li> <li><a href="/wiki/Rough_number" title="Rough number">Rough</a></li> <li><a href="/wiki/Smooth_number" title="Smooth number">Smooth</a></li> <li><a href="/wiki/Sphenic_number" title="Sphenic number">Sphenic</a></li> <li><a href="/wiki/St%C3%B8rmer_number" title="Størmer number">Størmer</a></li> <li><a href="/wiki/Super-Poulet_number" title="Super-Poulet number">Super-Poulet</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Numeral_system-dependent_numbers743" style="font-size:114%;margin:0 4em"><a href="/wiki/Numeral_system" title="Numeral system">Numeral system</a>-dependent numbers</div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Arithmetic_function" title="Arithmetic function">Arithmetic functions</a> <br />and <a href="/wiki/Arithmetic_dynamics" title="Arithmetic dynamics">dynamics</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Persistence_of_a_number" title="Persistence of a number">Persistence</a> <ul><li><a href="/wiki/Additive_persistence" class="mw-redirect" title="Additive persistence">Additive</a></li> <li><a href="/wiki/Multiplicative_persistence" class="mw-redirect" title="Multiplicative persistence">Multiplicative</a></li></ul></li></ul> </div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Digit_sum" title="Digit sum">Digit sum</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Digit_sum" title="Digit sum">Digit sum</a></li> <li><a href="/wiki/Digital_root" title="Digital root">Digital root</a></li> <li><a href="/wiki/Self_number" title="Self number">Self</a></li> <li><a href="/wiki/Sum-product_number" title="Sum-product number">Sum-product</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Digit product</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Multiplicative_digital_root" title="Multiplicative digital root">Multiplicative digital root</a></li> <li><a href="/wiki/Sum-product_number" title="Sum-product number">Sum-product</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Coding-related</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Meertens_number" title="Meertens number">Meertens</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Dudeney_number" title="Dudeney number">Dudeney</a></li> <li><a href="/wiki/Factorion" title="Factorion">Factorion</a></li> <li><a href="/wiki/Kaprekar_number" title="Kaprekar number">Kaprekar</a></li> <li><a href="/wiki/Kaprekar%27s_routine" title="Kaprekar's routine">Kaprekar's constant</a></li> <li><a href="/wiki/Keith_number" title="Keith number">Keith</a></li> <li><a href="/wiki/Lychrel_number" title="Lychrel number">Lychrel</a></li> <li><a href="/wiki/Narcissistic_number" title="Narcissistic number">Narcissistic</a></li> <li><a href="/wiki/Perfect_digit-to-digit_invariant" title="Perfect digit-to-digit invariant">Perfect digit-to-digit invariant</a></li> <li><a href="/wiki/Perfect_digital_invariant" title="Perfect digital invariant">Perfect digital invariant</a> <ul><li><a href="/wiki/Happy_number" title="Happy number">Happy</a></li></ul></li></ul> </div></td></tr></tbody></table><div> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/P-adic_numbers" class="mw-redirect" title="P-adic numbers">P-adic numbers</a>-related</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Automorphic_number" title="Automorphic number">Automorphic</a> <ul><li><a href="/wiki/Trimorphic_number" class="mw-redirect" title="Trimorphic number">Trimorphic</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Numerical_digit" title="Numerical digit">Digit</a>-composition related</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Palindromic_number" title="Palindromic number">Palindromic</a></li> <li><a href="/wiki/Pandigital_number" title="Pandigital number">Pandigital</a></li> <li><a href="/wiki/Repdigit" title="Repdigit">Repdigit</a></li> <li><a href="/wiki/Repunit" title="Repunit">Repunit</a></li> <li><a href="/wiki/Self-descriptive_number" title="Self-descriptive number">Self-descriptive</a></li> <li><a href="/wiki/Smarandache%E2%80%93Wellin_number" title="Smarandache–Wellin number">Smarandache–Wellin</a></li> <li><a href="/wiki/Undulating_number" title="Undulating number">Undulating</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Digit-<a href="/wiki/Permutation" title="Permutation">permutation</a> related</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Cyclic_number" title="Cyclic number">Cyclic</a></li> <li><a href="/wiki/Digit-reassembly_number" title="Digit-reassembly number">Digit-reassembly</a></li> <li><a href="/wiki/Parasitic_number" title="Parasitic number">Parasitic</a></li> <li><a href="/wiki/Primeval_number" title="Primeval number">Primeval</a></li> <li><a href="/wiki/Transposable_integer" title="Transposable integer">Transposable</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Divisor-related</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Equidigital_number" title="Equidigital number">Equidigital</a></li> <li><a href="/wiki/Extravagant_number" title="Extravagant number">Extravagant</a></li> <li><a href="/wiki/Frugal_number" title="Frugal number">Frugal</a></li> <li><a href="/wiki/Harshad_number" title="Harshad number">Harshad</a></li> <li><a href="/wiki/Polydivisible_number" title="Polydivisible number">Polydivisible</a></li> <li><a href="/wiki/Smith_number" title="Smith number">Smith</a></li> <li><a href="/wiki/Vampire_number" title="Vampire number">Vampire</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Friedman_number" title="Friedman number">Friedman</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Binary_numbers743" style="font-size:114%;margin:0 4em"><a href="/wiki/Binary_number" title="Binary number">Binary numbers</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Evil_number" title="Evil number">Evil</a></li> <li><a href="/wiki/Odious_number" title="Odious number">Odious</a></li> <li><a href="/wiki/Pernicious_number" title="Pernicious number">Pernicious</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Generated_via_a_sieve743" style="font-size:114%;margin:0 4em">Generated via a <a href="/wiki/Sieve_theory" title="Sieve theory">sieve</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Lucky_number" title="Lucky number">Lucky</a></li> <li><a href="/wiki/Generation_of_primes" title="Generation of primes">Prime</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Sorting_related743" style="font-size:114%;margin:0 4em"><a href="/wiki/Sorting_algorithm" title="Sorting algorithm">Sorting</a> related</div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Pancake_sorting" title="Pancake sorting">Pancake number</a></li> <li><a href="/wiki/Sorting_number" title="Sorting number">Sorting number</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Natural_language_related743" style="font-size:114%;margin:0 4em"><a href="/wiki/Natural_language" title="Natural language">Natural language</a> related</div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Aronson%27s_sequence" title="Aronson's sequence">Aronson's sequence</a></li> <li><a href="/wiki/Ban_number" title="Ban number">Ban</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Graphemics_related743" style="font-size:114%;margin:0 4em"><a href="/wiki/Graphemics" title="Graphemics">Graphemics</a> related</div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Strobogrammatic_number" title="Strobogrammatic number">Strobogrammatic</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><td class="navbox-abovebelow hlist" colspan="2" style="font-weight:bold;"><div> <ul><li><span class="noviewer" typeof="mw:File"><a href="/wiki/File:Symbol_portal_class.svg" class="mw-file-description" title="Portal"><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/e/e2/Symbol_portal_class.svg/16px-Symbol_portal_class.svg.png" decoding="async" width="16" height="16" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/e/e2/Symbol_portal_class.svg/23px-Symbol_portal_class.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/e/e2/Symbol_portal_class.svg/31px-Symbol_portal_class.svg.png 2x" data-file-width="180" data-file-height="185" /></a></span> <a href="/wiki/Portal:Mathematics" title="Portal:Mathematics">Mathematics portal</a></li></ul> </div></td></tr></tbody></table></div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?useformat=desktop&type=1x1&usesul3=0" 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=Euler_pseudoprime&oldid=1257754025">https://en.wikipedia.org/w/index.php?title=Euler_pseudoprime&oldid=1257754025</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:Pseudoprimes" title="Category:Pseudoprimes">Pseudoprimes</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_matches_Wikidata" title="Category:Short description matches Wikidata">Short description matches Wikidata</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> This page was last edited on 16 November 2024, at 13:30<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=Euler_pseudoprime&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"><picture><source media="(min-width: 500px)" srcset="/static/images/footer/wikimedia-button.svg" width="84" height="29"><img src="/static/images/footer/wikimedia.svg" width="25" height="25" alt="Wikimedia Foundation" lang="en" loading="lazy"></picture></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"><picture><source media="(min-width: 500px)" srcset="/w/resources/assets/poweredby_mediawiki.svg" width="88" height="31"><img src="/w/resources/assets/mediawiki_compact.svg" alt="Powered by MediaWiki" width="25" height="25" loading="lazy"></picture></a></li> </ul> </footer> </div> </div> </div> <div class="vector-header-container vector-sticky-header-container"> <div id="vector-sticky-header" class="vector-sticky-header"> <div class="vector-sticky-header-start"> <div class="vector-sticky-header-icon-start vector-button-flush-left vector-button-flush-right" aria-hidden="true"> <button class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-sticky-header-search-toggle" tabindex="-1" data-event-name="ui.vector-sticky-search-form.icon"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </button> </div> <div role="search" class="vector-search-box-vue vector-search-box-show-thumbnail vector-search-box"> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail"> <form action="/w/index.php" id="vector-sticky-search-form" class="cdx-search-input cdx-search-input--has-end-button"> <div 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"> <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> <div class="vector-sticky-header-context-bar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-sticky-header-toc" class="vector-dropdown mw-portlet mw-portlet-sticky-header-toc vector-sticky-header-toc vector-button-flush-left" > <input type="checkbox" id="vector-sticky-header-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-sticky-header-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-sticky-header-toc-label" for="vector-sticky-header-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-sticky-header-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div class="vector-sticky-header-context-bar-primary" aria-hidden="true" ><span class="mw-page-title-main">Euler pseudoprime</span></div> </div> </div> <div class="vector-sticky-header-end" aria-hidden="true"> <div class="vector-sticky-header-icons"> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-talk-sticky-header" tabindex="-1" data-event-name="talk-sticky-header"><span class="vector-icon mw-ui-icon-speechBubbles mw-ui-icon-wikimedia-speechBubbles"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-subject-sticky-header" tabindex="-1" data-event-name="subject-sticky-header"><span class="vector-icon mw-ui-icon-article mw-ui-icon-wikimedia-article"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-history-sticky-header" tabindex="-1" data-event-name="history-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-history mw-ui-icon-wikimedia-wikimedia-history"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only mw-watchlink" id="ca-watchstar-sticky-header" tabindex="-1" data-event-name="watch-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-star mw-ui-icon-wikimedia-wikimedia-star"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-edit-sticky-header" tabindex="-1" data-event-name="wikitext-edit-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-wikiText mw-ui-icon-wikimedia-wikimedia-wikiText"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-ve-edit-sticky-header" tabindex="-1" data-event-name="ve-edit-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-edit mw-ui-icon-wikimedia-wikimedia-edit"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-viewsource-sticky-header" tabindex="-1" data-event-name="ve-edit-protected-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-editLock mw-ui-icon-wikimedia-wikimedia-editLock"></span> <span></span> </a> </div> <div class="vector-sticky-header-buttons"> <button class="cdx-button cdx-button--weight-quiet mw-interlanguage-selector" id="p-lang-btn-sticky-header" tabindex="-1" data-event-name="ui.dropdown-p-lang-btn-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-language mw-ui-icon-wikimedia-wikimedia-language"></span> <span>5 languages</span> </button> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive" id="ca-addsection-sticky-header" tabindex="-1" data-event-name="addsection-sticky-header"><span class="vector-icon mw-ui-icon-speechBubbleAdd-progressive mw-ui-icon-wikimedia-speechBubbleAdd-progressive"></span> <span>Add topic</span> </a> </div> <div class="vector-sticky-header-icon-end"> <div class="vector-user-links"> </div> </div> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-d8647bfd6-xtkk4","wgBackendResponseTime":147,"wgPageParseReport":{"limitreport":{"cputime":"0.305","walltime":"0.426","ppvisitednodes":{"value":1195,"limit":1000000},"postexpandincludesize":{"value":109696,"limit":2097152},"templateargumentsize":{"value":737,"limit":2097152},"expansiondepth":{"value":15,"limit":100},"expensivefunctioncount":{"value":2,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":14048,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 296.832 1 -total"," 35.10% 104.174 1 Template:Classes_of_natural_numbers"," 33.71% 100.067 1 Template:Navbox_with_collapsible_groups"," 29.69% 88.144 1 Template:Reflist"," 24.85% 73.756 1 Template:Cite_journal"," 19.13% 56.773 1 Template:Short_description"," 11.35% 33.690 2 Template:Pagetype"," 8.90% 26.418 1 Template:R"," 6.99% 20.742 1 Template:R/ref"," 6.21% 18.438 7 Template:Navbox"]},"scribunto":{"limitreport-timeusage":{"value":"0.167","limit":"10.000"},"limitreport-memusage":{"value":4593507,"limit":52428800}},"cachereport":{"origin":"mw-web.codfw.main-c7f495d9b-chzgf","timestamp":"20250219145750","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Euler pseudoprime","url":"https:\/\/en.wikipedia.org\/wiki\/Euler_pseudoprime","sameAs":"http:\/\/www.wikidata.org\/entity\/Q356653","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q356653","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":"2003-05-11T18:32:09Z","dateModified":"2024-11-16T13:30:04Z","headline":"odd composite number which passes the given congruence"}</script> </body> </html>