# Euler's theorem

572 VIEWS

Everipedia is now IQ.wiki - Join the IQ Brainlist and our Discord for early access to editing on the new platform and to participate in the beta testing.

# Euler's theorem

Euler's theorem

In number theory, **Euler's theorem** (also known as the **Fermat–Euler theorem** or **Euler's totient theorem**) states that if *n* and *a* are coprime positive integers, then

`whereisEuler's totient function. (The notation is explained in the articlemodular arithmetic.) In 1736,Leonhard Eulerpublished his proof ofFermat's little theorem,`

^{[1]}whichFermathad presented without proof. Subsequently, Euler presented other proofs of the theorem, culminating with "Euler's theorem" in his paper of 1763, in which he attempted to find the smallest exponent for which Fermat's little theorem was always true.^{[2]}`The converse of Euler's theorem is also true: if the above congruence is true, thenandmust be coprime.`

The theorem is a generalization of Fermat's little theorem, and is further generalized by Carmichael's theorem.

`The theorem may be used to easily reduce large powers modulo. For example, consider finding the ones place decimal digit of, i.e.. The integers 7 and 10 are coprime, and. So Euler's theorem yields, and we get.`

`In general, when reducing a power ofmodulo(whereandare coprime), one needs to work moduloin the exponent of:`

- if, then.

`Euler's theorem is sometimes cited as forming the basis of theRSA encryption system, however it is insufficient (and unnecessary) to use Euler's theorem to certify the validity of RSA encryption. In RSA, the net result of firstencryptingaplaintextmessage, then laterdecryptingit, amounts to exponentiating a large input number by, for some positive integer. In the case that the original number is relatively prime to, Euler's theorem then guarantees that the decrypted output number is equal to the original input number, giving back the plaintext. However, becauseis a product of two distinct primes,and, when the number encrypted is a multiple ofor, Euler's theorem does not apply and it is necessary to use the uniqueness provision of theChinese Remainder Theorem. The Chinese Remainder Theorem also suffices in the case where the number is relatively prime to, and so Euler's theorem is neither sufficient nor necessary.`

Proofs

- Euler's theorem can be proven using concepts from the theory of groups:
^{[3]}The residue classes modulo n that are coprime to n form a group under multiplication (see the article Multiplicative group of integers modulo n for details). The order of that group is*φ*(*n*) where φ denotes Euler's totient function. Lagrange's theorem states that the order of any subgroup of a finite group divides the order of the entire group, in this case*φ*(*n*). If a is any number coprime to n then a is in one of these residue classes, and its powers*a*,*a*2, ... ,*a**k*are a subgroup modulo n, with*a**k*≡ 1 (mod*n*). Lagrange's theorem says k must divide*φ*(*n*), i.e. there is an integer M such that*kM*=*φ*(*n*). But then,

- There is also a direct proof:
^{[4]}^{[5]}Let*R*= {*x*1,*x*2, ... ,*x**φ*(*n*)} be a reduced residue system (mod*n*) and let a be any integer coprime to n. The proof hinges on the fundamental fact that multiplication by a permutes the xi: in other words if*axj*≡*axk*(mod*n*) then*j*=*k*. (This law of cancellation is proved in the article multiplicative group of integers modulo n.^{[6]}) That is, the sets R and*aR*= {*ax*1,*ax*2, ... ,*ax**φ*(*n*)}, considered as sets of congruence classes (mod*n*), are identical (as sets—they may be listed in different orders), so the product of all the numbers in R is congruent (mod*n*) to the product of all the numbers in aR:

- and using the cancellation law to cancel eachx

_{i}gives Euler's theorem:

Euler quotient

The **Euler quotient** of an integer *a* with respect to *n* is defined as:

The special case of an Euler quotient when *n* is prime is called a Fermat quotient.

`Any odd number`

*n*that dividesis called aWieferich number. This is equivalent to saying that 2*φ*(*n*)≡ 1 (mod*n*2). As a generalization, any number*n*that is coprime to a positive integer*a*, and such that*n*divides, is called a (generalized) Wieferich number to base*a*. This is equivalent to saying that a*φ*(*n*)≡ 1 (mod*n*2).a | numbers n coprime to a that divide(searched up to 1048576) | OEIS sequence |

1 | 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, ... (all natural numbers) | A000027 |

2 | 1, 1093, 3279, 3511, 7651, 10533, 14209, 17555, 22953, 31599, 42627, 45643, 52665, 68859, 94797, 99463, 127881, 136929, 157995, 228215, 298389, 410787, 473985, 684645, 895167, 1232361, 2053935, 2685501, 3697083, 3837523, 6161805, 11512569, ... | A077816 |

3 | 1, 11, 22, 44, 55, 110, 220, 440, 880, 1006003, 2012006, 4024012, 11066033, 22132066, 44264132, 55330165, 88528264, 110660330, 221320660, 442641320, 885282640, 1770565280, 56224501667, 112449003334, ... | A242958 |

4 | 1, 1093, 3279, 3511, 7651, 10533, 14209, 17555, 22953, 31599, 42627, 45643, 52665, 68859, 94797, 99463, 127881, 136929, 157995, 228215, 298389, 410787, 473985, 684645, 895167, ... | |

5 | 1, 2, 20771, 40487, 41542, 80974, 83084, 161948, 643901, 1255097, 1287802, 1391657, 1931703, 2510194, 2575604, 2783314, 3765291, 3863406, 4174971, 5020388, 5151208, 5566628, 7530582, 7726812, 8349942, 10040776, 11133256, 15061164, 15308227, 15453624, 16699884, ... | A242959 |

6 | 1, 66161, 330805, 534851, 2674255, 3152573, 10162169, 13371275, 50810845, 54715147, 129255493, 148170931, 254054225, 273575735, 301121113, 383006029, 646277465, ... | A241978 |

7 | 1, 4, 5, 10, 20, 40, 80, 491531, 983062, 1966124, 2457655, 3932248, 4915310, 6389903, 9339089, 9830620, 12288275, 12779806, 18678178, 19169709, 19661240, 24576550, 25559612, ... | A242960 |

8 | 1, 3, 1093, 3279, 3511, 7651, 9837, 10533, 14209, 17555, 22953, 31599, 42627, 45643, 52665, 68859, 94797, 99463, 127881, 136929, 157995, 206577, 228215, 284391, 298389, 383643, 410787, 473985, 684645, 895167, ... | |

9 | 1, 2, 4, 11, 22, 44, 55, 88, 110, 220, 440, 880, 1760, 1006003, ... | |

10 | 1, 3, 487, 1461, 4383, 13149, 39447, 118341, 355023, 56598313, 169794939, 509384817, ... | A241977 |

11 | 1, 71, 142, 284, 355, 497, 710, 994, 1420, 1491, 1988, 2485, 2840, 2982, 3976, 4970, 5680, 5964, 7455, 9940, 11928, 14910, 19880, 23856, 29820, 39760, 59640, 79520, 119280, 238560, 477120, ... | A253016 |

12 | 1, 2693, 123653, 1812389, 2349407, 12686723, 201183431, 332997529, ... | A245529 |

13 | 1, 2, 863, 1726, 3452, 371953, 743906, 1487812, 1747591, 1859765, 2975624, 3495182, 3719530, 5242773, 6990364, 7439060, 8737955, 10485546, 14878120, 15993979, 17475910, 20971092, 26213865, 29756240, 31987958, 34951820, 41942184, 47981937, 52427730, 59512480, ... | A257660 |

14 | 1, 29, 353, 3883, 10237, 19415, 112607, 563035, ... | |

15 | 1, 4, 8, 29131, 58262, 116524, 233048, 466096, ... | |

16 | 1, 1093, 3279, 3511, 7651, 10533, 14209, 17555, 22953, 31599, 42627, 45643, 52665, 68859, 94797, 99463, 127881, 136929, 157995, 228215, 298389, 410787, 473985, 684645, 895167, ... | |

17 | 1, 2, 3, 4, 6, 8, 12, 24, 48, 46021, 48947, 92042, 97894, 138063, 146841, 184084, 195788, 230105, 276126, 293682, 368168, 391576, 414189, 460210, 552252, 587364, 598273, 690315, 736336, 783152, 828378, 920420, ... | |

18 | 1, 5, 7, 35, 37, 49, 185, 245, 259, 331, 1295, 1655, 1813, 2317, 3641, 8275, 9065, 11585, 12247, 16219, 18205, 25487, 33923, 57925, 61235, 81095, 85729, 91025, 127435, 134717, 169615, 178409, 237461, 306175, 405475, 428645, 455125, 600103, 637175, 673585, 892045, 943019, ... | |

19 | 1, 3, 6, 7, 12, 13, 14, 21, 26, 28, 39, 42, 43, 49, 52, 63, 78, 84, 86, 91, 98, 104, 117, 126, 129, 137, 147, 156, 168, 172, 182, 196, 234, 252, 258, 273, 274, 294, 301, 312, 364, 387, 411, 441, 468, 504, 516, 546, 548, 559, 588, 602, 624, 637, 728, 774, 819, 822, 882, 903, 936, 959, 1032, 1092, 1096, 1118, 1176, 1204, 1274, 1456, 1548, 1638, 1644, 1677, 1764, 1781, 1806, 1872, 1911, 1918, 2107, 2184, 2192, 2236, 2329, 2408, 2457, 2548, 2709, 2877, 3096, 3276, 3288, 3354, 3528, 3562, 3612, 3822, 3836, 3913, 4214, 4368, 4472, 4658, 4914, 5031, 5096, 5343, 5418, 5733, 5754, 5891, 6321, 6552, 6576, 6708, 6713, 6987, 7124, 7224, 7644, 7672, 7826, 8127, 8428, 8631, 8736, 8944, 9316, 9828, 10062, 10192, 10686, 10836, 11466, 11508, 11739, 11782, 12467, 12642, 13104, 13152, 13416, 13426, 13974, 14248, 14448, 14749, 15093, 15288, 15344, 15652, 16029, 16254, 16303, 16856, 17199, 17262, 17673, 18632, 18963, 19656, 20124, 20139, 21372, 21672, 22932, 23016, 23478, 23564, 24934, 25284, 26208, 26832, 26852, 27391, 27948, 28496, 29498, 30186, 30277, 30576, 30688, 31304, 32058, 32508, 32606, 34398, 34524, 35217, 35346, 37264, 37401, 37926, 39312, 40248, 40278, 41237, 42744, 43344, 44247, 45864, 46032, 46956, 47128, 48909, 49868, 50568, 53019, 53664, 53704, 54782, 55896, 56889, 56992, 58996, 60372, 60417, 60554, 61152, 62608, 64116, 65016, 65212, 68796, 69048, 70434, 70692, 74528, 74802, 75852, 76583, 78624, 80496, 80556, 82173, 82474, 85488, 87269, 88494, 90831, 91728, 92064, 93912, 94256, 97818, 99736, 100147, 101136, 105651, 106038, 107408, 109564, 111792, 112203, 113778, 113984, 114121, 117992, 120744, 120834, 121108, 123711, 125216, 128232, 130032, 130424, 132741, 137592, 138096, 140868, 141384, 146727, 149056, 149604, 151704, 153166, 160992, 161112, 164346, 164948, 170976, 174538, 176988, 181662, 183456, 184128, 187824, 188512, 191737, 195636, 199472, 200294, 211302, 211939, 212076, 214816, 219128, 223584, 224406, 227556, 228242, 229749, 241488, 241668, 242216, 246519, 247422, 256464, 260848, 261807, 265482, 272493, 275184, 276192, 281736, 282768, 288659, 293454, 298112, 299208, 300441, 303408, 306332, 316953, 322224, 328692, 329896, 336609, 341952, 342363, 349076, 353976, 363324, 371133, 375648, 383474, 391272, 398223, 398944, 400588, 422604, 423878, 424152, 438256, 447168, 448812, 455112, 456484, 459498, 482976, 483336, 484432, 493038, 494844, 512928, 521696, 523614, 530964, 536081, 544986, 550368, 552384, 563472, 565536, 575211, 577318, 586908, 596224, 598416, 600882, 612664, 633906, 635817, 644448, 657384, 659792, 673218, 683904, 684726, 689247, 698152, 701029, 707952, 726648, 739557, 742266, 751296, 766948, 782544, 785421, 796446, 797888, 801176, 845208, 847756, 848304, 865977, 876512, 894336, 897624, 901323, 910224, 912968, 918996, 966672, 968864, 986076, 989688, 1025856, 1027089, 1043392, 1047228, ... | |

20 | 1, 281, 1967, 5901, 46457, ... | |

21 | 1, 2, ... | |

22 | 1, 13, 39, 673, 2019, 4711, 8749, 14133, 26247, 42399, 61243, 78741, 183729, 551187, ... | |

23 | 1, 4, 13, 26, 39, 52, 78, 104, 156, 208, 312, 624, 1248, ... | |

24 | 1, 5, 25633, 128165, ... | |

25 | 1, 2, 4, 20771, 40487, 41542, 80974, 83084, 161948, 166168, 323896, 643901, ... | |

26 | 1, 3, 5, 9, 15, 45, 71, 213, 355, 497, 639, 1065, 1491, 1775, 2485, 3195, 4473, 5325, 7455, 12425, 13419, 15975, 22365, 37275, 67095, 111825, 335475, ... | |

27 | 1, 11, 22, 44, 55, 110, 220, 440, 880, 1006003, ... | |

28 | 1, 3, 9, 19, 23, 57, 69, 171, 207, 253, 437, 513, 759, 1265, 1311, 1539, 2277, 3795, 3933, 4807, 11385, 11799, 14421, 24035, 35397, 43263, 72105, 129789, 216315, 389367, 648945, ... | |

29 | 1, 2, ... | |

30 | 1, 7, 160541, ... |

The least base *b* > 1 which *n* is a Wieferich number are

See also

Carmichael function

Euler's criterion

Wilson's theorem

## References

[1]

Citation Linkwww.math.dartmouth.eduSee:
Leonhard Euler (presented: August 2, 1736; published: 1741) "Theorematum quorundam ad numeros primos spectantium demonstratio" (A proof of certain theorems regarding prime numbers),

*Commentarii academiae scientiarum Petropolitanae*,**8**: 141–146. For further details on this paper, including an English translation, see: The Euler Archive.Sep 20, 2019, 3:47 AM

[2]

Citation Linkpeople.wcsu.eduSee:
L. Euler (published: 1763) "Theoremata arithmetica nova methodo demonstrata" (Proof of a new method in the theory of arithmetic),

*Novi Commentarii academiae scientiarum Petropolitanae*,**8**: 74–104. Euler's theorem appears as "Theorema 11" on page 102. This paper was first presented to the Berlin Academy on June 8, 1758 and to the St. Petersburg Academy on October 15, 1759. In this paper, Euler's totient function, , is not named but referred to as "numerus partium ad*N*primarum" (the number of parts prime to*N*; that is, the number of natural numbers that are smaller than*N*and relatively prime to*N*). For further details on this paper, see: The Euler Archive. For a review of Euler's work over the years leading to Euler's theorem, see: Ed Sandifer (2005) "Euler's proof of Fermat's little theorem"Sep 20, 2019, 3:47 AM

[7]

Citation Linkbooks.google.com"Theorematum quorundam ad numeros primos spectantium demonstratio"

Sep 20, 2019, 3:47 AM

[11]

Citation Linkpeople.wcsu.eduEd Sandifer (2005) "Euler's proof of Fermat's little theorem"

Sep 20, 2019, 3:47 AM

[12]

Citation Linkarchive.org

*An Introduction to the Theory of Numbers (Fifth edition)*Sep 20, 2019, 3:47 AM

[16]

Citation Linkbooks.google.com"Theorematum quorundam ad numeros primos spectantium demonstratio"

Sep 20, 2019, 3:47 AM

[20]

Citation Linkpeople.wcsu.eduEd Sandifer (2005) "Euler's proof of Fermat's little theorem"

Sep 20, 2019, 3:47 AM