CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Fermat 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-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available";var cookie=document.cookie.match(/(?:^|; )enwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy", "wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"ed9a061d-4e7a-4861-97ce-d457200c0dd8","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Fermat_pseudoprime","wgTitle":"Fermat pseudoprime","wgCurRevisionId":1259406491,"wgRevisionId":1259406491,"wgArticleId":45891,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Articles with short description","Short description is different from Wikidata","Articles containing German-language text","Pseudoprimes","Asymmetric-key algorithms"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Fermat_pseudoprime","wgRelevantArticleId":45891,"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":40000,"wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":false,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q1406394","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false, "wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.cite.styles":"ready","ext.math.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","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","wikibase.sidebar.tracking"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=en&modules=ext.cite.styles%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cext.wikimediamessages.styles%7Cjquery.makeCollapsible.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.4"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Fermat 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/Fermat_pseudoprime"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Fermat_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/Fermat_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-Fermat_pseudoprime rootpage-Fermat_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" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Main menu" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Main menu</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Main menu</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">hide</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z"><span>Main page</span></a></li><li id="n-contents" class="mw-list-item"><a href="/wiki/Wikipedia:Contents" title="Guides to browsing Wikipedia"><span>Contents</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:Current_events" title="Articles related to current events"><span>Current events</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Random" title="Visit a randomly selected article [x]" accesskey="x"><span>Random article</span></a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:About" title="Learn about Wikipedia and how it works"><span>About Wikipedia</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia"><span>Contact us</span></a></li> </ul> </div> </div> <div id="p-interaction" class="vector-menu mw-portlet mw-portlet-interaction" > <div class="vector-menu-heading"> Contribute </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia"><span>Help</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/Help:Introduction" title="Learn how to edit Wikipedia"><span>Learn to edit</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Community_portal" title="The hub for editors"><span>Community portal</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:RecentChanges" title="A list of recent changes to Wikipedia [r]" accesskey="r"><span>Recent changes</span></a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_upload_wizard" title="Add images or other media for use on Wikipedia"><span>Upload file</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Main_Page" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="The Free Encyclopedia" src="/static/images/mobile/copyright/wikipedia-tagline-en.svg" width="117" height="13" style="width: 7.3125em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Special:Search" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Search Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search Wikipedia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Personal tools"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Appearance" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Appearance</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en" class=""><span>Donate</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:CreateAccount&returnto=Fermat+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=Fermat+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/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en"><span>Donate</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&returnto=Fermat+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=Fermat+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-Definition" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Definition"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Definition</span> </div> </a> <ul id="toc-Definition-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Properties" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Properties"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Properties</span> </div> </a> <button aria-controls="toc-Properties-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Properties subsection</span> </button> <ul id="toc-Properties-sublist" class="vector-toc-list"> <li id="toc-Distribution" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Distribution"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.1</span> <span>Distribution</span> </div> </a> <ul id="toc-Distribution-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Factorizations" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Factorizations"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.2</span> <span>Factorizations</span> </div> </a> <ul id="toc-Factorizations-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Smallest_Fermat_pseudoprimes" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Smallest_Fermat_pseudoprimes"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.3</span> <span>Smallest Fermat pseudoprimes</span> </div> </a> <ul id="toc-Smallest_Fermat_pseudoprimes-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-List_of_Fermat_pseudoprimes_in_fixed_base_n" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#List_of_Fermat_pseudoprimes_in_fixed_base_n"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.4</span> <span>List of Fermat pseudoprimes in fixed base <i>n</i></span> </div> </a> <ul id="toc-List_of_Fermat_pseudoprimes_in_fixed_base_n-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Bases_b_for_which_n_is_a_Fermat_pseudoprime" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Bases_b_for_which_n_is_a_Fermat_pseudoprime"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Bases <i>b</i> for which <i>n</i> is a Fermat pseudoprime</span> </div> </a> <ul id="toc-Bases_b_for_which_n_is_a_Fermat_pseudoprime-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Weak_pseudoprimes" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Weak_pseudoprimes"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Weak pseudoprimes</span> </div> </a> <ul id="toc-Weak_pseudoprimes-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Euler–Jacobi_pseudoprimes" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Euler–Jacobi_pseudoprimes"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Euler–Jacobi pseudoprimes</span> </div> </a> <ul id="toc-Euler–Jacobi_pseudoprimes-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Applications" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Applications"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>Applications</span> </div> </a> <ul id="toc-Applications-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">7</span> <span>References</span> </div> </a> <ul id="toc-References-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-External_links" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#External_links"> <div class="vector-toc-text"> <span class="vector-toc-numb">8</span> <span>External links</span> </div> </a> <ul id="toc-External_links-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Fermat 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 6 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-6" 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">6 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-ar mw-list-item"><a href="https://ar.wikipedia.org/wiki/%D8%A3%D8%B9%D8%AF%D8%A7%D8%AF_%D9%81%D9%8A%D8%B1%D9%85%D8%A7_%D8%B4%D8%A8%D9%87_%D8%A7%D9%84%D8%A3%D9%88%D9%84%D9%8A%D8%A9" title="أعداد فيرما شبه الأولية – Arabic" lang="ar" hreflang="ar" data-title="أعداد فيرما شبه الأولية" data-language-autonym="العربية" data-language-local-name="Arabic" class="interlanguage-link-target"><span>العربية</span></a></li><li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Fermatsche_Pseudoprimzahl" title="Fermatsche Pseudoprimzahl – German" lang="de" hreflang="de" data-title="Fermatsche 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_Fermat" title="Número pseudoprimo de Fermat – Spanish" lang="es" hreflang="es" data-title="Número pseudoprimo de Fermat" 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-ru badge-Q17559452 badge-recommendedarticle mw-list-item" title="recommended article"><a href="https://ru.wikipedia.org/wiki/%D0%9F%D1%81%D0%B5%D0%B2%D0%B4%D0%BE%D0%BF%D1%80%D0%BE%D1%81%D1%82%D1%8B%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B5%D1%80%D0%BC%D0%B0" title="Псевдопростые числа Ферма – Russian" lang="ru" hreflang="ru" data-title="Псевдопростые числа Ферма" data-language-autonym="Русский" data-language-local-name="Russian" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-sv mw-list-item"><a href="https://sv.wikipedia.org/wiki/Fermatpseudoprimtal" title="Fermatpseudoprimtal – Swedish" lang="sv" hreflang="sv" data-title="Fermatpseudoprimtal" data-language-autonym="Svenska" data-language-local-name="Swedish" class="interlanguage-link-target"><span>Svenska</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E8%B4%B9%E9%A9%AC%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/Q1406394#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/Fermat_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:Fermat_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/Fermat_pseudoprime"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Fermat_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=Fermat_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/Fermat_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=Fermat_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=Fermat_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/Fermat_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/Fermat_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="/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages" title="A list of all special pages [q]" accesskey="q"><span>Special pages</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Fermat_pseudoprime&oldid=1259406491" 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=Fermat_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=Fermat_pseudoprime&id=1259406491&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%2FFermat_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%2FFermat_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=Fermat_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=Fermat_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/Q1406394" 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">Composite number that passes Fermat's probable primality test</div> <p>In <a href="/wiki/Number_theory" title="Number theory">number theory</a>, the <b>Fermat pseudoprimes</b> make up the most important class of <a href="/wiki/Pseudoprime" title="Pseudoprime">pseudoprimes</a> that come from <a href="/wiki/Fermat%27s_little_theorem" title="Fermat's little theorem">Fermat's little theorem</a>. </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Fermat_pseudoprime&action=edit&section=1" title="Edit section: Definition"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p><a href="/wiki/Fermat%27s_little_theorem" title="Fermat's little theorem">Fermat's little theorem</a> states that if <i>p</i> is prime and <i>a</i> is <a href="/wiki/Coprime" class="mw-redirect" title="Coprime">coprime</a> to <i>p</i>, then <i>a</i><sup><i>p</i>−1</sup> − 1 is <a href="/wiki/Divisor" title="Divisor">divisible</a> by <i>p</i>. For a positive integer <i>a</i>, if a composite integer <i>x</i> divides <i>a</i><sup><i>x</i>−1</sup> − 1, then <i>x</i> is called a <b>Fermat pseudoprime</b> to base <i>a</i>. <sup id="cite_ref-JoyOfFactoring_1-0" class="reference"><a href="#cite_note-JoyOfFactoring-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page / location: Def. 3.32">: Def. 3.32 </span></sup> In other words, a composite integer is a Fermat pseudoprime to base <i>a</i> if it successfully passes the <a href="/wiki/Fermat_primality_test" title="Fermat primality test">Fermat primality test</a> for the base <i>a</i>.<sup id="cite_ref-desmedt-10-23_2-0" class="reference"><a href="#cite_note-desmedt-10-23-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> The false statement that all numbers that pass the Fermat primality test for base 2 are prime is called the <a href="/wiki/Chinese_hypothesis" title="Chinese hypothesis">Chinese hypothesis</a>. </p><p>The smallest base-2 Fermat pseudoprime is 341. It is not a prime, since it equals 11·31, but it satisfies Fermat's little theorem: 2<sup>340</sup> ≡ 1 (mod 341) and thus passes the <a href="/wiki/Fermat_primality_test" title="Fermat primality test">Fermat primality test</a> for the base 2. </p><p>Pseudoprimes to base 2 are sometimes called <b>Sarrus numbers</b>, after <a href="/wiki/Pierre_Fr%C3%A9d%C3%A9ric_Sarrus" title="Pierre Frédéric Sarrus">P. F. Sarrus</a> who discovered that 341 has this property, <b>Poulet numbers</b>, after <a href="/wiki/Paul_Poulet" title="Paul Poulet">P. Poulet</a> who made a table of such numbers, or <b>Fermatians</b> (sequence <span class="nowrap external"><a href="//oeis.org/A001567" class="extiw" title="oeis:A001567">A001567</a></span> in the <a href="/wiki/On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>). </p><p>A Fermat pseudoprime is often called a <b>pseudoprime</b>, with the modifier <b>Fermat</b> being understood. </p><p>An integer <i>x</i> that is a Fermat pseudoprime for all values of <i>a</i> that are coprime to <i>x</i> is called a <a href="/wiki/Carmichael_number" title="Carmichael number">Carmichael number</a>.<sup id="cite_ref-desmedt-10-23_2-1" class="reference"><a href="#cite_note-desmedt-10-23-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-JoyOfFactoring_1-1" class="reference"><a href="#cite_note-JoyOfFactoring-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page / location: Def. 3.34">: Def. 3.34 </span></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Properties">Properties</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Fermat_pseudoprime&action=edit&section=2" title="Edit section: Properties"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Distribution">Distribution</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Fermat_pseudoprime&action=edit&section=3" title="Edit section: Distribution"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>There are infinitely many pseudoprimes to any given base <i>a</i> > 1. In 1904, Cipolla showed how to produce an infinite number of pseudoprimes to base <i>a</i> > 1: let <i>A</i> = (<i>a</i><sup><i>p</i></sup> - 1)/(<i>a</i> - 1) and let <i>B</i> = (<i>a</i><sup><i>p</i></sup> + 1)/(<i>a</i> + 1), where <i>p</i> is a prime number that does not divide <i>a</i>(<i>a</i><sup><i>2</i></sup> - 1). Then <i>n</i> = <i>AB</i> is composite, and is a pseudoprime to base <i>a</i>.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> For example, if <i>a</i> = 2 and <i>p</i> = 5, then <i>A</i> = 31, <i>B</i> = 11, and <i>n</i> = 341 is a pseudoprime to base 2. </p><p>In fact, there are infinitely many <a href="/wiki/Strong_pseudoprime" title="Strong pseudoprime">strong pseudoprimes</a> to any base greater than 1 (see Theorem 1 of <sup id="cite_ref-PSW_5-0" class="reference"><a href="#cite_note-PSW-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup>) and infinitely many Carmichael numbers,<sup id="cite_ref-Alford1994_6-0" class="reference"><a href="#cite_note-Alford1994-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> but they are comparatively rare. There are three pseudoprimes to base 2 below 1000, 245 below one million, and 21853 less than 25·10<sup>9</sup>. There are 4842 strong pseudoprimes base 2 and 2163 Carmichael numbers below this limit (see Table 1 of <sup id="cite_ref-PSW_5-1" class="reference"><a href="#cite_note-PSW-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup>). </p><p>Starting at 17·257, the product of consecutive Fermat numbers is a base-2 pseudoprime, and so are all <a href="/wiki/Fermat_prime" class="mw-redirect" title="Fermat prime">Fermat composites</a> and <a href="/wiki/Mersenne_prime" title="Mersenne prime">Mersenne composites</a>. </p><p>The probability of a composite number n passing the Fermat test approaches zero for <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\to \infty }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mo stretchy="false">→</mo> <mi mathvariant="normal">∞</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n\to \infty }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a0d55d9b32f6fa8fab6a84ea444a6b5a24bb45e1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.333ex; height:1.843ex;" alt="{\displaystyle n\to \infty }"></span>. Specifically, Kim and Pomerance showed the following: The probability that a random odd number n ≤ x is a Fermat pseudoprime to a random base <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1<b<n-1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>1</mn> <mo><</mo> <mi>b</mi> <mo><</mo> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 1<b<n-1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b8899d5d1441c063e530ad11e457a79535e4ce99" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:13.755ex; height:2.343ex;" alt="{\displaystyle 1<b<n-1}"></span> is less than 2.77·10<sup>-8</sup> for x= 10<sup>100</sup>, and is at most (log x)<sup>-197</sup><10<sup>-10,000</sup> for x≥10<sup>100,000</sup>.<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Factorizations">Factorizations</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Fermat_pseudoprime&action=edit&section=4" title="Edit section: Factorizations"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The factorizations of the 60 Poulet numbers up to 60787, including 13 Carmichael numbers (in bold), are in the following table. </p><p>(sequence <span class="nowrap external"><a href="//oeis.org/A001567" class="extiw" title="oeis:A001567">A001567</a></span> in the <a href="/wiki/On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>) </p> <table border="0" cellpadding="0" cellspacing="0"> <tbody><tr valign="top"> <td> <table class="wikitable"> <caption>Poulet 1 to 15 </caption> <tbody><tr> <td>341</td> <td>11 · 31 </td></tr> <tr> <td><b>561</b></td> <td>3 · 11 · 17 </td></tr> <tr> <td>645</td> <td>3 · 5 · 43 </td></tr> <tr> <td><b>1105</b></td> <td>5 · 13 · 17 </td></tr> <tr> <td>1387</td> <td>19 · 73 </td></tr> <tr> <td><b>1729</b></td> <td>7 · 13 · 19 </td></tr> <tr> <td>1905</td> <td>3 · 5 · 127 </td></tr> <tr> <td>2047</td> <td>23 · 89 </td></tr> <tr> <td><b>2465</b></td> <td>5 · 17 · 29 </td></tr> <tr> <td>2701</td> <td>37 · 73 </td></tr> <tr> <td><b>2821</b></td> <td>7 · 13 · 31 </td></tr> <tr> <td>3277</td> <td>29 · 113 </td></tr> <tr> <td>4033</td> <td>37 · 109 </td></tr> <tr> <td>4369</td> <td>17 · 257 </td></tr> <tr> <td>4371</td> <td>3 · 31 · 47 </td></tr></tbody></table> </td> <td> <table class="wikitable"> <caption>Poulet 16 to 30 </caption> <tbody><tr> <td>4681</td> <td>31 · 151 </td></tr> <tr> <td>5461</td> <td>43 · 127 </td></tr> <tr> <td><b>6601</b></td> <td>7 · 23 · 41 </td></tr> <tr> <td>7957</td> <td>73 · 109 </td></tr> <tr> <td>8321</td> <td>53 · 157 </td></tr> <tr> <td>8481</td> <td>3 · 11 · 257 </td></tr> <tr> <td><b>8911</b></td> <td>7 · 19 · 67 </td></tr> <tr> <td>10261</td> <td>31 · 331 </td></tr> <tr> <td><b>10585</b></td> <td>5 · 29 · 73 </td></tr> <tr> <td>11305</td> <td>5 · 7 · 17 · 19 </td></tr> <tr> <td>12801</td> <td>3 · 17 · 251 </td></tr> <tr> <td>13741</td> <td>7 · 13 · 151 </td></tr> <tr> <td>13747</td> <td>59 · 233 </td></tr> <tr> <td>13981</td> <td>11 · 31 · 41 </td></tr> <tr> <td>14491</td> <td>43 · 337 </td></tr></tbody></table> </td> <td> <table class="wikitable"> <caption>Poulet 31 to 45 </caption> <tbody><tr> <td>15709</td> <td>23 · 683 </td></tr> <tr> <td><b>15841</b></td> <td>7 · 31 · 73 </td></tr> <tr> <td>16705</td> <td>5 · 13 · 257 </td></tr> <tr> <td>18705</td> <td>3 · 5 · 29 · 43 </td></tr> <tr> <td>18721</td> <td>97 · 193 </td></tr> <tr> <td>19951</td> <td>71 · 281 </td></tr> <tr> <td>23001</td> <td>3 · 11 · 17 · 41 </td></tr> <tr> <td>23377</td> <td>97 · 241 </td></tr> <tr> <td>25761</td> <td>3 · 31 · 277 </td></tr> <tr> <td><b>29341</b></td> <td>13 · 37 · 61 </td></tr> <tr> <td>30121</td> <td>7 · 13 · 331 </td></tr> <tr> <td>30889</td> <td>17 · 23 · 79 </td></tr> <tr> <td>31417</td> <td>89 · 353 </td></tr> <tr> <td>31609</td> <td>73 · 433 </td></tr> <tr> <td>31621</td> <td>103 · 307 </td></tr></tbody></table> </td> <td> <table class="wikitable"> <caption>Poulet 46 to 60 </caption> <tbody><tr> <td>33153</td> <td>3 · 43 · 257 </td></tr> <tr> <td>34945</td> <td>5 · 29 · 241 </td></tr> <tr> <td>35333</td> <td>89 · 397 </td></tr> <tr> <td>39865</td> <td>5 · 7 · 17 · 67 </td></tr> <tr> <td><b>41041</b></td> <td>7 · 11 · 13 · 41 </td></tr> <tr> <td>41665</td> <td>5 · 13 · 641 </td></tr> <tr> <td>42799</td> <td>127 · 337 </td></tr> <tr> <td><b>46657</b></td> <td>13 · 37 · 97 </td></tr> <tr> <td>49141</td> <td>157 · 313 </td></tr> <tr> <td>49981</td> <td>151 · 331 </td></tr> <tr> <td><b>52633</b></td> <td>7 · 73 · 103 </td></tr> <tr> <td>55245</td> <td>3 · 5 · 29 · 127 </td></tr> <tr> <td>57421</td> <td>7 · 13 · 631 </td></tr> <tr> <td>60701</td> <td>101 · 601 </td></tr> <tr> <td>60787</td> <td>89 · 683 </td></tr></tbody></table> </td></tr></tbody></table> <p>A Poulet number all of whose divisors <i>d</i> divide 2<sup><i>d</i></sup> − 2 is called a <a href="/wiki/Super-Poulet_number" title="Super-Poulet number">super-Poulet number</a>. There are infinitely many Poulet numbers which are not super-Poulet Numbers.<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Smallest_Fermat_pseudoprimes">Smallest Fermat pseudoprimes</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Fermat_pseudoprime&action=edit&section=5" title="Edit section: Smallest Fermat pseudoprimes"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The smallest pseudoprime for each base <i>a</i> ≤ 200 is given in the following table; the colors mark the number of prime factors. Unlike in the definition at the start of the article, pseudoprimes below <i>a</i> are excluded in the table. (For that to allow pseudoprimes below <i>a</i>, see <span class="nowrap external"><a href="/wiki/On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>: <a href="//oeis.org/A090086" class="extiw" title="oeis:A090086">A090086</a></span>) </p><p>(sequence <span class="nowrap external"><a href="//oeis.org/A007535" class="extiw" title="oeis:A007535">A007535</a></span> in the <a href="/wiki/On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>) </p> <table class="wikitable"> <tbody><tr> <th><i>a</i> </th> <th>smallest p-p </th> <th><i>a</i> </th> <th>smallest p-p </th> <th><i>a</i> </th> <th>smallest p-p </th> <th><i>a</i> </th> <th>smallest p-p </th></tr> <tr> <td bgcolor="#FFCBCB">1 </td> <td bgcolor="#FFCBCB">4 = 2² </td> <td>51 </td> <td>65 = 5 · 13 </td> <td bgcolor="#FFEBAD">101 </td> <td bgcolor="#FFEBAD">175 = 5² · 7 </td> <td bgcolor="#FFEBAD">151 </td> <td bgcolor="#FFEBAD">175 = 5² · 7 </td></tr> <tr> <td>2 </td> <td>341 = 11 · 31 </td> <td>52 </td> <td>85 = 5 · 17 </td> <td>102 </td> <td>133 = 7 · 19 </td> <td bgcolor="#FFEBAD">152 </td> <td bgcolor="#FFEBAD">153 = 3² · 17 </td></tr> <tr> <td>3 </td> <td>91 = 7 · 13 </td> <td>53 </td> <td>65 = 5 · 13 </td> <td>103 </td> <td>133 = 7 · 19 </td> <td>153 </td> <td>209 = 11 · 19 </td></tr> <tr> <td>4 </td> <td>15 = 3 · 5 </td> <td>54 </td> <td>55 = 5 · 11 </td> <td bgcolor="#B3B7FF">104 </td> <td bgcolor="#B3B7FF">105 = 3 · 5 · 7 </td> <td>154 </td> <td>155 = 5 · 31 </td></tr> <tr> <td bgcolor="#FFEBAD">5 </td> <td bgcolor="#FFEBAD">124 = 2² · 31 </td> <td bgcolor="#FFEBAD">55 </td> <td bgcolor="#FFEBAD">63 = 3² · 7 </td> <td>105 </td> <td>451 = 11 · 41 </td> <td bgcolor="#B3B7FF">155 </td> <td bgcolor="#B3B7FF">231 = 3 · 7 · 11 </td></tr> <tr> <td>6 </td> <td>35 = 5 · 7 </td> <td>56 </td> <td>57 = 3 · 19 </td> <td>106 </td> <td>133 = 7 · 19 </td> <td>156 </td> <td>217 = 7 · 31 </td></tr> <tr> <td bgcolor="#FFCBCB">7 </td> <td bgcolor="#FFCBCB">25 = 5² </td> <td>57 </td> <td>65 = 5 · 13 </td> <td>107 </td> <td>133 = 7 · 19 </td> <td bgcolor="#B3B7FF">157 </td> <td bgcolor="#B3B7FF">186 = 2 · 3 · 31 </td></tr> <tr> <td bgcolor="#FFCBCB">8 </td> <td bgcolor="#FFCBCB">9 = 3² </td> <td>58 </td> <td>133 = 7 · 19 </td> <td>108 </td> <td>341 = 11 · 31 </td> <td>158 </td> <td>159 = 3 · 53 </td></tr> <tr> <td bgcolor="#FFEBAD">9 </td> <td bgcolor="#FFEBAD">28 = 2² · 7 </td> <td>59 </td> <td>87 = 3 · 29 </td> <td bgcolor="#FFEBAD">109 </td> <td bgcolor="#FFEBAD">117 = 3² · 13 </td> <td>159 </td> <td>247 = 13 · 19 </td></tr> <tr> <td>10 </td> <td>33 = 3 · 11 </td> <td>60 </td> <td>341 = 11 · 31 </td> <td>110 </td> <td>111 = 3 · 37 </td> <td>160 </td> <td>161 = 7 · 23 </td></tr> <tr> <td>11 </td> <td>15 = 3 · 5 </td> <td>61 </td> <td>91 = 7 · 13 </td> <td bgcolor="#B3B7FF">111 </td> <td bgcolor="#B3B7FF">190 = 2 · 5 · 19 </td> <td bgcolor="#B3B7FF">161 </td> <td bgcolor="#B3B7FF">190 = 2 · 5 · 19 </td></tr> <tr> <td>12 </td> <td>65 = 5 · 13 </td> <td bgcolor="#FFEBAD">62 </td> <td bgcolor="#FFEBAD">63 = 3² · 7 </td> <td bgcolor="#FFCBCB">112 </td> <td bgcolor="#FFCBCB">121 = 11² </td> <td>162 </td> <td>481 = 13 · 37 </td></tr> <tr> <td>13 </td> <td>21 = 3 · 7 </td> <td>63 </td> <td>341 = 11 · 31 </td> <td>113 </td> <td>133 = 7 · 19 </td> <td bgcolor="#B3B7FF">163 </td> <td bgcolor="#B3B7FF">186 = 2 · 3 · 31 </td></tr> <tr> <td>14 </td> <td>15 = 3 · 5 </td> <td>64 </td> <td>65 = 5 · 13 </td> <td>114 </td> <td>115 = 5 · 23 </td> <td bgcolor="#B3B7FF">164 </td> <td bgcolor="#B3B7FF">165 = 3 · 5 · 11 </td></tr> <tr> <td>15 </td> <td>341 = 11 · 31 </td> <td bgcolor="#FFEBAD">65 </td> <td bgcolor="#FFEBAD">112 = 2⁴ · 7 </td> <td>115 </td> <td>133 = 7 · 19 </td> <td bgcolor="#FFEBAD">165 </td> <td bgcolor="#FFEBAD">172 = 2² · 43 </td></tr> <tr> <td>16 </td> <td>51 = 3 · 17 </td> <td>66 </td> <td>91 = 7 · 13 </td> <td bgcolor="#FFEBAD">116 </td> <td bgcolor="#FFEBAD">117 = 3² · 13 </td> <td>166 </td> <td>301 = 7 · 43 </td></tr> <tr> <td bgcolor="#FFEBAD">17 </td> <td bgcolor="#FFEBAD">45 = 3² · 5 </td> <td>67 </td> <td>85 = 5 · 17 </td> <td>117 </td> <td>145 = 5 · 29 </td> <td bgcolor="#B3B7FF">167 </td> <td bgcolor="#B3B7FF">231 = 3 · 7 · 11 </td></tr> <tr> <td bgcolor="#FFCBCB">18 </td> <td bgcolor="#FFCBCB">25 = 5² </td> <td>68 </td> <td>69 = 3 · 23 </td> <td>118 </td> <td>119 = 7 · 17 </td> <td bgcolor="#FFCBCB">168 </td> <td bgcolor="#FFCBCB">169 = 13² </td></tr> <tr> <td bgcolor="#FFEBAD">19 </td> <td bgcolor="#FFEBAD">45 = 3² · 5 </td> <td>69 </td> <td>85 = 5 · 17 </td> <td>119 </td> <td>177 = 3 · 59 </td> <td bgcolor="#B3B7FF">169 </td> <td bgcolor="#B3B7FF">231 = 3 · 7 · 11 </td></tr> <tr> <td>20 </td> <td>21 = 3 · 7 </td> <td bgcolor="#FFCBCB">70 </td> <td bgcolor="#FFCBCB">169 = 13² </td> <td bgcolor="#FFCBCB">120 </td> <td bgcolor="#FFCBCB">121 = 11² </td> <td bgcolor="#FFEBAD">170 </td> <td bgcolor="#FFEBAD">171 = 3² · 19 </td></tr> <tr> <td>21 </td> <td>55 = 5 · 11 </td> <td bgcolor="#B3B7FF">71 </td> <td bgcolor="#B3B7FF">105 = 3 · 5 · 7 </td> <td>121 </td> <td>133 = 7 · 19 </td> <td>171 </td> <td>215 = 5 · 43 </td></tr> <tr> <td>22 </td> <td>69 = 3 · 23 </td> <td>72 </td> <td>85 = 5 · 17 </td> <td>122 </td> <td>123 = 3 · 41 </td> <td>172 </td> <td>247 = 13 · 19 </td></tr> <tr> <td>23 </td> <td>33 = 3 · 11 </td> <td>73 </td> <td>111 = 3 · 37 </td> <td>123 </td> <td>217 = 7 · 31 </td> <td>173 </td> <td>205 = 5 · 41 </td></tr> <tr> <td bgcolor="#FFCBCB">24 </td> <td bgcolor="#FFCBCB">25 = 5² </td> <td bgcolor="#FFEBAD">74 </td> <td bgcolor="#FFEBAD">75 = 3 · 5² </td> <td bgcolor="#FFEBAD">124 </td> <td bgcolor="#FFEBAD">125 = 5³ </td> <td bgcolor="#FFEBAD">174 </td> <td bgcolor="#FFEBAD">175 = 5² · 7 </td></tr> <tr> <td bgcolor="#FFEBAD">25 </td> <td bgcolor="#FFEBAD">28 = 2² · 7 </td> <td>75 </td> <td>91 = 7 · 13 </td> <td>125 </td> <td>133 = 7 · 19 </td> <td>175 </td> <td>319 = 11 · 19 </td></tr> <tr> <td bgcolor="#FFEBAD">26 </td> <td bgcolor="#FFEBAD">27 = 3³ </td> <td>76 </td> <td>77 = 7 · 11 </td> <td>126 </td> <td>247 = 13 · 19 </td> <td>176 </td> <td>177 = 3 · 59 </td></tr> <tr> <td>27 </td> <td>65 = 5 · 13 </td> <td>77 </td> <td>247 = 13 · 19 </td> <td bgcolor="#FFEBAD">127 </td> <td bgcolor="#FFEBAD">153 = 3² · 17 </td> <td bgcolor="#FFEBAD">177 </td> <td bgcolor="#FFEBAD">196 = 2² · 7² </td></tr> <tr> <td bgcolor="#FFEBAD">28 </td> <td bgcolor="#FFEBAD">45 = 3² · 5 </td> <td>78 </td> <td>341 = 11 · 31 </td> <td>128 </td> <td>129 = 3 · 43 </td> <td>178 </td> <td>247 = 13 · 19 </td></tr> <tr> <td>29 </td> <td>35 = 5 · 7 </td> <td>79 </td> <td>91 = 7 · 13 </td> <td>129 </td> <td>217 = 7 · 31 </td> <td>179 </td> <td>185 = 5 · 37 </td></tr> <tr> <td bgcolor="#FFCBCB">30 </td> <td bgcolor="#FFCBCB">49 = 7² </td> <td bgcolor="#FFEBAD">80 </td> <td bgcolor="#FFEBAD">81 = 3⁴ </td> <td>130 </td> <td>217 = 7 · 31 </td> <td>180 </td> <td>217 = 7 · 31 </td></tr> <tr> <td bgcolor="#FFCBCB">31 </td> <td bgcolor="#FFCBCB">49 = 7² </td> <td>81 </td> <td>85 = 5 · 17 </td> <td>131 </td> <td>143 = 11 · 13 </td> <td bgcolor="#B3B7FF">181 </td> <td bgcolor="#B3B7FF">195 = 3 · 5 · 13 </td></tr> <tr> <td>32 </td> <td>33 = 3 · 11 </td> <td>82 </td> <td>91 = 7 · 13 </td> <td>132 </td> <td>133 = 7 · 19 </td> <td>182 </td> <td>183 = 3 · 61 </td></tr> <tr> <td>33 </td> <td>85 = 5 · 17 </td> <td bgcolor="#B3B7FF">83 </td> <td bgcolor="#B3B7FF">105 = 3 · 5 · 7 </td> <td>133 </td> <td>145 = 5 · 29 </td> <td>183 </td> <td>221 = 13 · 17 </td></tr> <tr> <td>34 </td> <td>35 = 5 · 7 </td> <td>84 </td> <td>85 = 5 · 17 </td> <td bgcolor="#FFEBAD">134 </td> <td bgcolor="#FFEBAD">135 = 3³ · 5 </td> <td>184 </td> <td>185 = 5 · 37 </td></tr> <tr> <td>35 </td> <td>51 = 3 · 17 </td> <td>85 </td> <td>129 = 3 · 43 </td> <td>135 </td> <td>221 = 13 · 17 </td> <td>185 </td> <td>217 = 7 · 31 </td></tr> <tr> <td>36 </td> <td>91 = 7 · 13 </td> <td>86 </td> <td>87 = 3 · 29 </td> <td>136 </td> <td>265 = 5 · 53 </td> <td>186 </td> <td>187 = 11 · 17 </td></tr> <tr> <td bgcolor="#FFEBAD">37 </td> <td bgcolor="#FFEBAD">45 = 3² · 5 </td> <td>87 </td> <td>91 = 7 · 13 </td> <td bgcolor="#FFEBAD">137 </td> <td bgcolor="#FFEBAD">148 = 2² · 37 </td> <td>187 </td> <td>217 = 7 · 31 </td></tr> <tr> <td>38 </td> <td>39 = 3 · 13 </td> <td>88 </td> <td>91 = 7 · 13 </td> <td>138 </td> <td>259 = 7 · 37 </td> <td bgcolor="#FFEBAD">188 </td> <td bgcolor="#FFEBAD">189 = 3³ · 7 </td></tr> <tr> <td>39 </td> <td>95 = 5 · 19 </td> <td bgcolor="#FFEBAD">89 </td> <td bgcolor="#FFEBAD">99 = 3² · 11 </td> <td>139 </td> <td>161 = 7 · 23 </td> <td>189 </td> <td>235 = 5 · 47 </td></tr> <tr> <td>40 </td> <td>91 = 7 · 13 </td> <td>90 </td> <td>91 = 7 · 13 </td> <td>140 </td> <td>141 = 3 · 47 </td> <td bgcolor="#B3B7FF">190 </td> <td bgcolor="#B3B7FF">231 = 3 · 7 · 11 </td></tr> <tr> <td bgcolor="#B3B7FF">41 </td> <td bgcolor="#B3B7FF">105 = 3 · 5 · 7 </td> <td>91 </td> <td>115 = 5 · 23 </td> <td>141 </td> <td>355 = 5 · 71 </td> <td>191 </td> <td>217 = 7 · 31 </td></tr> <tr> <td>42 </td> <td>205 = 5 · 41 </td> <td>92 </td> <td>93 = 3 · 31 </td> <td>142 </td> <td>143 = 11 · 13 </td> <td>192 </td> <td>217 = 7 · 31 </td></tr> <tr> <td>43 </td> <td>77 = 7 · 11 </td> <td>93 </td> <td>301 = 7 · 43 </td> <td>143 </td> <td>213 = 3 · 71 </td> <td bgcolor="#FFEBAD">193 </td> <td bgcolor="#FFEBAD">276 = 2² · 3 · 23 </td></tr> <tr> <td bgcolor="#FFEBAD">44 </td> <td bgcolor="#FFEBAD">45 = 3² · 5 </td> <td>94 </td> <td>95 = 5 · 19 </td> <td>144 </td> <td>145 = 5 · 29 </td> <td bgcolor="#B3B7FF">194 </td> <td bgcolor="#B3B7FF">195 = 3 · 5 · 13 </td></tr> <tr> <td bgcolor="#FFEBAD">45 </td> <td bgcolor="#FFEBAD">76 = 2² · 19 </td> <td>95 </td> <td>141 = 3 · 47 </td> <td bgcolor="#FFEBAD">145 </td> <td bgcolor="#FFEBAD">153 = 3² · 17 </td> <td>195 </td> <td>259 = 7 · 37 </td></tr> <tr> <td>46 </td> <td>133 = 7 · 19 </td> <td>96 </td> <td>133 = 7 · 19 </td> <td bgcolor="#FFEBAD">146 </td> <td bgcolor="#FFEBAD">147 = 3 · 7² </td> <td>196 </td> <td>205 = 5 · 41 </td></tr> <tr> <td>47 </td> <td>65 = 5 · 13 </td> <td bgcolor="#B3B7FF">97 </td> <td bgcolor="#B3B7FF">105 = 3 · 5 · 7 </td> <td bgcolor="#FFCBCB">147 </td> <td bgcolor="#FFCBCB">169 = 13² </td> <td bgcolor="#B3B7FF">197 </td> <td bgcolor="#B3B7FF">231 = 3 · 7 · 11 </td></tr> <tr> <td bgcolor="#FFCBCB">48 </td> <td bgcolor="#FFCBCB">49 = 7² </td> <td bgcolor="#FFEBAD">98 </td> <td bgcolor="#FFEBAD">99 = 3² · 11 </td> <td bgcolor="#B3B7FF">148 </td> <td bgcolor="#B3B7FF">231 = 3 · 7 · 11 </td> <td>198 </td> <td>247 = 13 · 19 </td></tr> <tr> <td bgcolor="#B3B7FF">49 </td> <td bgcolor="#B3B7FF">66 = 2 · 3 · 11 </td> <td>99 </td> <td>145 = 5 · 29 </td> <td bgcolor="#FFEBAD">149 </td> <td bgcolor="#FFEBAD">175 = 5² · 7 </td> <td bgcolor="#FFEBAD">199 </td> <td bgcolor="#FFEBAD">225 = 3² · 5² </td></tr> <tr> <td>50 </td> <td>51 = 3 · 17 </td> <td bgcolor="#FFEBAD">100 </td> <td bgcolor="#FFEBAD">153 = 3² · 17 </td> <td bgcolor="#FFCBCB">150 </td> <td bgcolor="#FFCBCB">169 = 13² </td> <td>200 </td> <td>201 = 3 · 67 </td></tr></tbody></table> <div class="mw-heading mw-heading3"><h3 id="List_of_Fermat_pseudoprimes_in_fixed_base_n">List of Fermat pseudoprimes in fixed base <i>n</i></h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Fermat_pseudoprime&action=edit&section=6" title="Edit section: List of Fermat pseudoprimes in fixed 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>First few Fermat pseudoprimes in base <i>n</i> </td> <td><a href="/wiki/OEIS" class="mw-redirect" title="OEIS">OEIS</a> sequence </td></tr> <tr> <td>1 </td> <td>4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 50, 51, 52, 54, 55, 56, 57, 58, 60, 62, 63, 64, 65, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78, 80, 81, 82, 84, 85, 86, 87, 88, 90, 91, 92, 93, 94, 95, 96, 98, 99, 100, ... (All composites) </td> <td><a href="//oeis.org/A002808" class="extiw" title="oeis:A002808">A002808</a> </td></tr> <tr> <td>2 </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> <td><a href="//oeis.org/A001567" class="extiw" title="oeis:A001567">A001567</a> </td></tr> <tr> <td>3 </td> <td>91, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, 4961, 5551, 6601, 7381, 8401, 8911, ... </td> <td><a href="//oeis.org/A005935" class="extiw" title="oeis:A005935">A005935</a> </td></tr> <tr> <td>4 </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> <td><a href="//oeis.org/A020136" class="extiw" title="oeis:A020136">A020136</a> </td></tr> <tr> <td>5 </td> <td>4, 124, 217, 561, 781, 1541, 1729, 1891, 2821, 4123, 5461, 5611, 5662, 5731, 6601, 7449, 7813, 8029, 8911, 9881, ... </td> <td><a href="//oeis.org/A005936" class="extiw" title="oeis:A005936">A005936</a> </td></tr> <tr> <td>6 </td> <td>35, 185, 217, 301, 481, 1105, 1111, 1261, 1333, 1729, 2465, 2701, 2821, 3421, 3565, 3589, 3913, 4123, 4495, 5713, 6533, 6601, 8029, 8365, 8911, 9331, 9881, ... </td> <td><a href="//oeis.org/A005937" class="extiw" title="oeis:A005937">A005937</a> </td></tr> <tr> <td>7 </td> <td>6, 25, 325, 561, 703, 817, 1105, 1825, 2101, 2353, 2465, 3277, 4525, 4825, 6697, 8321, ... </td> <td><a href="//oeis.org/A005938" class="extiw" title="oeis:A005938">A005938</a> </td></tr> <tr> <td>8 </td> <td>9, 21, 45, 63, 65, 105, 117, 133, 153, 231, 273, 341, 481, 511, 561, 585, 645, 651, 861, 949, 1001, 1105, 1281, 1365, 1387, 1417, 1541, 1649, 1661, 1729, 1785, 1905, 2047, 2169, 2465, 2501, 2701, 2821, 3145, 3171, 3201, 3277, 3605, 3641, 4005, 4033, 4097, 4369, 4371, 4641, 4681, 4921, 5461, 5565, 5963, 6305, 6533, 6601, 6951, 7107, 7161, 7957, 8321, 8481, 8911, 9265, 9709, 9773, 9881, 9945, ... </td> <td><a href="//oeis.org/A020137" class="extiw" title="oeis:A020137">A020137</a> </td></tr> <tr> <td>9 </td> <td>4, 8, 28, 52, 91, 121, 205, 286, 364, 511, 532, 616, 671, 697, 703, 946, 949, 1036, 1105, 1288, 1387, 1541, 1729, 1891, 2465, 2501, 2665, 2701, 2806, 2821, 2926, 3052, 3281, 3367, 3751, 4376, 4636, 4961, 5356, 5551, 6364, 6601, 6643, 7081, 7381, 7913, 8401, 8695, 8744, 8866, 8911, ... </td> <td><a href="//oeis.org/A020138" class="extiw" title="oeis:A020138">A020138</a> </td></tr> <tr> <td>10 </td> <td>9, 33, 91, 99, 259, 451, 481, 561, 657, 703, 909, 1233, 1729, 2409, 2821, 2981, 3333, 3367, 4141, 4187, 4521, 5461, 6533, 6541, 6601, 7107, 7471, 7777, 8149, 8401, 8911, ... </td> <td><a href="//oeis.org/A005939" class="extiw" title="oeis:A005939">A005939</a> </td></tr> <tr> <td>11 </td> <td>10, 15, 70, 133, 190, 259, 305, 481, 645, 703, 793, 1105, 1330, 1729, 2047, 2257, 2465, 2821, 4577, 4921, 5041, 5185, 6601, 7869, 8113, 8170, 8695, 8911, 9730, ... </td> <td><a href="//oeis.org/A020139" class="extiw" title="oeis:A020139">A020139</a> </td></tr> <tr> <td>12 </td> <td>65, 91, 133, 143, 145, 247, 377, 385, 703, 1045, 1099, 1105, 1649, 1729, 1885, 1891, 2041, 2233, 2465, 2701, 2821, 2983, 3367, 3553, 5005, 5365, 5551, 5785, 6061, 6305, 6601, 8911, 9073, ... </td> <td><a href="//oeis.org/A020140" class="extiw" title="oeis:A020140">A020140</a> </td></tr> <tr> <td>13 </td> <td>4, 6, 12, 21, 85, 105, 231, 244, 276, 357, 427, 561, 1099, 1785, 1891, 2465, 2806, 3605, 5028, 5149, 5185, 5565, 6601, 7107, 8841, 8911, 9577, 9637, ... </td> <td><a href="//oeis.org/A020141" class="extiw" title="oeis:A020141">A020141</a> </td></tr> <tr> <td>14 </td> <td>15, 39, 65, 195, 481, 561, 781, 793, 841, 985, 1105, 1111, 1541, 1891, 2257, 2465, 2561, 2665, 2743, 3277, 5185, 5713, 6501, 6533, 6541, 7107, 7171, 7449, 7543, 7585, 8321, 9073, ... </td> <td><a href="//oeis.org/A020142" class="extiw" title="oeis:A020142">A020142</a> </td></tr> <tr> <td>15 </td> <td>14, 341, 742, 946, 1477, 1541, 1687, 1729, 1891, 1921, 2821, 3133, 3277, 4187, 6541, 6601, 7471, 8701, 8911, 9073, ... </td> <td><a href="//oeis.org/A020143" class="extiw" title="oeis:A020143">A020143</a> </td></tr> <tr> <td>16 </td> <td>15, 51, 85, 91, 255, 341, 435, 451, 561, 595, 645, 703, 1105, 1247, 1261, 1271, 1285, 1387, 1581, 1687, 1695, 1729, 1891, 1905, 2047, 2071, 2091, 2431, 2465, 2701, 2821, 3133, 3277, 3367, 3655, 3683, 4033, 4369, 4371, 4681, 4795, 4859, 5083, 5151, 5461, 5551, 6601, 6643, 7471, 7735, 7957, 8119, 8227, 8245, 8321, 8481, 8695, 8749, 8911, 9061, 9131, 9211, 9605, 9919, ... </td> <td><a href="//oeis.org/A020144" class="extiw" title="oeis:A020144">A020144</a> </td></tr> <tr> <td>17 </td> <td>4, 8, 9, 16, 45, 91, 145, 261, 781, 1111, 1228, 1305, 1729, 1885, 2149, 2821, 3991, 4005, 4033, 4187, 4912, 5365, 5662, 5833, 6601, 6697, 7171, 8481, 8911, ... </td> <td><a href="//oeis.org/A020145" class="extiw" title="oeis:A020145">A020145</a> </td></tr> <tr> <td>18 </td> <td>25, 49, 65, 85, 133, 221, 323, 325, 343, 425, 451, 637, 931, 1105, 1225, 1369, 1387, 1649, 1729, 1921, 2149, 2465, 2701, 2821, 2825, 2977, 3325, 4165, 4577, 4753, 5525, 5725, 5833, 5941, 6305, 6517, 6601, 7345, 8911, 9061, ... </td> <td><a href="//oeis.org/A020146" class="extiw" title="oeis:A020146">A020146</a> </td></tr> <tr> <td>19 </td> <td>6, 9, 15, 18, 45, 49, 153, 169, 343, 561, 637, 889, 905, 906, 1035, 1105, 1629, 1661, 1849, 1891, 2353, 2465, 2701, 2821, 2955, 3201, 4033, 4681, 5461, 5466, 5713, 6223, 6541, 6601, 6697, 7957, 8145, 8281, 8401, 8869, 9211, 9997, ... </td> <td><a href="//oeis.org/A020147" class="extiw" title="oeis:A020147">A020147</a> </td></tr> <tr> <td>20 </td> <td>21, 57, 133, 231, 399, 561, 671, 861, 889, 1281, 1653, 1729, 1891, 2059, 2413, 2501, 2761, 2821, 2947, 3059, 3201, 4047, 5271, 5461, 5473, 5713, 5833, 6601, 6817, 7999, 8421, 8911, ... </td> <td><a href="//oeis.org/A020148" class="extiw" title="oeis:A020148">A020148</a> </td></tr> <tr> <td>21 </td> <td>4, 10, 20, 55, 65, 85, 221, 703, 793, 1045, 1105, 1852, 2035, 2465, 3781, 4630, 5185, 5473, 5995, 6541, 7363, 8695, 8965, 9061, ... </td> <td><a href="//oeis.org/A020149" class="extiw" title="oeis:A020149">A020149</a> </td></tr> <tr> <td>22 </td> <td>21, 69, 91, 105, 161, 169, 345, 483, 485, 645, 805, 1105, 1183, 1247, 1261, 1541, 1649, 1729, 1891, 2037, 2041, 2047, 2413, 2465, 2737, 2821, 3241, 3605, 3801, 5551, 5565, 5963, 6019, 6601, 6693, 7081, 7107, 7267, 7665, 8119, 8365, 8421, 8911, 9453, ... </td> <td><a href="//oeis.org/A020150" class="extiw" title="oeis:A020150">A020150</a> </td></tr> <tr> <td>23 </td> <td>22, 33, 91, 154, 165, 169, 265, 341, 385, 451, 481, 553, 561, 638, 946, 1027, 1045, 1065, 1105, 1183, 1271, 1729, 1738, 1749, 2059, 2321, 2465, 2501, 2701, 2821, 2926, 3097, 3445, 4033, 4081, 4345, 4371, 4681, 5005, 5149, 6253, 6369, 6533, 6541, 7189, 7267, 7957, 8321, 8365, 8651, 8745, 8911, 8965, 9805, ... </td> <td><a href="//oeis.org/A020151" class="extiw" title="oeis:A020151">A020151</a> </td></tr> <tr> <td>24 </td> <td>25, 115, 175, 325, 553, 575, 805, 949, 1105, 1541, 1729, 1771, 1825, 1975, 2413, 2425, 2465, 2701, 2737, 2821, 2885, 3781, 4207, 4537, 6601, 6931, 6943, 7081, 7189, 7471, 7501, 7813, 8725, 8911, 9085, 9361, 9809, ... </td> <td><a href="//oeis.org/A020152" class="extiw" title="oeis:A020152">A020152</a> </td></tr> <tr> <td>25 </td> <td>4, 6, 8, 12, 24, 28, 39, 66, 91, 124, 217, 232, 276, 403, 426, 451, 532, 561, 616, 703, 781, 804, 868, 946, 1128, 1288, 1541, 1729, 1891, 2047, 2701, 2806, 2821, 2911, 2926, 3052, 3126, 3367, 3592, 3976, 4069, 4123, 4207, 4564, 4636, 4686, 5321, 5461, 5551, 5611, 5662, 5731, 5963, 6601, 7449, 7588, 7813, 8029, 8646, 8911, 9881, 9976, ... </td> <td><a href="//oeis.org/A020153" class="extiw" title="oeis:A020153">A020153</a> </td></tr> <tr> <td>26 </td> <td>9, 15, 25, 27, 45, 75, 133, 135, 153, 175, 217, 225, 259, 425, 475, 561, 589, 675, 703, 775, 925, 1035, 1065, 1147, 2465, 3145, 3325, 3385, 3565, 3825, 4123, 4525, 4741, 4921, 5041, 5425, 6093, 6475, 6525, 6601, 6697, 8029, 8695, 8911, 9073, ... </td> <td><a href="//oeis.org/A020154" class="extiw" title="oeis:A020154">A020154</a> </td></tr> <tr> <td>27 </td> <td>26, 65, 91, 121, 133, 247, 259, 286, 341, 365, 481, 671, 703, 949, 1001, 1105, 1541, 1649, 1729, 1891, 2071, 2465, 2665, 2701, 2821, 2981, 2993, 3146, 3281, 3367, 3605, 3751, 4033, 4745, 4921, 4961, 5299, 5461, 5551, 5611, 5621, 6305, 6533, 6601, 7381, 7585, 7957, 8227, 8321, 8401, 8911, 9139, 9709, 9809, 9841, 9881, 9919, ... </td> <td><a href="//oeis.org/A020155" class="extiw" title="oeis:A020155">A020155</a> </td></tr> <tr> <td>28 </td> <td>9, 27, 45, 87, 145, 261, 361, 529, 561, 703, 783, 785, 1105, 1305, 1413, 1431, 1885, 2041, 2413, 2465, 2871, 3201, 3277, 4553, 4699, 5149, 5181, 5365, 7065, 8149, 8321, 8401, 9841, ... </td> <td><a href="//oeis.org/A020156" class="extiw" title="oeis:A020156">A020156</a> </td></tr> <tr> <td>29 </td> <td>4, 14, 15, 21, 28, 35, 52, 91, 105, 231, 268, 341, 364, 469, 481, 561, 651, 793, 871, 1105, 1729, 1876, 1897, 2105, 2257, 2821, 3484, 3523, 4069, 4371, 4411, 5149, 5185, 5356, 5473, 5565, 5611, 6097, 6601, 7161, 7294, 8321, 8401, 8421, 8841, 8911, ... </td> <td><a href="//oeis.org/A020157" class="extiw" title="oeis:A020157">A020157</a> </td></tr> <tr> <td>30 </td> <td>49, 91, 133, 217, 247, 341, 403, 469, 493, 589, 637, 703, 871, 899, 901, 931, 1273, 1519, 1537, 1729, 2059, 2077, 2821, 3097, 3277, 3283, 3367, 3577, 4081, 4097, 4123, 5729, 6031, 6061, 6097, 6409, 6601, 6817, 7657, 8023, 8029, 8401, 8911, 9881, ... </td> <td><a href="//oeis.org/A020158" class="extiw" title="oeis:A020158">A020158</a> </td></tr></tbody></table> <p>For more information (base 31 to 100), see <span class="nowrap external"><a href="/wiki/On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>: <a href="//oeis.org/A020159" class="extiw" title="oeis:A020159">A020159</a></span> to <span class="nowrap external"><a href="/wiki/On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>: <a href="//oeis.org/A020228" class="extiw" title="oeis:A020228">A020228</a></span>, and for all bases up to 150, see <a class="external text" href="https://de.m.wikibooks.org/wiki/Pseudoprimzahlen:_Tabelle_Fermatsche_Pseudoprimzahlen">table of Fermat pseudoprimes (text in German)</a>, this page does not define <i>n</i> is a pseudoprime to a base congruent to 1 or -1 (mod <i>n</i>) </p> <div class="mw-heading mw-heading2"><h2 id="Bases_b_for_which_n_is_a_Fermat_pseudoprime">Bases <i>b</i> for which <i>n</i> is a Fermat pseudoprime</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Fermat_pseudoprime&action=edit&section=7" title="Edit section: Bases b for which n is a Fermat pseudoprime"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>If composite <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span> is even, then <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span> is a Fermat pseudoprime to the trivial base <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b\equiv 1{\pmod {n}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>b</mi> <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 b\equiv 1{\pmod {n}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4edaeabb37d364f3476d9520050656bb35d18493" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.337ex; height:2.843ex;" alt="{\displaystyle b\equiv 1{\pmod {n}}}"></span>. If composite <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span> is odd, then <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span> is a Fermat pseudoprime to the trivial bases <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b\equiv \pm 1{\pmod {n}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>b</mi> <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 b\equiv \pm 1{\pmod {n}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/79886a2535cac048c02ca0e021bbc106b1e4d18a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.145ex; height:2.843ex;" alt="{\displaystyle b\equiv \pm 1{\pmod {n}}}"></span>. </p><p>For any composite <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span>, the <i>number</i> of distinct bases <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>b</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle b}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f11423fbb2e967f986e36804a8ae4271734917c3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}"></span> modulo <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span>, for which <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span> is a Fermat pseudoprime base <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>b</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle b}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f11423fbb2e967f986e36804a8ae4271734917c3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}"></span>, is <sup id="cite_ref-lpsp_9-0" class="reference"><a href="#cite_note-lpsp-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page / location: Thm. 1, p. 1392">: Thm. 1, p. 1392 </span></sup> </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \prod _{i=1}^{k}\gcd(p_{i}-1,n-1)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <munderover> <mo>∏</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>=</mo> <mn>1</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </munderover> <mo movablelimits="true" form="prefix">gcd</mo> <mo stretchy="false">(</mo> <msub> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo>−</mo> <mn>1</mn> <mo>,</mo> <mi>n</mi> <mo>−</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \prod _{i=1}^{k}\gcd(p_{i}-1,n-1)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6a0515675f265a667a627527f3f725e68cc66ceb" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:21.057ex; height:7.343ex;" alt="{\displaystyle \prod _{i=1}^{k}\gcd(p_{i}-1,n-1)}"></span></dd></dl> <p>where <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{1},\dots ,p_{k}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>p</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle p_{1},\dots ,p_{k}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8bd293a6d2f8a9b0c0dadace3afded25f4de7994" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:9.749ex; height:2.009ex;" alt="{\displaystyle p_{1},\dots ,p_{k}}"></span> are the distinct prime factors of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span>. This includes the trivial bases. </p><p>For example, for <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=341=11\cdot 31}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mo>=</mo> <mn>341</mn> <mo>=</mo> <mn>11</mn> <mo>⋅</mo> <mn>31</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n=341=11\cdot 31}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/58d5fc73e61e1a3a0c24c05e7599387259cfe43a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:17.408ex; height:2.176ex;" alt="{\displaystyle n=341=11\cdot 31}"></span>, this product is <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \gcd(10,340)\cdot \gcd(30,340)=100}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo movablelimits="true" form="prefix">gcd</mo> <mo stretchy="false">(</mo> <mn>10</mn> <mo>,</mo> <mn>340</mn> <mo stretchy="false">)</mo> <mo>⋅</mo> <mo movablelimits="true" form="prefix">gcd</mo> <mo stretchy="false">(</mo> <mn>30</mn> <mo>,</mo> <mn>340</mn> <mo stretchy="false">)</mo> <mo>=</mo> <mn>100</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \gcd(10,340)\cdot \gcd(30,340)=100}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e7459e2e3d51891ab40ad43cd5cf103eb8464eb8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:32.551ex; height:2.843ex;" alt="{\displaystyle \gcd(10,340)\cdot \gcd(30,340)=100}"></span>. For <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=341}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mo>=</mo> <mn>341</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n=341}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/72836ab7a34e08e0781cacb05b7e2e7a9da18da7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.981ex; height:2.176ex;" alt="{\displaystyle n=341}"></span>, the smallest such nontrivial base is <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b=2}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>b</mi> <mo>=</mo> <mn>2</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle b=2}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/32584049ed5f72969777f89d69b74ee462875e82" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.258ex; height:2.176ex;" alt="{\displaystyle b=2}"></span>. </p><p>Every odd composite <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span> is a Fermat pseudoprime to at least two nontrivial bases modulo <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span> unless <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span> is a power of 3.<sup id="cite_ref-lpsp_9-1" class="reference"><a href="#cite_note-lpsp-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page / location: Cor. 1, p. 1393">: Cor. 1, p. 1393 </span></sup> </p><p>For composite <i>n</i> < 200, the following is a table of all bases <i>b</i> < <i>n</i> which <i>n</i> is a Fermat pseudoprime. If a composite number <i>n</i> is not in the table (or <i>n</i> is in the sequence <a href="//oeis.org/A209211" class="extiw" title="oeis:A209211">A209211</a>), then <i>n</i> is a pseudoprime only to the trivial base 1 modulo <i>n</i>. </p> <table class="wikitable"> <tbody><tr> <td><i>n</i> </td> <td>bases 0 < <i>b</i> < <i>n</i> to which <i>n</i> is a Fermat pseudoprime </td> <td># of bases<br /><span class="nowrap external"><a href="/wiki/On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>: <a href="//oeis.org/A063994" class="extiw" title="oeis:A063994">A063994</a></span> </td></tr> <tr> <td>9 </td> <td>1, 8 </td> <td>2 </td></tr> <tr> <td>15 </td> <td>1, 4, 11, 14 </td> <td>4 </td></tr> <tr> <td>21 </td> <td>1, 8, 13, 20 </td> <td>4 </td></tr> <tr> <td>25 </td> <td>1, 7, 18, 24 </td> <td>4 </td></tr> <tr> <td>27 </td> <td>1, 26 </td> <td>2 </td></tr> <tr> <td>28 </td> <td>1, 9, 25 </td> <td>3 </td></tr> <tr> <td>33 </td> <td>1, 10, 23, 32 </td> <td>4 </td></tr> <tr> <td>35 </td> <td>1, 6, 29, 34 </td> <td>4 </td></tr> <tr> <td>39 </td> <td>1, 14, 25, 38 </td> <td>4 </td></tr> <tr> <td>45 </td> <td>1, 8, 17, 19, 26, 28, 37, 44 </td> <td>8 </td></tr> <tr> <td>49 </td> <td>1, 18, 19, 30, 31, 48 </td> <td>6 </td></tr> <tr> <td>51 </td> <td>1, 16, 35, 50 </td> <td>4 </td></tr> <tr> <td>52 </td> <td>1, 9, 29 </td> <td>3 </td></tr> <tr> <td>55 </td> <td>1, 21, 34, 54 </td> <td>4 </td></tr> <tr> <td>57 </td> <td>1, 20, 37, 56 </td> <td>4 </td></tr> <tr> <td>63 </td> <td>1, 8, 55, 62 </td> <td>4 </td></tr> <tr> <td>65 </td> <td>1, 8, 12, 14, 18, 21, 27, 31, 34, 38, 44, 47, 51, 53, 57, 64 </td> <td>16 </td></tr> <tr> <td>66 </td> <td>1, 25, 31, 37, 49 </td> <td>5 </td></tr> <tr> <td>69 </td> <td>1, 22, 47, 68 </td> <td>4 </td></tr> <tr> <td>70 </td> <td>1, 11, 51 </td> <td>3 </td></tr> <tr> <td>75 </td> <td>1, 26, 49, 74 </td> <td>4 </td></tr> <tr> <td>76 </td> <td>1, 45, 49 </td> <td>3 </td></tr> <tr> <td>77 </td> <td>1, 34, 43, 76 </td> <td>4 </td></tr> <tr> <td>81 </td> <td>1, 80 </td> <td>2 </td></tr> <tr> <td>85 </td> <td>1, 4, 13, 16, 18, 21, 33, 38, 47, 52, 64, 67, 69, 72, 81, 84 </td> <td>16 </td></tr> <tr> <td>87 </td> <td>1, 28, 59, 86 </td> <td>4 </td></tr> <tr> <td>91 </td> <td>1, 3, 4, 9, 10, 12, 16, 17, 22, 23, 25, 27, 29, 30, 36, 38, 40, 43, 48, 51, 53, 55, 61, 62, 64, 66, 68, 69, 74, 75, 79, 81, 82, 87, 88, 90 </td> <td>36 </td></tr> <tr> <td>93 </td> <td>1, 32, 61, 92 </td> <td>4 </td></tr> <tr> <td>95 </td> <td>1, 39, 56, 94 </td> <td>4 </td></tr> <tr> <td>99 </td> <td>1, 10, 89, 98 </td> <td>4 </td></tr> <tr> <td>105 </td> <td>1, 8, 13, 22, 29, 34, 41, 43, 62, 64, 71, 76, 83, 92, 97, 104 </td> <td>16 </td></tr> <tr> <td>111 </td> <td>1, 38, 73, 110 </td> <td>4 </td></tr> <tr> <td>112 </td> <td>1, 65, 81 </td> <td>3 </td></tr> <tr> <td>115 </td> <td>1, 24, 91, 114 </td> <td>4 </td></tr> <tr> <td>117 </td> <td>1, 8, 44, 53, 64, 73, 109, 116 </td> <td>8 </td></tr> <tr> <td>119 </td> <td>1, 50, 69, 118 </td> <td>4 </td></tr> <tr> <td>121 </td> <td>1, 3, 9, 27, 40, 81, 94, 112, 118, 120 </td> <td>10 </td></tr> <tr> <td>123 </td> <td>1, 40, 83, 122 </td> <td>4 </td></tr> <tr> <td>124 </td> <td>1, 5, 25 </td> <td>3 </td></tr> <tr> <td>125 </td> <td>1, 57, 68, 124 </td> <td>4 </td></tr> <tr> <td>129 </td> <td>1, 44, 85, 128 </td> <td>4 </td></tr> <tr> <td>130 </td> <td>1, 61, 81 </td> <td>3 </td></tr> <tr> <td>133 </td> <td>1, 8, 11, 12, 18, 20, 26, 27, 30, 31, 37, 39, 45, 46, 50, 58, 64, 65, 68, 69, 75, 83, 87, 88, 94, 96, 102, 103, 106, 107, 113, 115, 121, 122, 125, 132 </td> <td>36 </td></tr> <tr> <td>135 </td> <td>1, 26, 109, 134 </td> <td>4 </td></tr> <tr> <td>141 </td> <td>1, 46, 95, 140 </td> <td>4 </td></tr> <tr> <td>143 </td> <td>1, 12, 131, 142 </td> <td>4 </td></tr> <tr> <td>145 </td> <td>1, 12, 17, 28, 41, 46, 57, 59, 86, 88, 99, 104, 117, 128, 133, 144 </td> <td>16 </td></tr> <tr> <td>147 </td> <td>1, 50, 97, 146 </td> <td>4 </td></tr> <tr> <td>148 </td> <td>1, 121, 137 </td> <td>3 </td></tr> <tr> <td>153 </td> <td>1, 8, 19, 26, 35, 53, 55, 64, 89, 98, 100, 118, 127, 134, 145, 152 </td> <td>16 </td></tr> <tr> <td>154 </td> <td>1, 23, 67 </td> <td>3 </td></tr> <tr> <td>155 </td> <td>1, 61, 94, 154 </td> <td>4 </td></tr> <tr> <td>159 </td> <td>1, 52, 107, 158 </td> <td>4 </td></tr> <tr> <td>161 </td> <td>1, 22, 139, 160 </td> <td>4 </td></tr> <tr> <td>165 </td> <td>1, 23, 32, 34, 43, 56, 67, 76, 89, 98, 109, 122, 131, 133, 142, 164 </td> <td>16 </td></tr> <tr> <td>169 </td> <td>1, 19, 22, 23, 70, 80, 89, 99, 146, 147, 150, 168 </td> <td>12 </td></tr> <tr> <td>171 </td> <td>1, 37, 134, 170 </td> <td>4 </td></tr> <tr> <td>172 </td> <td>1, 49, 165 </td> <td>3 </td></tr> <tr> <td>175 </td> <td>1, 24, 26, 51, 74, 76, 99, 101, 124, 149, 151, 174 </td> <td>12 </td></tr> <tr> <td>176 </td> <td>1, 49, 81, 97, 113 </td> <td>5 </td></tr> <tr> <td>177 </td> <td>1, 58, 119, 176 </td> <td>4 </td></tr> <tr> <td>183 </td> <td>1, 62, 121, 182 </td> <td>4 </td></tr> <tr> <td>185 </td> <td>1, 6, 31, 36, 38, 43, 68, 73, 112, 117, 142, 147, 149, 154, 179, 184 </td> <td>16 </td></tr> <tr> <td>186 </td> <td>1, 97, 109, 157, 163 </td> <td>5 </td></tr> <tr> <td>187 </td> <td>1, 67, 120, 186 </td> <td>4 </td></tr> <tr> <td>189 </td> <td>1, 55, 134, 188 </td> <td>4 </td></tr> <tr> <td>190 </td> <td>1, 11, 61, 81, 101, 111, 121, 131, 161 </td> <td>9 </td></tr> <tr> <td>195 </td> <td>1, 14, 64, 79, 116, 131, 181, 194 </td> <td>8 </td></tr> <tr> <td>196 </td> <td>1, 165, 177 </td> <td>3 </td></tr></tbody></table> <p>For more information (<i>n</i> = 201 to 5000), see <span title="German-language text"><span lang="de" style="font-style: normal;"><a href="https://en.wikibooks.org/wiki/de:Pseudoprimzahlen:_Tabelle_Pseudoprimzahlen_(15_-_4999)" class="extiw" title="b:de:Pseudoprimzahlen: Tabelle Pseudoprimzahlen (15 - 4999)">b:de:Pseudoprimzahlen: Tabelle Pseudoprimzahlen (15 - 4999)</a></span></span> (Table of pseudoprimes 16–4999). Unlike the list above, that page excludes the bases 1 and <i>n</i>−1. When <i>p</i> is a prime, <i>p</i><sup>2</sup> is a Fermat pseudoprime to base <i>b</i> <a href="/wiki/If_and_only_if" title="If and only if">if and only if</a> <i>p</i> is a <a href="/wiki/Wieferich_prime" title="Wieferich prime">Wieferich prime</a> to base <i>b</i>. For example, 1093<sup>2</sup> = 1194649 is a Fermat pseudoprime to base 2, and 11<sup>2</sup> = 121 is a Fermat pseudoprime to base 3. </p><p>The number of the values of <i>b</i> for <i>n</i> are (For <i>n</i> prime, the number of the values of <i>b</i> must be <i>n</i> − 1, since all <i>b</i> satisfy the <a href="/wiki/Fermat_little_theorem" class="mw-redirect" title="Fermat little theorem">Fermat little theorem</a>) </p> <dl><dd>1, 1, 2, 1, 4, 1, 6, 1, 2, 1, 10, 1, 12, 1, 4, 1, 16, 1, 18, 1, 4, 1, 22, 1, 4, 1, 2, 3, 28, 1, 30, 1, 4, 1, 4, 1, 36, 1, 4, 1, 40, 1, 42, 1, 8, 1, 46, 1, 6, 1, ... (sequence <span class="nowrap external"><a href="//oeis.org/A063994" class="extiw" title="oeis:A063994">A063994</a></span> in the <a href="/wiki/On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>)</dd></dl> <p>The least base <i>b</i> > 1 which <i>n</i> is a pseudoprime to base <i>b</i> (or prime number) are </p> <dl><dd>2, 3, 2, 5, 2, 7, 2, 9, 8, 11, 2, 13, 2, 15, 4, 17, 2, 19, 2, 21, 8, 23, 2, 25, 7, 27, 26, 9, 2, 31, 2, 33, 10, 35, 6, 37, 2, 39, 14, 41, 2, 43, 2, 45, 8, 47, 2, 49, 18, 51, ... (sequence <span class="nowrap external"><a href="//oeis.org/A105222" class="extiw" title="oeis:A105222">A105222</a></span> in the <a href="/wiki/On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>)</dd></dl> <p>The number of the values of <i>b</i> for a given <i>n</i> must divide <a href="/wiki/Euler_phi_function" class="mw-redirect" title="Euler phi function"><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varphi }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>φ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \varphi }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/33ee699558d09cf9d653f6351f9fda0b2f4aaa3e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.52ex; height:2.176ex;" alt="{\displaystyle \varphi }"></span></a>(<i>n</i>), or <a href="//oeis.org/A000010" class="extiw" title="oeis:A000010">A000010</a>(<i>n</i>) = 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, 12, 10, 22, 8, 20, 12, 18, 12, 28, 8, 30, 16, 20, 16, 24, 12, 36, 18, 24, 16, 40, 12, 42, 20, 24, 22, 46, 16, 42, 20, ... The <a href="/wiki/Quotient" title="Quotient">quotient</a> can be any natural number, and the quotient = 1 <a href="/wiki/If_and_only_if" title="If and only if">if and only if</a> <i>n</i> is a <a href="/wiki/Prime_number" title="Prime number">prime</a> or a <a href="/wiki/Carmichael_number" title="Carmichael number">Carmichael number</a> (561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, ... <a href="//oeis.org/A002997" class="extiw" title="oeis:A002997">A002997</a>) The quotient = 2 if and only if <i>n</i> is in the sequence: 4, 6, 15, 91, 703, 1891, 2701, 11305, 12403, 13981, 18721, ... <a href="//oeis.org/A191311" class="extiw" title="oeis:A191311">A191311</a>.) </p><p>The least numbers which are pseudoprime to <i>k</i> values of <i>b</i> are (or 0 if no such number exists) </p> <dl><dd>1, 3, 28, 5, 66, 7, 232, 45, 190, 11, 276, 13, 1106, 0, 286, 17, 1854, 19, 3820, 891, 2752, 23, 1128, 595, 2046, 0, 532, 29, 1770, 31, 9952, 425, 1288, 0, 2486, 37, 8474, 0, 742, 41, 3486, 43, 7612, 5589, 2356, 47, 13584, 325, 9850, 0, ... (sequence <span class="nowrap external"><a href="//oeis.org/A064234" class="extiw" title="oeis:A064234">A064234</a></span> in the <a href="/wiki/On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>) (<a href="/wiki/If_and_only_if" title="If and only if">if and only if</a> <i>k</i> is <a href="/wiki/Even_number" class="mw-redirect" title="Even number">even</a> and not <a href="/wiki/Totient" class="mw-redirect" title="Totient">totient</a> of <a href="/wiki/Squarefree_number" class="mw-redirect" title="Squarefree number">squarefree number</a>, then the <i>k</i>th term of this sequence is 0.)</dd></dl> <div class="mw-heading mw-heading2"><h2 id="Weak_pseudoprimes">Weak pseudoprimes</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Fermat_pseudoprime&action=edit&section=8" title="Edit section: Weak pseudoprimes"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A composite number <i>n</i> which satisfies <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b^{n}\equiv b{\pmod {n}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>b</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> <mo>≡</mo> <mi>b</mi> <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 b^{n}\equiv b{\pmod {n}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0ee96e9be7fb8ce02619e5cb4be7a7368a3c592d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.391ex; height:2.843ex;" alt="{\displaystyle b^{n}\equiv b{\pmod {n}}}"></span> is called a <b>weak pseudoprime to base <i>b</i></b>. For any given base <i>b</i>, all Fermat pseudoprimes are weak pseudoprimes, and all weak pseudoprimes coprime to <i>b</i> are Fermat pseudoprimes. However, this definition also permits some pseudoprimes which are <i>not</i> coprime to <i>b</i>.<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> For example, the smallest even weak pseudoprime in base 2 is 161038 (see <span class="nowrap external"><a href="/wiki/On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>: <a href="//oeis.org/A006935" class="extiw" title="oeis:A006935">A006935</a></span>). </p><p>The least weak pseudoprime to bases <i>b</i> = 1, 2, ... are: </p> <dl><dd>4, 341, 6, 4, 4, 6, 6, 4, 4, 6, 10, 4, 4, 14, 6, 4, 4, 6, 6, 4, 4, 6, 22, 4, 4, 9, 6, 4, 4, 6, 6, 4, 4, 6, 9, 4, 4, 38, 6, 4, 4, 6, 6, 4, 4, 6, 46, 4, 4, 10, ... <span class="nowrap external"><a href="/wiki/On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>: <a href="//oeis.org/A000790" class="extiw" title="oeis:A000790">A000790</a></span></dd></dl> <p>Carmichael numbers are weak pseudoprimes to all bases, thus all terms in this list are less than or equal to the smallest Carmichael number, 561. Except for 561 = 3⋅11⋅17, only <a href="/wiki/Semiprime" title="Semiprime">semiprimes</a> can occur in the above sequence. Not all semiprimes less than 561 occur; a semiprime <i>pq</i> (<i>p</i> ≤ <i>q</i>) less than 561 occurs in the above sequences <a href="/wiki/If_and_only_if" title="If and only if">if and only if</a> <i>p</i> − 1 divides <i>q</i> − 1 (see <span class="nowrap external"><a href="/wiki/On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>: <a href="//oeis.org/A108574" class="extiw" title="oeis:A108574">A108574</a></span>). The least Fermat pseudoprime to base <i>b</i> (also not necessary exceeding <i>b</i>) (<span class="nowrap external"><a href="/wiki/On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>: <a href="//oeis.org/A090086" class="extiw" title="oeis:A090086">A090086</a></span>) is <i>usually</i> semiprime, but not always; the first counterexample is <a href="//oeis.org/A090086" class="extiw" title="oeis:A090086">A090086</a>(648) = 385 = 5 × 7 × 11. </p><p>If we require <i>n</i> > <i>b</i>, the least weak pseudoprimes (for <i>b</i> = 1, 2, ...) are: </p> <dl><dd>4, 341, 6, 6, 10, 10, 14, 9, 12, 15, 15, 22, 21, 15, 21, 20, 34, 25, 38, 21, 28, 33, 33, 25, 28, 27, 39, 36, 35, 49, 49, 33, 44, 35, 45, 42, 45, 39, 57, 52, 82, 66, 77, 45, 55, 69, 65, 49, 56, 51, ... <span class="nowrap external"><a href="/wiki/On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>: <a href="//oeis.org/A239293" class="extiw" title="oeis:A239293">A239293</a></span></dd></dl> <div class="mw-heading mw-heading2"><h2 id="Euler–Jacobi_pseudoprimes"><span id="Euler.E2.80.93Jacobi_pseudoprimes"></span>Euler–Jacobi pseudoprimes</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Fermat_pseudoprime&action=edit&section=9" title="Edit section: 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>Another approach is to use more refined notions of pseudoprimality, e.g. <a href="/wiki/Strong_pseudoprime" title="Strong pseudoprime">strong pseudoprimes</a> or <a href="/wiki/Euler%E2%80%93Jacobi_pseudoprime" title="Euler–Jacobi pseudoprime">Euler–Jacobi pseudoprimes</a>, for which there are no analogues of <a href="/wiki/Carmichael_number" title="Carmichael number">Carmichael numbers</a>. This leads to <a href="/wiki/Randomized_algorithm" title="Randomized algorithm">probabilistic algorithms</a> such as the <a href="/wiki/Solovay%E2%80%93Strassen_primality_test" title="Solovay–Strassen primality test">Solovay–Strassen primality test</a>, the <a href="/wiki/Baillie%E2%80%93PSW_primality_test" title="Baillie–PSW primality test">Baillie–PSW primality test</a>, and the <a href="/wiki/Miller%E2%80%93Rabin_primality_test" title="Miller–Rabin primality test">Miller–Rabin primality test</a>, which produce what are known as <a href="/wiki/Industrial-grade_primes" class="mw-redirect" title="Industrial-grade primes">industrial-grade primes</a>. Industrial-grade primes are integers for which primality has not been "certified" (i.e. rigorously proven), but have undergone a test such as the Miller–Rabin test which has nonzero, but arbitrarily low, probability of failure. </p> <div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Fermat_pseudoprime&action=edit&section=10" title="Edit section: Applications"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The rarity of such pseudoprimes has important practical implications. For example, <a href="/wiki/Public-key_cryptography" title="Public-key cryptography">public-key cryptography</a> algorithms such as <a href="/wiki/RSA_(algorithm)" class="mw-redirect" title="RSA (algorithm)">RSA</a> require the ability to quickly find large primes. The usual algorithm to generate prime numbers is to generate random odd numbers and <a href="/wiki/Primality_test" title="Primality test">test</a> them for primality. However, <a href="/wiki/Deterministic_algorithm" title="Deterministic algorithm">deterministic</a> primality tests are slow. If the user is willing to tolerate an arbitrarily small chance that the number found is not a prime number but a pseudoprime, it is possible to use the much faster and simpler <a href="/wiki/Fermat_primality_test" title="Fermat primality test">Fermat primality test</a>. </p> <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=Fermat_pseudoprime&action=edit&section=11" 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-JoyOfFactoring-1"><span class="mw-cite-backlink">^ <a href="#cite_ref-JoyOfFactoring_1-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-JoyOfFactoring_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="CITEREFSamuel_S._Wagstaff_Jr.2013" class="citation book cs1"><a href="/wiki/Samuel_S._Wagstaff,_Jr." class="mw-redirect" title="Samuel S. Wagstaff, Jr.">Samuel S. Wagstaff Jr.</a> (2013). <a rel="nofollow" class="external text" href="https://www.ams.org/bookpages/stml-68"><i>The Joy of Factoring</i></a>. Providence, RI: American Mathematical Society. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-4704-1048-3" title="Special:BookSources/978-1-4704-1048-3"><bdi>978-1-4704-1048-3</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=The+Joy+of+Factoring&rft.place=Providence%2C+RI&rft.pub=American+Mathematical+Society&rft.date=2013&rft.isbn=978-1-4704-1048-3&rft.au=Samuel+S.+Wagstaff+Jr.&rft_id=https%3A%2F%2Fwww.ams.org%2Fbookpages%2Fstml-68&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFermat+pseudoprime" class="Z3988"></span></span> </li> <li id="cite_note-desmedt-10-23-2"><span class="mw-cite-backlink">^ <a href="#cite_ref-desmedt-10-23_2-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-desmedt-10-23_2-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFDesmedt2010" class="citation book cs1">Desmedt, Yvo (2010). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=SbPpg_4ZRGsC&pg=SA10-PA23">"Encryption Schemes"</a>. In <a href="/wiki/Mikhail_Atallah" title="Mikhail Atallah">Atallah, Mikhail J.</a>; Blanton, Marina (eds.). <i>Algorithms and theory of computation handbook: Special topics and techniques</i>. CRC Press. pp. 10–23. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-58488-820-8" title="Special:BookSources/978-1-58488-820-8"><bdi>978-1-58488-820-8</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Encryption+Schemes&rft.btitle=Algorithms+and+theory+of+computation+handbook%3A+Special+topics+and+techniques&rft.pages=10-23&rft.pub=CRC+Press&rft.date=2010&rft.isbn=978-1-58488-820-8&rft.aulast=Desmedt&rft.aufirst=Yvo&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DSbPpg_4ZRGsC%26pg%3DSA10-PA23&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFermat+pseudoprime" class="Z3988"></span></span> </li> <li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFPaulo_Ribenboim1996" class="citation book cs1"><a href="/wiki/Paulo_Ribenboim" title="Paulo Ribenboim">Paulo Ribenboim</a> (1996). <i>The New Book of Prime Number Records</i>. New York: <a href="/wiki/Springer-Verlag" class="mw-redirect" title="Springer-Verlag">Springer-Verlag</a>. p. 108. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-387-94457-5" title="Special:BookSources/0-387-94457-5"><bdi>0-387-94457-5</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=The+New+Book+of+Prime+Number+Records&rft.place=New+York&rft.pages=108&rft.pub=Springer-Verlag&rft.date=1996&rft.isbn=0-387-94457-5&rft.au=Paulo+Ribenboim&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFermat+pseudoprime" class="Z3988"></span></span> </li> <li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFHamahataKokubun2007" class="citation journal cs1">Hamahata, Yoshinori; Kokubun, Y. (2007). <a rel="nofollow" class="external text" href="https://cs.uwaterloo.ca/journals/JIS/VOL10/Hamahata2/hamahata44.pdf">"Cipolla Pseudoprimes"</a> <span class="cs1-format">(PDF)</span>. <i>Journal of Integer Sequences</i>. <b>10</b> (8).</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Integer+Sequences&rft.atitle=Cipolla+Pseudoprimes&rft.volume=10&rft.issue=8&rft.date=2007&rft.aulast=Hamahata&rft.aufirst=Yoshinori&rft.au=Kokubun%2C+Y.&rft_id=https%3A%2F%2Fcs.uwaterloo.ca%2Fjournals%2FJIS%2FVOL10%2FHamahata2%2Fhamahata44.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFermat+pseudoprime" class="Z3988"></span></span> </li> <li id="cite_note-PSW-5"><span class="mw-cite-backlink">^ <a href="#cite_ref-PSW_5-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-PSW_5-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFPomeranceSelfridgeWagstaff1980" class="citation journal cs1"><a href="/wiki/Carl_Pomerance" title="Carl Pomerance">Pomerance, Carl</a>; <a href="/wiki/John_L._Selfridge" class="mw-redirect" title="John L. Selfridge">Selfridge, John L.</a>; <a href="/wiki/Samuel_S._Wagstaff_Jr." title="Samuel S. Wagstaff Jr.">Wagstaff, Samuel S. Jr.</a> (July 1980). <a rel="nofollow" class="external text" href="http://www.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): 1003–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 rel="nofollow" class="external text" href="https://web.archive.org/web/20050304202721/http://math.dartmouth.edu/~carlp/PDF/paper25.pdf">Archived</a> <span class="cs1-format">(PDF)</span> from the original on 2005-03-04.</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=1003-1026&rft.date=1980-07&rft_id=info%3Adoi%2F10.1090%2FS0025-5718-1980-0572872-7&rft.aulast=Pomerance&rft.aufirst=Carl&rft.au=Selfridge%2C+John+L.&rft.au=Wagstaff%2C+Samuel+S.+Jr.&rft_id=http%3A%2F%2Fwww.math.dartmouth.edu%2F~carlp%2FPDF%2Fpaper25.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFermat+pseudoprime" class="Z3988"></span></span> </li> <li id="cite_note-Alford1994-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-Alford1994_6-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFAlfordGranvillePomerance1994" class="citation journal cs1"><a href="/wiki/W._R._(Red)_Alford" class="mw-redirect" title="W. R. (Red) Alford">Alford, W. R.</a>; <a href="/wiki/Andrew_Granville" title="Andrew Granville">Granville, Andrew</a>; <a href="/wiki/Carl_Pomerance" title="Carl Pomerance">Pomerance, Carl</a> (1994). <a rel="nofollow" class="external text" href="http://www.math.dartmouth.edu/~carlp/PDF/paper95.pdf">"There are Infinitely Many Carmichael Numbers"</a> <span class="cs1-format">(PDF)</span>. <i><a href="/wiki/Annals_of_Mathematics" title="Annals of Mathematics">Annals of Mathematics</a></i>. <b>140</b> (3): 703–722. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F2118576">10.2307/2118576</a>. <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/2118576">2118576</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20050304203448/http://math.dartmouth.edu/~carlp/PDF/paper95.pdf">Archived</a> <span class="cs1-format">(PDF)</span> from the original on 2005-03-04.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Annals+of+Mathematics&rft.atitle=There+are+Infinitely+Many+Carmichael+Numbers&rft.volume=140&rft.issue=3&rft.pages=703-722&rft.date=1994&rft_id=info%3Adoi%2F10.2307%2F2118576&rft_id=https%3A%2F%2Fwww.jstor.org%2Fstable%2F2118576%23id-name%3DJSTOR&rft.aulast=Alford&rft.aufirst=W.+R.&rft.au=Granville%2C+Andrew&rft.au=Pomerance%2C+Carl&rft_id=http%3A%2F%2Fwww.math.dartmouth.edu%2F~carlp%2FPDF%2Fpaper95.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFermat+pseudoprime" class="Z3988"></span></span> </li> <li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFKimPomerance1989" class="citation journal cs1">Kim, Su Hee; Pomerance, Carl (1989). <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2008733">"The Probability that a Random Probable Prime is Composite"</a>. <i>Mathematics of Computation</i>. <b>53</b> (188): 721–741. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F2008733">10.2307/2008733</a>. <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/2008733">2008733</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+Probability+that+a+Random+Probable+Prime+is+Composite&rft.volume=53&rft.issue=188&rft.pages=721-741&rft.date=1989&rft_id=info%3Adoi%2F10.2307%2F2008733&rft_id=https%3A%2F%2Fwww.jstor.org%2Fstable%2F2008733%23id-name%3DJSTOR&rft.aulast=Kim&rft.aufirst=Su+Hee&rft.au=Pomerance%2C+Carl&rft_id=https%3A%2F%2Fwww.jstor.org%2Fstable%2F2008733&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFermat+pseudoprime" class="Z3988"></span></span> </li> <li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFSierpinski1988" class="citation cs2">Sierpinski, W. (1988-02-15), "Chapter V.7", in Ed. A. Schinzel (ed.), <i>Elementary Theory of Numbers</i>, North-Holland Mathematical Library (2 Sub ed.), Amsterdam: North Holland, p. 232, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/9780444866622" title="Special:BookSources/9780444866622"><bdi>9780444866622</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Chapter+V.7&rft.btitle=Elementary+Theory+of+Numbers&rft.place=Amsterdam&rft.series=North-Holland+Mathematical+Library&rft.pages=232&rft.edition=2+Sub&rft.pub=North+Holland&rft.date=1988-02-15&rft.isbn=9780444866622&rft.aulast=Sierpinski&rft.aufirst=W.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFermat+pseudoprime" class="Z3988"></span></span> </li> <li id="cite_note-lpsp-9"><span class="mw-cite-backlink">^ <a href="#cite_ref-lpsp_9-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-lpsp_9-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFRobert_BaillieSamuel_S._Wagstaff_Jr.1980" class="citation journal cs1">Robert Baillie; <a href="/wiki/Samuel_S._Wagstaff_Jr." title="Samuel S. Wagstaff Jr.">Samuel S. Wagstaff Jr.</a> (October 1980). <a rel="nofollow" class="external text" href="http://mpqs.free.fr/LucasPseudoprimes.pdf">"Lucas Pseudoprimes"</a> <span class="cs1-format">(PDF)</span>. <i>Mathematics of Computation</i>. <b>35</b> (152): 1391–1417. <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-0583518-6">10.1090/S0025-5718-1980-0583518-6</a></span>. <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0583518">0583518</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20060906205655/http://mpqs.free.fr/LucasPseudoprimes.pdf">Archived</a> <span class="cs1-format">(PDF)</span> from the original on 2006-09-06.</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=Lucas+Pseudoprimes&rft.volume=35&rft.issue=152&rft.pages=1391-1417&rft.date=1980-10&rft_id=info%3Adoi%2F10.1090%2FS0025-5718-1980-0583518-6&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D583518%23id-name%3DMR&rft.au=Robert+Baillie&rft.au=Samuel+S.+Wagstaff+Jr.&rft_id=http%3A%2F%2Fmpqs.free.fr%2FLucasPseudoprimes.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFermat+pseudoprime" class="Z3988"></span></span> </li> <li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFMichon2003" class="citation web cs1">Michon, Gérard P. (19 November 2003). <a rel="nofollow" class="external text" href="http://www.numericana.com/answer/pseudo.htm#weak">"Pseudo-primes, Weak Pseudoprimes, Strong Pseudoprimes, Primality"</a>. <i>Numericana</i><span class="reference-accessdate">. Retrieved <span class="nowrap">21 April</span> 2018</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=Numericana&rft.atitle=Pseudo-primes%2C+Weak+Pseudoprimes%2C+Strong+Pseudoprimes%2C+Primality&rft.date=2003-11-19&rft.aulast=Michon&rft.aufirst=G%C3%A9rard+P.&rft_id=http%3A%2F%2Fwww.numericana.com%2Fanswer%2Fpseudo.htm%23weak&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFermat+pseudoprime" class="Z3988"></span></span> </li> </ol></div></div> <div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Fermat_pseudoprime&action=edit&section=12" title="Edit section: External links"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li>W. F. Galway and Jan Feitsma, <a rel="nofollow" class="external text" href="http://www.cecm.sfu.ca/Pseudoprimes/">Tables of pseudoprimes to base 2 and related data</a> (comprehensive list of all pseudoprimes to base 2 below 2<sup>64</sup>, including factorization, strong pseudoprimes, and Carmichael numbers)</li> <li><a rel="nofollow" class="external text" href="http://www.numericana.com/answer/pseudo.htm">A research for pseudoprime</a></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_numbers" 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_numbers" 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_numbers" 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_±_1" 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_numbers" 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_numbers" 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_numbers" 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_sums" 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_numbers" 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_numbers" 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="Primes" 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="Pseudoprimes" 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 href="/wiki/Euler_pseudoprime" title="Euler pseudoprime">Euler pseudoprime</a></li> <li><a href="/wiki/Euler%E2%80%93Jacobi_pseudoprime" title="Euler–Jacobi pseudoprime">Euler–Jacobi pseudoprime</a></li> <li><a class="mw-selflink selflink">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_dynamics" 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_numbers" 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_numbers" 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_numbers" 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_sieve" 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_related" 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_related" 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_related" 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 class="navbox-styles"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236075235"></div><div role="navigation" class="navbox" aria-labelledby="Pierre_de_Fermat" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse 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"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1239400231"><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Pierre_de_Fermat" title="Template:Pierre de Fermat"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/w/index.php?title=Template_talk:Pierre_de_Fermat&action=edit&redlink=1" class="new" title="Template talk:Pierre de Fermat (page does not exist)"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Pierre_de_Fermat" title="Special:EditPage/Template:Pierre de Fermat"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Pierre_de_Fermat" style="font-size:114%;margin:0 4em"><a href="/wiki/Pierre_de_Fermat" title="Pierre de Fermat">Pierre de Fermat</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Work</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/Fermat%27s_Last_Theorem" title="Fermat's Last Theorem">Fermat's Last Theorem</a></li> <li><a href="/wiki/Fermat_number" title="Fermat number">Fermat number</a></li> <li><a href="/wiki/Fermat%27s_principle" title="Fermat's principle">Fermat's principle</a></li> <li><a href="/wiki/Fermat%27s_little_theorem" title="Fermat's little theorem">Fermat's little theorem</a></li> <li><a href="/wiki/Fermat_polygonal_number_theorem" title="Fermat polygonal number theorem">Fermat polygonal number theorem</a></li> <li><a class="mw-selflink selflink">Fermat pseudoprime</a></li> <li><a href="/wiki/Fermat_point" title="Fermat point">Fermat point</a></li> <li><a href="/wiki/Fermat%27s_theorem_(stationary_points)" title="Fermat's theorem (stationary points)">Fermat's theorem (stationary points)</a></li> <li><a href="/wiki/Fermat%27s_theorem_on_sums_of_two_squares" title="Fermat's theorem on sums of two squares">Fermat's theorem on sums of two squares</a></li> <li><a href="/wiki/Fermat%27s_spiral" title="Fermat's spiral">Fermat's spiral</a></li> <li><a href="/wiki/Fermat%27s_right_triangle_theorem" title="Fermat's right triangle theorem">Fermat's right triangle theorem</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">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/List_of_things_named_after_Pierre_de_Fermat" title="List of things named after Pierre de Fermat">List of things named after Pierre de Fermat</a></li> <li><a href="/wiki/Wiles%27s_proof_of_Fermat%27s_Last_Theorem" title="Wiles's proof of Fermat's Last Theorem">Wiles's proof of Fermat's Last Theorem</a></li> <li><a href="/wiki/Fermat%27s_Last_Theorem_in_fiction" title="Fermat's Last Theorem in fiction">Fermat's Last Theorem in fiction</a></li> <li><a href="/wiki/Fermat_Prize" title="Fermat Prize">Fermat Prize</a></li> <li><i><a href="/wiki/Fermat%27s_Last_Tango" title="Fermat's Last Tango">Fermat's Last Tango</a></i> (2000 musical)</li> <li><i><a href="/wiki/Fermat%27s_Last_Theorem_(book)" title="Fermat's Last Theorem (book)">Fermat's Last Theorem</a></i> (popular science book)</li></ul> </div></td></tr></tbody></table></div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=Fermat_pseudoprime&oldid=1259406491">https://en.wikipedia.org/w/index.php?title=Fermat_pseudoprime&oldid=1259406491</a>"</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Help:Category" title="Help:Category">Categories</a>: <ul><li><a href="/wiki/Category:Pseudoprimes" title="Category:Pseudoprimes">Pseudoprimes</a></li><li><a href="/wiki/Category:Asymmetric-key_algorithms" title="Category:Asymmetric-key algorithms">Asymmetric-key algorithms</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_is_different_from_Wikidata" title="Category:Short description is different from Wikidata">Short description is different from Wikidata</a></li><li><a href="/wiki/Category:Articles_containing_German-language_text" title="Category:Articles containing German-language text">Articles containing German-language text</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 25 November 2024, at 00:03<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=Fermat_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"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" loading="lazy"></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/w/resources/assets/poweredby_mediawiki.svg" alt="Powered by MediaWiki" width="88" height="31" loading="lazy"></a></li> </ul> </footer> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-6b7f745dd4-dm7th","wgBackendResponseTime":176,"wgPageParseReport":{"limitreport":{"cputime":"0.729","walltime":"0.930","ppvisitednodes":{"value":2992,"limit":1000000},"postexpandincludesize":{"value":138571,"limit":2097152},"templateargumentsize":{"value":2058,"limit":2097152},"expansiondepth":{"value":16,"limit":100},"expensivefunctioncount":{"value":2,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":56366,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 671.878 1 -total"," 30.08% 202.117 1 Template:Reflist"," 21.66% 145.512 1 Template:Lang"," 20.11% 135.082 1 Template:Classes_of_natural_numbers"," 19.72% 132.503 1 Template:Navbox_with_collapsible_groups"," 18.32% 123.121 3 Template:Cite_book"," 11.72% 78.713 1 Template:Short_description"," 7.25% 48.685 2 Template:Pagetype"," 6.33% 42.503 4 Template:Rp"," 5.47% 36.724 1 Template:Main"]},"scribunto":{"limitreport-timeusage":{"value":"0.430","limit":"10.000"},"limitreport-memusage":{"value":15850817,"limit":52428800}},"cachereport":{"origin":"mw-api-int.codfw.main-849f99967d-dfhgl","timestamp":"20241125000326","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Fermat pseudoprime","url":"https:\/\/en.wikipedia.org\/wiki\/Fermat_pseudoprime","sameAs":"http:\/\/www.wikidata.org\/entity\/Q1406394","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q1406394","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":"2002-03-24T20:09:41Z","dateModified":"2024-11-25T00:03:17Z","headline":"pseudoprime that satisfies Fermat\u2019s little theorem"}</script> </body> </html>