En teoría de números , el teorema de Euler (también conocido como el teorema de Fermat-Euler o el teorema del totient de Euler ) establece que si n y a son enteros coprimos positivos, entonces a elevado a la potencia del totiente de n es congruente con uno, módulo n , o:
dónde es la función totient de Euler . En 1736, Leonhard Euler publicó su prueba del pequeño teorema de Fermat , [1] que Fermat había presentado sin prueba. Posteriormente, Euler presentó otras demostraciones del teorema, culminando con el "teorema de Euler" en su artículo de 1763, en el que intentó encontrar el exponente más pequeño para el cual el pequeño teorema de Fermat siempre fue cierto. [2]
Lo contrario del teorema de Euler también es cierto: si la congruencia anterior es verdadera, entonces y debe ser coprime.
El teorema es una generalización del pequeño teorema de Fermat , y el teorema de Carmichael lo generaliza más .
El teorema se puede utilizar para reducir fácilmente grandes potencias módulo . Por ejemplo, considere encontrar el dígito decimal del lugar de las unidades de, es decir . Los enteros 7 y 10 son coprimos y. Entonces el teorema de Euler producey obtenemos .
En general, al reducir una potencia de modulo (dónde y son coprime), es necesario trabajar módulo en el exponente de :
- Si , luego .
El teorema de Euler es la base del criptosistema RSA , que se usa ampliamente en las comunicaciones por Internet . En este criptosistema, se utiliza el teorema de Euler siendo n un producto de dos números primos grandes , y la seguridad del sistema se basa en la dificultad de factorizar dicho número entero.
Pruebas
Teorema 1. de Euler se puede probar usando conceptos de la teoría de los grupos : [3] Las clases de residuos modulo n que son primos entre sí a n forman un grupo bajo la multiplicación (véase el artículo grupo multiplicativo de enteros módulo n para los detalles). El orden de ese grupo es φ ( n ) . El teorema de Lagrange establece que el orden de cualquier subgrupo de un grupo finito divide el orden de todo el grupo, en este caso φ ( n ) . Si una es cualquier número primos entre sí a n entonces una está en una de estas clases de residuos, y sus poderes a , un 2 , ..., un k módulo n formar un subgrupo del grupo de clases de residuos, con una k ≡ 1 ( mod n ) . El teorema de Lagrange dice que k debe dividir φ ( n ) , es decir, hay un entero M tal que kM = φ ( n ) . Esto entonces implica,
2. También hay una prueba directa: [4] [5] Sea R = { x 1 , x 2 , ..., x φ ( n ) } un sistema de residuos reducido ( mod n ) y sea a cualquier número entero coprime a n . La demostración depende del hecho fundamental de que la multiplicación por a permuta x i : en otras palabras, si ax j ≡ ax k (mod n ) entonces j = k . (Esta ley de cancelación se demuestra en el artículo Grupo multiplicativo de enteros módulo n . [6] ) Es decir, los conjuntos R y aR = { ax 1 , ax 2 , ..., ax φ ( n ) } , considerados como conjuntos de clases de congruencia ( mod n ), son idénticos (como conjuntos; pueden enumerarse en diferentes órdenes), por lo que el producto de todos los números en R es congruente ( mod n ) con el producto de todos los números en aR :
- y el uso de la ley de cancelación para cancelar cada x i da el teorema de Euler:
Cociente de Euler
El cociente de Euler de un número entero a con respecto a n se define como:
El caso especial de un cociente de Euler cuando n es primo se llama cociente de Fermat .
Cualquier número impar n que dividase llama número de Wieferich . Esto equivale a decir que 2 φ ( n ) ≡ 1 (mod n 2 ). Como generalización, cualquier número n que sea coprime a un entero positivo a , y tal que n divida, se llama un número de Wieferich (generalizado) a la base a . Esto equivale a decir que a φ ( n ) ≡ 1 (mod n 2 ).
a | números n coprime a a que dividen (buscado hasta 1048576) | Secuencia OEIS |
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, ... (todos los números naturales) | 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, ... . | 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, 7581258, 556623428 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, 20971386592, 3198795810 34951820, 41942184, 47981937, 52427730, 59512480, ... | A257660 |
14 | 1, 29, 353, 3883, 10237, 19415, 112607, 563035, ... | |
15 | 1, 4, 8, 29131, 58262, 116524, 233048, 466096, ... | |
dieciséis | 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, 427 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, 105651, 106038, 107408, 109564, 111792, 112203, 113778, 113984, 114121, 117992, 120744, 120834, 121108, 123711, 125216, 128232, 130032, 130424, 132741, 137592, 138096, 140868, 141384, 146727, 149604, 151704, 153166, 160992, 161112, 164346, 164948, 170976, 174538, 176988, 181662, 183456, 184128, 187824, 188512, 191737, 195636, 199472, 200294, 211302, 211939, 212076, 21848, 223584, 21912 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, 3533952, 3490 363324, 371133, 375648, 383474, 391272, 398223, 398944, 400588, 422604, 423878, 424152, 438256, 447168, 448812, 455112, 456484, 459498, 482976, 483336, 484432, 493038, 494844, 5129 530964, 536081, 544986, 550368, 552384, 563472, 565536, 575211, 577318, 586908, 596224, 598416, 600882, 612664, 633906, 635817, 644448, 657384, 659792, 673218, 683904, 6871026, 69829 707952, 726648, 739557, 742266, 751296, 766948, 782544, 785421, 796446, 797888, 801176, 845208, 847756, 848304, 865977, 876512, 894336, 897624, 901323, 910224, 91260968, 966, 9182996 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, ... |
La base mínima b > 1 que n es un número de Wieferich son
Ver también
Notas
- ^ Ver:
- Leonhard Euler (presentado: 2 de agosto de 1736; publicado: 1741) "Theorematum quorundam ad numeros primos spectantium demostratio" (Una demostración de ciertos teoremas sobre números primos), Commentarii academiae scientiarum Petropolitanae , 8 : 141-146.
- Para obtener más detalles sobre este documento, incluida una traducción al inglés, consulte: The Euler Archive .
- ^ Ver:
- L. Euler (publicado: 1763) "Theoremata arithmetica nova methodo demonstrata" (Prueba de un nuevo método en la teoría de la aritmética), Novi Commentarii academiae scientiarum Petropolitanae , 8 : 74-104. El teorema de Euler aparece como "Teorema 11" en la página 102. Este artículo se presentó por primera vez a la Academia de Berlín el 8 de junio de 1758 y a la Academia de San Petersburgo el 15 de octubre de 1759. En este artículo, la función totient de Euler,, no se nombra sino que se denomina "numerus partium ad N primarum" (el número de partes primo de N ; es decir, el número de números naturales que son menores que N y relativamente primos con N ).
- Para obtener más detalles sobre este documento, consulte: The Euler Archive .
- Para una revisión del trabajo de Euler a lo largo de los años que condujeron al teorema de Euler, ver: Ed Sandifer (2005) "Demostración de Euler del pequeño teorema de Fermat"
- ^ Irlanda y Rosen, corr. 1 a la hélice 3.3.2
- ^ Hardy y Wright, thm. 72
- ^ Landau, thm. 75
- ^ Ver el lema de Bézout
Referencias
The Disquisitiones Arithmeticae se ha traducido del latín ciceroniano de Gauss al inglés y al alemán. La edición alemana incluye todos sus artículos sobre teoría de números: todas las pruebas de reciprocidad cuadrática, la determinación del signo de la suma de Gauss, las investigaciones sobre la reciprocidad bicuadrática y notas inéditas.
- Gauss, Carl Friedrich; Clarke, Arthur A. (traducido al inglés) (1986), Disquisitiones Arithemeticae (Segunda edición corregida) , Nueva York: Springer , ISBN 0-387-96254-9
- Gauss, Carl Friedrich; Maser, H. (traducido al alemán) (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae y otros artículos sobre teoría de números) (Segunda edición) , Nueva York: Chelsea, ISBN 0-8284-0191-8
- Hardy, GH; Wright, EM (1980), Introducción a la teoría de los números (quinta edición) , Oxford: Oxford University Press , ISBN 978-0-19-853171-5
- Irlanda, Kenneth; Rosen, Michael (1990), A Classical Introduction to Modern Number Theory (Segunda edición) , Nueva York: Springer , ISBN 0-387-97329-X
- Landau, Edmund (1966), Teoría de números elemental , Nueva York: Chelsea
enlaces externos
- Weisstein, Eric W. "Teorema de Totient de Euler" . MathWorld .
- Teorema de Euler-Fermat en PlanetMath