Editing Euler pseudoprime

{{Short description|Odd composite number which passes the given congruence}}
In [[mathematics]], an [[Odd number|odd]] [[composite number|composite]] [[integer]] ''n'' is called an '''Euler pseudoprime''' to base ''a'', if ''a'' and ''n'' are [[coprime]], and 

: <math>a^{(n-1)/2} \equiv \pm  1\pmod{n}</math>

(where ''mod'' refers to the [[modular arithmetic|modulo]] operation).

The motivation for this definition is the fact that all [[prime number]]s ''p'' satisfy the above equation which can be deduced from [[Fermat's little theorem]]. Fermat's theorem  asserts that if ''p'' is prime, and coprime to ''a'', then ''a''<sup>''p''&minus;1</sup> ≡ 1 (mod ''p''). Suppose that ''p''>2 is prime, then ''p'' can be expressed as 2''q''&nbsp;+&nbsp;1 where ''q'' is an integer. Thus, ''a''<sup>(2''q''+1)&nbsp;&minus;&nbsp;1</sup> ≡ 1 (mod&nbsp;''p''), which means that ''a''<sup>2''q''</sup>&nbsp;&minus;&nbsp;1 ≡ 0 (mod ''p''). This can be factored as (''a''<sup>''q''</sup>&nbsp;&minus;&nbsp;1)(''a''<sup>''q''</sup> + 1) ≡ 0 (mod ''p''), which is equivalent to ''a''<sup>(''p''&minus;1)/2</sup> ≡ ±1 (mod&nbsp;''p'').

The equation can be tested rather quickly, which can be used for probabilistic [[prime testing|primality testing]]. These tests are twice as strong as tests based on Fermat's little theorem.

Every Euler [[pseudoprime]] is also a [[Fermat pseudoprime]]. It is not possible to produce a definite test of primality based on whether a [[number]] is an Euler pseudoprime because there exist ''absolute Euler pseudoprimes'', numbers which are Euler pseudoprimes to every base relatively prime to themselves. The absolute Euler pseudoprimes are a [[subset]] of the absolute Fermat pseudoprimes, or [[Carmichael number]]s, and the smallest absolute Euler pseudoprime is [[1729 (number)|1729]] = 7&times;13&times;19 {{OEIS|id=A033181}}.

==Relation to Euler–Jacobi pseudoprimes==
{{main|Euler–Jacobi pseudoprime}}
A slightly stronger test uses the [[Jacobi symbol]] to predict which of the two results will be found.  The resultant [[Euler-Jacobi pseudoprime|Euler-Jacobi probable prime]] test verifies that
: <math> a^{(n-1)/2} \equiv \left(\frac{a}{n}\right) \neq 0 \pmod n.</math>
As with the basic Euler test, ''a'' and ''n'' are required to be comprime, but that test is included in the computation of the Jacobi symbol (''a''/''n''), whose value equals 0 if the values are ''not'' coprime.  This slightly stronger test is called simply an Euler probable prime test by some authors.  See, for example, page 115 of the book by Koblitz listed below, page 90 of the book by Riesel, or page 1003 of.<ref name="PSW">{{cite journal |author1 = Carl Pomerance |author-link1 = Carl Pomerance |author2 = John L. Selfridge |author-link2 = John L. Selfridge |author3 = Samuel S. Wagstaff, Jr. |author-link3 = Samuel S. Wagstaff, Jr. |title=The pseudoprimes to 25·10<sup>9</sup> |journal=Mathematics of Computation |date=July 1980 |volume=35 |issue=151 |pages=1003–1026 |url=//math.dartmouth.edu/~carlp/PDF/paper25.pdf |jstor=2006210 |doi=10.1090/S0025-5718-1980-0572872-7 |doi-access =free }}</ref>

As an example of this test's increased strength, 341 is an Euler pseudoprime to the base 2, but not an Euler-Jacobi pseudoprime.  Even more significantly, there are no absolute Euler–Jacobi pseudoprimes.{{r|PSW|p=1004}}

A [[Strong pseudoprime|strong probable prime]] test is even stronger than the Euler-Jacobi test but takes the same computational effort. Because of this, prime-testing software is usually based on the strong test.

==Implementation in [[Lua (programming language)|Lua]]==

 '''function''' EulerTest(k)
   a = 2
   '''if''' k == 1 '''then return false'''
   '''elseif''' k == 2 '''then return true'''
   '''else'''
     m = [[Modular exponentiation#Implementation in Lua|modPow(a,(k-1)/2,k)]]
     '''if''' (m == 1) or (m == k-1) '''then'''
       '''return true'''
     '''else'''
       '''return false'''
     '''end'''
   '''end'''
 '''end'''

==Examples==

{|class="wikitable"
!''n''
!Euler pseudoprimes to base ''n''
|-
|1
|All odd composite numbers: 9, 15, 21, 25, 27, 33, 35, 39, 45, 49, 51, 55, 57, 63, 65, 69, 75, 77, 81, 85, 87, 91, 93, 95, 99, ...
|-
|2
|341, 561, 1105, 1729, 1905, 2047, 2465, 3277, 4033, 4681, 5461, 6601, 8321, 8481, ...
|-
|3
|121, 703, 1541, 1729, 1891, 2465, 2821, 3281, 4961, 7381, 8401, 8911, ...
|-
|4
|341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911, ...
|-
|5
|217, 781, 1541, 1729, 5461, 5611, 6601, 7449, 7813, ...
|-
|6
|185, 217, 301, 481, 1111, 1261, 1333, 1729, 2465, 2701, 3421, 3565, 3589, 3913, 5713, 6533, 8365, ...
|-
|7
|25, 325, 703, 817, 1825, 2101, 2353, 2465, 3277, 4525, 6697, 8321, ...
|-
|8
|9, 21, 65, 105, 133, 273, 341, 481, 511, 561, 585, 1001, 1105, 1281, 1417, 1541, 1661, 1729, 1905, 2047, 2465, 2501, 3201, 3277, 3641, 4033, 4097, 4641, 4681, 4921, 5461, 6305, 6533, 6601, 7161, 8321, 8481, 9265, 9709, ...
|-
|9
|91, 121, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, 4961, 5551, 6601, 7381, 8401, 8911, ...
|-
|10
|9, 33, 91, 481, 657, 1233, 1729, 2821, 2981, 4187, 5461, 6533, 6541, 6601, 7777, 8149, 8401, ...
|-
|11
|133, 305, 481, 645, 793, 1729, 2047, 2257, 2465, 4577, 4921, 5041, 5185, 8113, ...
|-
|12
|65, 91, 133, 145, 247, 377, 385, 1649, 1729, 2041, 2233, 2465, 2821, 3553, 6305, 8911, 9073, ...
|-
|13
|21, 85, 105, 561, 1099, 1785, 2465, 5149, 5185, 7107, 8841, 8911, 9577, 9637, ...
|-
|14
|15, 65, 481, 781, 793, 841, 985, 1541, 2257, 2465, 2561, 2743, 3277, 5185, 5713, 6533, 6541, 7171, 7449, 7585, 8321, 9073, ...
|-
|15
|341, 1477, 1541, 1687, 1729, 1921, 3277, 6541, 9073, ...
|-
|16
|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, ...
|-
|17
|9, 91, 145, 781, 1111, 1305, 1729, 2149, 2821, 4033, 4187, 5365, 5833, 6697, 7171, ...
|-
|18
|25, 49, 65, 133, 325, 343, 425, 1105, 1225, 1369, 1387, 1729, 1921, 2149, 2465, 2977, 4577, 5725, 5833, 5941, 6305, 6517, 6601, 7345, ...
|-
|19
|9, 45, 49, 169, 343, 561, 889, 905, 1105, 1661, 1849, 2353, 2465, 2701, 3201, 4033, 4681, 5461, 5713, 6541, 6697, 7957, 8145, 8281, 8401, 9997, ...
|-
|20
|21, 57, 133, 671, 889, 1281, 1653, 1729, 1891, 2059, 2413, 2761, 3201, 5461, 5473, 5713, 5833, 6601, 6817, 7999, ...
|-
|21
|65, 221, 703, 793, 1045, 1105, 2465, 3781, 5185, 5473, 6541, 7363, 8965, 9061, ...
|-
|22
|21, 69, 91, 105, 161, 169, 345, 485, 1183, 1247, 1541, 1729, 2041, 2047, 2413, 2465, 2821, 3241, 3801, 5551, 7665, 9453, ...
|-
|23
|33, 169, 265, 341, 385, 481, 553, 1065, 1271, 1729, 2321, 2465, 2701, 2821, 3097, 4033, 4081, 4345, 4371, 4681, 5149, 6533, 6541, 7189, 7957, 8321, 8651, 8745, 8911, 9805, ...
|-
|24
|25, 175, 553, 805, 949, 1541, 1729, 1825, 1975, 2413, 2465, 2701, 3781, 4537, 6931, 7501, 9085, 9361, ...
|-
|25
|217, 561, 781, 1541, 1729, 1891, 2821, 4123, 5461, 5611, 5731, 6601, 7449, 7813, 8029, 8911, 9881, ...
|-
|26
|9, 25, 27, 45, 133, 217, 225, 475, 561, 589, 703, 925, 1065, 2465, 3325, 3385, 3565, 3825, 4741, 4921, 5041, 5425, 6697, 8029, 9073, ...
|-
|27
|65, 121, 133, 259, 341, 365, 481, 703, 1001, 1541, 1649, 1729, 1891, 2465, 2821, 2981, 2993, 3281, 4033, 4745, 4921, 4961, 5461, 6305, 6533, 7381, 7585, 8321, 8401, 8911, 9809, 9841, 9881, ...
|-
|28
|9, 27, 145, 261, 361, 529, 785, 1305, 1431, 2041, 2413, 2465, 3201, 3277, 4553, 4699, 5149, 7065, 8321, 8401, 9841, ...
|-
|29
|15, 21, 91, 105, 341, 469, 481, 793, 871, 1729, 1897, 2105, 2257, 2821, 4371, 4411, 5149, 5185, 5473, 5565, 6097, 7161, 8321, 8401, 8421, 8841, ...
|-
|30
|49, 133, 217, 341, 403, 469, 589, 637, 871, 901, 931, 1273, 1537, 1729, 2059, 2077, 2821, 3097, 3277, 4081, 4097, 5729, 6031, 6061, 6097, 6409, 6817, 7657, 8023, 8029, 8401, 9881, ...
|}

==Least Euler pseudoprime to base ''n''==

{|class="wikitable"
|''n''
|Least EPSP
|''n''
|Least EPSP
|''n''
|Least EPSP
|''n''
|Least EPSP
|-
|1
|9
|33
|545
|65
|33
|97
|21
|-
|2
|341
|34
|21
|66
|65
|98
|9
|-
|3
|121
|35
|9
|67
|33
|99
|25
|-
|4
|341
|36
|35
|68
|25
|100
|9
|-
|5
|217
|37
|9
|69
|35
|101
|25
|-
|6
|185
|38
|39
|70
|69
|102
|133
|-
|7
|25
|39
|133
|71
|9
|103
|51
|-
|8
|9
|40
|39
|72
|85
|104
|15
|-
|9
|91
|41
|21
|73
|9
|105
|451
|-
|10
|9
|42
|451
|74
|15
|106
|15
|-
|11
|133
|43
|21
|75
|91
|107
|9
|-
|12
|65
|44
|9
|76
|15
|108
|91
|-
|13
|21
|45
|133
|77
|39
|109
|9
|-
|14
|15
|46
|9
|78
|77
|110
|111
|-
|15
|341
|47
|65
|79
|39
|111
|55
|-
|16
|15
|48
|49
|80
|9
|112
|65
|-
|17
|9
|49
|25
|81
|91
|113
|21
|-
|18
|25
|50
|21
|82
|9
|114
|115
|-
|19
|9
|51
|25
|83
|21
|115
|57
|-
|20
|21
|52
|51
|84
|85
|116
|9
|-
|21
|65
|53
|9
|85
|21
|117
|49
|-
|22
|21
|54
|55
|86
|65
|118
|9
|-
|23
|33
|55
|9
|87
|133
|119
|15
|-
|24
|25
|56
|33
|88
|87
|120
|77
|-
|25
|217
|57
|25
|89
|9
|121
|15
|-
|26
|9
|58
|57
|90
|91
|122
|33
|-
|27
|65
|59
|15
|91
|9
|123
|85
|-
|28
|9
|60
|341
|92
|21
|124
|25
|-
|29
|15
|61
|15
|93
|25
|125
|9
|-
|30
|49
|62
|9
|94
|57
|126
|25
|-
|31
|15
|63
|341
|95
|141
|127
|9
|-
|32
|25
|64
|9
|96
|65
|128
|49
|}

==See also==
* [[Probable prime]]

==References==
{{reflist}}
*M. Koblitz, "A Course in Number Theory and Cryptography", Springer-Verlag, 1987.
*H. Riesel, "Prime numbers and computer methods of factorisation", Birkhäuser, Boston, Mass., 1985.

{{Classes of natural numbers}}
{{DEFAULTSORT:Euler Pseudoprime}}
[[Category:Pseudoprimes]]