SUPPORT THE WORK

GetWiki

Euler's theorem

ARTICLE SUBJECTS
aesthetics  →
being  →
complexity  →
database  →
enterprise  →
ethics  →
fiction  →
history  →
internet  →
knowledge  →
language  →
licensing  →
linux  →
logic  →
method  →
news  →
perception  →
philosophy  →
policy  →
purpose  →
religion  →
science  →
sociology  →
software  →
truth  →
unix  →
wiki  →
ARTICLE TYPES
essay  →
feed  →
help  →
system  →
wiki  →
ARTICLE ORIGINS
critical  →
discussion  →
forked  →
imported  →
original  →
Euler's theorem
[ temporary import ]
please note:
- the content below is remote from Wikipedia
- it has been imported raw for GetWiki
{{about|Euler's theorem in number theory||List of topics named after Leonhard Euler}}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
a^{varphi (n)} equiv 1 pmod{n}
where varphi(n) is Euler's totient function. (The notation is explained in the article {{crossref|modular arithmetic}}.) In 1736, Leonhard Euler published his proof of Fermat's little theorem,See:
  • 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. which Fermat had 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.See:
  • 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, varphi(n), 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"
The converse of Euler's theorem is also true: if the above congruence is true, then a and n must 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 n. For example, consider finding the ones place decimal digit of 7^{222}, i.e. 7^{222} pmod{10}. Note that 7 and 10 are coprime, and varphi(10) = 4. So Euler's theorem yields 7^4 equiv 1 pmod{10}, and we get 7^{222} equiv 7^{4 times 55 + 2} equiv (7^4)^{55} times 7^2 equiv 1^{55} times 7^2 equiv 49 equiv 9 pmod{10}.In general, when reducing a power of a modulo n (where a and n are coprime), one needs to work modulo varphi(n) in the exponent of a:
if x equiv y pmod{varphi(n)}, then a^x equiv a^y pmod{n}.
Euler's theorem is sometimes cited as forming the basis of the RSA 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 first encrypting a plaintext message, then later decrypting it, amounts to exponentiating a large input number by kvarphi(n) + 1, for some positive integer k. In the case that the original number is relatively prime to n, Euler's theorem then guarantees that the decrypted output number is equal to the original input number, giving back the plaintext. However, because n is a product of two distinct primes, p and q, when the number encrypted is a multiple of p or q, Euler's theorem does not apply and it is necessary to use the uniqueness provision of the Chinese Remainder Theorem. The Chinese Remainder Theorem also suffices in the case where the number is relatively prime to n, and so Euler's theorem is neither sufficient nor necessary.

Proofs

1. Euler's theorem can be proven using concepts from the theory of groups:Ireland & Rosen, corr. 1 to prop 3.3.2 The residue classes (mod 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 varphi(n) where varphi 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 varphi(n). If a is any number coprime to n then a is in one of these residue classes, and its powers a, a^2, ldots, a^k equiv 1 pmod{n} are a subgroup. Lagrange's theorem says k must divide varphi(n), i.e. there is an integer M such that kM = varphi(n). But then,
a^{varphi(n)} = a^{kM} = (a^{k})^M equiv 1^M =1 equiv 1 pmod{n}.2. There is also a direct proof:Hardy & Wright, thm. 72Landau, thm. 75 Let R = lbrace x_1, x_2, ldots, x_{varphi(n)} rbrace 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 x_i: in other words if ax_j equiv ax_k pmod{n} then j = k. (This law of cancellation is proved in the article multiplicative group of integers modulo n.See Bézout's lemma) That is, the sets R and aR = lbrace ax_1, ax_2, ldots, ax_{varphi(n)} rbrace, 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:
prod_{i=1}^{varphi(n)} x_i equiv prod_{i=1}^{varphi(n)} ax_i =a^{varphi(n)}prod_{i=1}^{varphi(n)} x_i pmod{n},
and using the cancellation law to cancel the x_is gives Euler's theorem:


a^{varphi(n)}equiv 1 pmod{n}.

Euler quotient

The Euler quotient of an integer a with respect to n is defined as:
q_n(a)=frac{a^{varphi(n)}-1}{n}
The special case of Euler quotient is Fermat quotient, it happens when n is prime.A number n coprime to a which divides q_n(a) is called generalized Wieferich number to base a. In a special case, an odd number n which divides q_n(2) is called Wieferich number.{|class="wikitable"|a|numbers n coprime to a which divides q_n(a) (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)
id=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, ...
id=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, ...
id=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, ...
id=A242959}}
|6|1, 66161, 330805, 534851, 2674255, 3152573, 10162169, 13371275, 50810845, 54715147, 129255493, 148170931, 254054225, 273575735, 301121113, 383006029, 646277465, ...
id=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, ...
id=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, ...
id=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, ...
id=A253016}}
|12|1, 2693, 123653, 1812389, 2349407, 12686723, 201183431, 332997529, ...
id=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, ...
id=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
2, 5, 8, 7, 7, 17, 18, 15, 26, 7, 3, 17, 19, 19, 26, 31, 38, 53, 28, 7, 19, 3, 28, 17, 57, 19, 80, 19, 14, 107, 115, 63, 118, 65, 18, 53, 18, 69, 19, 7, 51, 19, 19, 3, 26, 63, 53, 17, 18, 57, ... {{OEIS|id=A250206}}

See also

Notes

{{reflist|2}}

References

The Disquisitiones Arithmeticae has been translated from Gauss's Ciceronian Latin into English and German. The German edition includes all of his papers on number theory: all the proofs of quadratic reciprocity, the determination of the sign of the Gauss sum, the investigations into biquadratic reciprocity, and unpublished notes.
  • {{citation


| last1 = Gauss | first1 = Carl Friedrich
| last2 = Clarke | first2 = Arthur A. (translator into English)
| title = Disquisitiones Arithemeticae (Second, corrected edition)
| publisher = Springer
| location = New York
| date = 1986
| isbn = 0-387-96254-9}}
  • {{citation


| last1 = Gauss | first1 = Carl Friedrich
| last2 = Maser | first2 = H. (translator into German)
| title = Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition)
| publisher = Chelsea
| location = New York
| date = 1965
| isbn = 0-8284-0191-8}}
  • {{citation


| last1 = Hardy | first1 = G. H.
| last2 = Wright | first2 = E. M.
| title = An Introduction to the Theory of Numbers (Fifth edition)
| publisher = Oxford University Press
| location = Oxford
| date = 1980
| isbn = 978-0-19-853171-5}}
  • {hide}citation


| last1 = Ireland | first1 = Kenneth
| last2 = Rosen | first2 = Michael
| title = A Classical Introduction to Modern Number Theory (Second edition)
| publisher = Springer
| location = New York
| date = 1990
| isbn = 0-387-97329-X{edih}
  • {hide}citation


| last1 = Landau | first1 = Edmund
| title = Elementary Number Theory
| publisher = Chelsea
| location = New York
| date = 1966{edih}

External links



- content above as imported from Wikipedia
- "Euler's theorem" does not exist on GetWiki (yet)
- time: 1:36pm EST - Sun, Nov 18 2018
[ this remote article is provided by Wikipedia ]
LATEST EDITS [ see all ]
GETWIKI 09 MAY 2016
GETWIKI 18 OCT 2015
M.R.M. Parrott
Biographies
GETWIKI 20 AUG 2014
GETWIKI 19 AUG 2014
GETWIKI 18 AUG 2014
Wikinfo
Culture
CONNECT