Artículos

5.1: El orden de números enteros y raíces primitivas - Matemáticas


En esta sección, estudiamos el orden de un número entero módulo (n ), donde (n ) es positivo. Por lo tanto, según el principio de ordenación correcta, hay un número entero positivo mínimo (x ) que satisface esta congruencia (a ^ {x} equiv 1 (mod n) ).

Sea ((a, b) = 1 ). El entero positivo más pequeño (x ) tal que (a ^ {x} equiv 1 (mod b) ) se llama el orden de (a ) modulo (b ). Denotamos el orden de (a ) módulo (b ) por (ord_ba ).

(ord_72 = 3 ) desde (2 ^ 3 equiv 1 (mod 7) ) mientras que (2 ^ 1 equiv 2 (mod 7) ) y (2 ^ 2 equiv 4 (mod 7) ).

Para encontrar todos los enteros (x ) tales que (a ^ x equiv 1 (mod b) ), necesitamos el siguiente teorema.

Si ((a, b) = 1 ) con (b> 0 ), entonces el entero positivo (x ) es una solución de la congruencia (a ^ x equiv 1 (mod b) ) si y solo si (ord_ba mid x ).

Teniendo (ord_ba mid x ), entonces tenemos ese (x = k.ord_ba ) para algún entero positivo (k ). Entonces [a ^ x = a ^ {kord_ba} = (a ^ {ord_ba}) ^ k equiv 1 (mod b). ] Ahora si (a ^ x equiv 1 (mod b) ) , usamos el algoritmo de división para escribir [x = q ord_ba + r, 0 leq r

Dado que (ord_72 = 3 ), entonces (2 ^ {15} equiv 1 (mod 7) ) mientras que 10 no es una solución para (2 ^ x equiv 1 (mod 7) ).

Si ((a, b) = 1 ) con (b> 0 ), entonces [a ^ i equiv a ^ j (mod b) ] donde (i ) y (j ) son enteros no negativos, si y solo si [i equiv j (mod ord_ba) ]

Suponga que [i equiv j (mod ord_ba) mbox {y} 0 leq j leq i. ] Entonces tenemos (ij = k.ord_ba ), donde (k ) es un número entero positivo. Por tanto, [a ^ i = a ^ {j + k.ord_ba} = a ^ j (a ^ {ord_ba}) ^ k equiv a ^ j (mod b). ] Supongamos ahora que (a ^ i equiv a ^ j (mod b) ) con (i geq j ). Por lo tanto, tenemos [a ^ i equiv a ^ ja ^ {ij} equiv a ^ j (mod b) ] Dado que ((a, b) = 1 ), tenemos ((a ^ j , b) = 1 ) y por lo tanto, por el teorema 22, obtenemos [a ^ {ij} equiv 1 (mod b). ] Por el teorema 54, obtenemos que (ord_ba mid (ij) ) y por tanto (i equiv j (mod b) ).

Introducimos ahora raíces primitivas y discutimos sus propiedades. Nos interesan los enteros cuyo orden módulo otro entero es ( phi (b) ). En uno de los ejercicios, se le pide a uno que demuestre que si (a ) y (b ) son relativamente primos, entonces (ord_ba mid phi (b) ).

Si ((r, m) = 1 ) con (m> 0 ) y si (ord_mr = phi (m) ) entonces (r ) se llama un módulo raíz primitivo (m ) .

Observe que ( phi (7) = 6 ) por lo tanto (2 ) no es un módulo raíz primitivo (7 ). Mientras que (ord_73 = 6 ) y por tanto (3 ) es un módulo raíz primitivo (7 ).

Si ((r, m) = 1 ) con (m> 0 ) y si (r ) es un módulo raíz primitivo (n ), entonces los enteros ( {r ^ 1, r ^ 2, ... r ^ { phi (m)} } ) forman un conjunto de residuos reducido módulo (m ).

Para probar que el conjunto ( {r ^ 1, r ^ 2, ... r ^ { phi (m)} } ) forma un conjunto de residuos reducido módulo (m ) necesitamos demostrar que cada dos de ellos son primos relativos y que ninguno de ellos es congruente módulo (m ). Dado que ((r, m) = 1 ), se deduce que ((r ^ n, m) = 1 ) para todos los enteros positivos (n ). Por tanto, todas las potencias de (r ) son primos relativos a (m ). Para mostrar que no hay dos potencias en el conjunto anterior son equivalentes módulo (m ), suponga que [r ^ i equiv r ^ j (mod m). ] Por el Teorema 55, vemos que [i equiv j (mod ord_m phi (m)). ] Observe que (1 leq i, j leq phi (m) ) y por tanto (i = j ).

Si (ord_ma = t ) y (u ) es un número entero positivo, entonces [ord_m (a ^ u) = t / (t, u). ]

Deje [v = ord_m (a ^ u), w = (t, u), t = t_1w mbox {y} u = u_1w. ] Observe que ((t_1, u_1) = 1. )

Como (t_1 = t / (t, u) ), queremos mostrar que (ord_m (a ^ u) = t_1 ). Para hacer esto, mostraremos que ((a ^ {u}) ^ {t_1} equiv 1 (mod m) ) y que si ((a ^ u) ^ v equiv 1 (mod m ) ), luego (t_1 mid v ). Primero tenga en cuenta que [(a ^ u) ^ {t_1} = (a ^ {u_1w}) ^ {(t / w)} = (a ^ t) ^ {u_1} equiv 1 (mod m). ] Por tanto, según el Teorema 54, tenemos (v mid t_1 ). Ahora, por otro lado, desde [(a ^ u) ^ v = a ^ {uv} equiv 1 (mod m), ] sabemos que (t mid uv ). Por tanto (t_1w mid u_1wv ) y por tanto (t_1 mid u_1v ). Como ((t_1, u_1) = 1 ), vemos que (t_1 mid v ). Dado que (v mid t_1 ) y (t_1 mid v ), concluimos que (v = t_1 = t / w = t / (t, u) ).

Vemos que (ord_73 ^ 4 = 6 / (6,4) ) ya que (ord_73 = 6 ).

Sea (r ) un módulo raíz primitivo (m ), donde (m ) es un entero positivo, (m> 1 ). Entonces (r ^ u ) es un módulo raíz primitivo (m ) si y solo si ((u, phi (m)) = 1 ).

Por el teorema 57, vemos que [ord_mr ^ u = ord_mr / (u, ord_mr) = phi (m) / (u, phi (m)). ] Así (ord_mr ^ u = phi (m ) ) y (r ^ u ) es una raíz primitiva si y solo si ((u, phi (m)) = 1 ).

El corolario anterior conduce al siguiente teorema

Si el entero positivo (m ) tiene una raíz primitiva, entonces tiene un total de ( phi ( phi (m)) ) raíces primitivas incongruentes.

Sea (r ) un módulo raíz primitivo (m ). Por el teorema 56, vemos que ( {r ^ 1, r ^ 2, ..., r ^ { phi (m)} } ) forman un sistema de residuos reducido módulo (n ). Por el Corolario 1, se sabe que (r ^ u ) es un módulo raíz primitivo (m ) si y solo si ((u, phi (m)) = 1 ). Por lo tanto, tenemos exactamente ( phi ( phi (m)) ) tales enteros (u ) que son primos relativos a ( phi (m) ) y, por lo tanto, hay exactamente ( phi ( phi (m)) ) raíces primitivas módulo (m ).

Ejercicios

  1. Determine (ord_ {13} 10 ).
  2. Determine (ord_ {11} 3. )
  3. Demuestre que 5 es una raíz primitiva de 6.
  4. Muestre que si ( bar {a} ) es un inverso de (a ) módulo (n ), entonces (ord_na = ord_n bar {a} ).
  5. Demuestre que si (n ) es un número entero positivo, y (a ) y (b ) son números primos relativos a (n ) tales que ((ord_na, ord_nb) = 1 ), entonces (ord_n (ab) = ord_na.ord_nb ).
  6. Muestre que si (a ) es un número entero primo relativo al entero positivo (m ) y (ord_ma = st ), entonces (ord_ma ^ t = s ).
  7. Muestre que si (a ) y (n ) son primos relativos con (n> 0 ), entonces (ord_na mid phi (n) ).

No existe una fórmula general para encontrar una raíz primitiva. Por lo general, lo que hace es elegir un número y probarlo. Una vez que encuentre una raíz primitiva, encontrará todas las demás.

Como pruebas

Para probar que $ a $ es una raíz primitiva de $ p $, debe hacer lo siguiente. Primero, sea $ s = phi (p) $ donde $ phi () $ es la función totient de Euler. Si $ p $ es primo, entonces $ s = p-1 $. Entonces necesitas determinar todos los factores primos de $ s $: $ p_1, ldots, p_k $. Finalmente, calcula $ a ^ mod p $ para todos $ i = 1 ldots k $, y si encuentra $ 1 $ entre los residuos, NO es una raíz primitiva, de lo contrario lo es.

Entonces, básicamente necesitas calcular y verificar $ k $ números donde $ k $ es el número de factores primos diferentes en $ phi (p) $.

Encontremos la raíz primitiva más baja de $ 761 $:

  • $ s = phi (761) = 760 = 2 ^ 3 times5 times19 $
  • los poderes para probar son: $ 760/2 = 380 $, $ 760/5 = 152 $ y $ 760/19 = 40 $ (solo 3 en lugar de probarlos todos)
  • prueba 2:
    • $ 2 ^ <380> equiv 1 mod 761 $ oops
    • $ 3 ^ <380> equiv -1 mod 761 $ OK
    • $ 3 ^ <152> equiv 1 mod 761 $ oops
    • $ 5 ^ <380> equiv 1 mod 761 $ oops
    • $ 6 ^ <380> equiv -1 mod 761 $ OK
    • $ 6 ^ <152> equiv 67 mod 761 $ OK
    • $ 6 ^ <40> equiv -263 mod 761 $ ¡hurra!

    Entonces, la raíz menos primitiva de 761 es 6.

    Como eliges

    Por lo general, elige al azar, o comienza desde 2 y sube (cuando busca la raíz menos primitiva, por ejemplo), o en cualquier otra secuencia según sus necesidades.

    Tenga en cuenta que cuando elige al azar, cuantos más factores primos haya en $ phi (p) $, menor es, en general, la probabilidad de encontrar uno al azar. Además, habrá más poderes para probar.

    Por ejemplo, si eliges un número aleatorio para probar si es una raíz primitiva de $ 761 $, entonces la probabilidad de encontrar uno es aproximadamente $ frac <1> <2> times frac <4> <5> times frac <18> <19> $ o 38%, y hay 3 poderes para probar. Pero si está buscando raíces primitivas de, digamos, $ 2311 $, entonces la probabilidad de encontrar una al azar es aproximadamente del 20% y hay 5 poderes para probar.

    ¿Cómo encuentras todas las otras raíces primitivas?

    Una vez que haya encontrado una raíz primitiva, podrá encontrar fácilmente todas las demás. De hecho, si $ a $ es un mod de raíz primitivo $ p $, y $ p $ es primo (para simplificar), entonces $ a $ puede generar todos los demás residuos $ 1 ldots (p-1) $ como potencias: $ a ^ 1 equiv a, a ^ 2, ldots, a ^ equiv 1 $. Y $ a ^ m mod p $ es otra raíz primitiva si y solo si $ m $ y $ p-1 $ son coprime (si $ gcd (m, p-1) = d $ entonces $ (a ^ m) ^ <(p-1) / d> equiv (a ^)^ equiv 1 mod p $, entonces necesitamos $ d = 1 $). Por cierto, esta es exactamente la razón por la que tienes $ phi (p-1) $ raíces primitivas cuando $ p $ es primo.

    Por ejemplo, $ 6 ^ 2 = 36 $ o $ 6 ^ <15> equiv 686 $ no son raíces primitivas de $ 761 $ porque $ gcd (2,760) = 2 & gt1 $ y $ gcd (15,760) = 5 & gt1 $, pero, por ejemplo, $ 6 ^ 3 = 216 $ es otra raíz primitiva de 761.


    Subsección 10.5.1 Encontrar una raíz superior ¶ enlace permanente

    Esta es una forma de resolver la primera congruencia. Primero, encuentre un módulo raíz primitivo (19 ). Obviamente, podríamos preguntarle a Sage o usar Lemma 10.2.3 con prueba y error. En un pasado no muy lejano, la parte posterior de cada texto de teoría de números tenía una tabla de raíces primitivas.

    Ahora lo que haremos es intentar representar ambas cosas lados de beginx ^ 4 equiv 13 text <(mod> 19) end como poderes de esa raíz primitiva.

    La parte fácil es representar (x ^ 4 ) simplemente decimos que (x equiv 2 ^ i ) para algunos (aún desconocidos) (i ), entonces beginx ^ 4 equiv left (2 ^ i right) ^ 4 equiv 2 ^ <4i> . end La parte más difícil es averiguar qué potencia de (2 ) da (13 ). Nuevamente, no hay atajos, aunque los libros en el pasado tenían enormes tablas de ellos y poderes (para una fácil referencia). En la práctica, uno tendría todos los poderes de una raíz primitiva determinada disponibles para su uso con anticipación.

    Sustituyendo las raíces primitivas por (x ^ 4 ) y (13 ), podemos decir que beginx ^ 4 equiv 13 text <(mod> 19) end se convierte en begin2 ^ <4i> equiv 2 ^ <5> text <(mod> 19) . End

    Este es un tipo de problema mucho más familiar. ¿Cómo hubiéramos resuelto esto en la escuela secundaria? Lo resolverías de esta manera, con ecuaciones (no congruencias): begin2 ^ <4i> = 2 ^ <5> Rightarrow 4i = 5 Rightarrow i = 5/4 . End Intentaremos hacer algo muy similar aquí.

    Lo que es muy importante es que esta congruencia, en cierto sentido, ya no es realmente una congruencia en ( mathbb_ <19> ). Para ser precisos, todo lo que está a la vista está realmente en (U_ <19> ), un grupo cíclico de orden ( phi (19) = 18 ). ¡Pero un grupo cíclico de orden (18 ) sería lo mismo que pensar módulo dieciocho! Entonces podemos sacar los exponentes, como en precálculo, pero hacer cosas (mod (18 )): begin4i equiv 5 text <(mod> 18) . End (Vea el ejercicio 10.6.12.)

    Lamentablemente, esto no tiene solución. ¡Pero lo descubrimos sin tener que tomar una de cada cuatro energías! De hecho, hacer eso confirma nuestro resultado:

    Ejemplo 10.5.1

    Probemos la misma congruencia módulo (17 ) en su lugar, es decir, ¿podemos resolver beginx ^ 4 equiv 13 text <(mod> 17) ? end Aquí, una raíz primitiva es (3 ), y resulta que (3 ^ 4 equiv 13 ), así que podemos intentarlo. Esto da begin3 ^ <4i> equiv 3 ^ 4 text <(mod> 17) Rightarrow 4i equiv 4 text <(mod> 16) ,, end que definitivamente tiene soluciones.

    De hecho, hay cuatro soluciones ( (1,5,9,13 )) para la congruencia reducida begini equiv 1 text <(mod> 4) end entonces hay cuatro soluciones ( (3 ^ 1,3 ^ 5,3 ^ 9,3 ^ <13> )) a la congruencia original. Revisemos esto:

    Incluso puedes verlo en funcionamiento para cosas más complicadas.

    Ejemplo 10.5.2

    Si intentamos resolver (x ^ 6 equiv 8 ) (mod (49 )), necesitaremos una raíz primitiva de 49 3 trabajos. Puedo averiguar qué potencia (3 ^ i ) de (3 ) produce (8 ):

    Entonces escribimos (x = 3 ^ i ) para algunos aún desconocidos (i ), y obtenemos begin3 ^ <6i> equiv 3 ^ <36> text <(mod> 49) , end lo que nos da begin6i equiv 36 text <(mod> phi (49) = 42) end y esto se reduce a begini equiv 6 text <(mod> 7) . end Entonces (i = 6,13,20,27,34,41 ) todo funciona, lo que significa que (x = 3 ^ equiv 43,10,16,6,39,33 ) todo debería funcionar.


    Euler y rsquos Totient

    Otro método interesante para determinar el orden de un elemento es usar la función totient de Euler & rsquos. Este es un método más rápido, ya que no necesitamos verificar cada elemento en orden en un enfoque de & ldquobrute-force & rdquo y solo necesitaremos verificar los enteros que son divisores de ϕ (n).

    Veamos & rsquos un teorema que usa Euler & rsquos totient:

    Esto dice que el orden de un módulo n divide a ϕ (n) si y solo si su máximo común divisor es 1.

    En lugar de buscar en todo el espacio un entero m donde a m ≡ 1 mod n, ¡solo buscamos por los divisores que dividen uniformemente el resultado de ϕ (n)!

    Esto tiene más sentido con algunos ejemplos.

    Algunos pueden haber notado que el teorema para encontrar el entero positivo más pequeño m tal que a m ≡ 1 mod n es muy similar al teorema de Euler & rsquos:

    una ϕ (n) ≡ 1 mod n

    Si bien el teorema de Euler & rsquos nos dará un número entero que es congruente con 1 mod n (cuando a y n son primos relativos, por supuesto), es posible que no nos dé la pequeñísimo entero positivo.


    Anillo de enteros¶

    La clase IntegerRing representa el anillo de enteros (precisión arbitraria). Cada entero es una instancia de la clase Entero , que se define en un módulo de extensión Pyrex que envuelve enteros GMP (el mpz_t escriba GMP).

    Hay instancias únicas de clase. IntegerRing . Para crear un Entero , coaccionar ya sea un Python int, long o una cadena. Varios otros tipos también coaccionarán a los números enteros, cuando tenga sentido.

    Para introducir el anillo de enteros, ilustramos la creación, llamando a algunas funciones y trabajando con sus elementos.

    Se pueden dar cadenas para crear números enteros. Cadenas que comienzan con 0x se interpretan como hexadecimales y las cadenas que comienzan con 0 se interpretan como octal:

    Como inverso a dígitos () , se aceptan listas de dígitos, siempre que proporcione una base. Las listas se interpretan en orden little-endian, de modo que la entrada I de la lista es el coeficiente de base ^ i :

    A continuación, ilustramos la aritmética básica en :

    Cuando dividimos en números enteros usando /, el resultado se convierte automáticamente en el campo de los números racionales, incluso si el resultado es un número entero.

    Para la división del piso, en su lugar, use el operador //:

    A continuación, ilustramos la aritmética con coerción automática. Los tipos que coaccionan son: str, int, long, Integer.

    Podemos crear números enteros a partir de varios tipos de objetos.

    Devuelve el grado absoluto de los números enteros, que es 1

    Devuelve la característica de los enteros, que es 0

    Devuelve la finalización de Z en p.

    Devuelve el grado de los números enteros, que es 1

    Devuelve el orden en el campo numérico definido por poli generado (como un anillo) por una raíz de poli.

    Devuelve el campo de números racionales, el campo de fracción de los números enteros.

    Devuelve el generador aditivo de los enteros, que es 1.

    Devuelve la tupla (1,) que contiene un solo elemento, el generador aditivo de los enteros, que es 1.

    Devuelve Verdadero, ya que los elementos de los números enteros no tienen que imprimirse entre paréntesis alrededor, cuando son coeficientes, por ejemplo, en un polinomio.

    Devuelve falso: los números enteros no son un campo.

    Devuelve falso: los números enteros son un anillo infinito.

    Devuelve que el anillo entero es, de hecho, un anillo integralmente cerrado.

    Devolver verdadero: los números enteros son un anillo noetheriano.

    Devuelve True si ZZ es un subanillo de otro de forma natural.

    Cada anillo de característica 0 contiene ZZ como subanillo.

    Devuelve la dimensión de Krull de los enteros, que es 1.

    Devuelve el número de generadores aditivos del anillo, que es 1.

    Devuelve el orden (cardinalidad) de los enteros, que es + Infinito.

    Devuelve un número entero de grado 1 para la propiedad euclidiana de ZZ, a saber, 1.

    Devuelve el cociente de por el ideal o entero .

    La distribución predeterminada para ZZ.random_element () se basa en , dónde es una variable aleatoria distribuida uniformemente entre -1 y 1. Esto da , y por . La mayoría de las muestras serán pequeñas -1, 0 y 1 con probabilidad de 1/5 cada una. Pero también tenemos una proporción pequeña pero no despreciable de & # 8220outliers & # 8221 , por ejemplo, esperamos que en una de cada 1250 muestras.

    De hecho, usamos un truncamiento fácil de calcular de la distribución anterior, las probabilidades dadas anteriormente se mantienen bastante bien hasta aproximadamente , pero alrededor algunos valores nunca se devolverán en absoluto, y nunca devolveremos nada mayor que .

    La distribución predeterminada es en promedio del 50%.

    La distribución uniforme predeterminada es números enteros entre -2 y 2 inclusive:

    Si se da un rango, la distribución es uniforme en ese rango:

    Tenga en cuenta que no se incluye el punto final correcto:

    Calculamos un histograma sobre 1000 muestras de la distribución predeterminada:

    Función de rango optimizada para entero Sage.

    Utiliza un código diferente si el paso no encaja en un largo:

    Devuelve el campo de residuo de los enteros módulo el primo dado, es decir .

    • principal - un número primo
    • cheque - (booleano, por defecto True) si se verifica o no la primacía de primo.

    SALIDA: El campo de residuos en este cebado.

    La construcción puede ser de un ideal principal en lugar de uno principal:

    Devuelve una raíz n & # 8217th primitiva de la unidad en los enteros, o genera un error si no existe ninguno

    SALIDA: una raíz de unidad n & # 8217th en ZZ

    Calcule y devuelva una base del teorema del resto chino para la lista X de enteros coprimos.

    E [i] tiene la propiedad de que si A es una lista de objetos, por ejemplo, números enteros, vectores, matrices, etc., donde A [i] es módulos X [i], entonces una elevación CRT de A es simplemente

    ALGORITMO: Para calcular E [i], calcule los números enteros syt tales que

    Entonces E [i] = t * (pinchar sobre i! = J de X [j]). Observe que la ecuación (*) implica que E [i] es congruente con 1 módulo X [i] y con 0 módulo el otro X [j] para j! = I.

    COMPLEJIDAD: Calculamos len (X) Extended GCD & # 8217s.

    Devuelve la factorización del entero positivo como una lista ordenada de tuplas tal que .


    5.1: El orden de números enteros y raíces primitivas - Matemáticas

    Artin conjeturó que esta secuencia es infinita.

    Conjetura: la secuencia contiene infinitos pares de primos gemelos. - Benoit Cloitre, 8 de mayo de 2003

    Pieter Moree escribe (20 de octubre de 2004): Suponiendo la Hipótesis de Riemann generalizada, se puede demostrar que la densidad de primos p tal que un entero prescrito g tiene orden (p-1) / t, con t fijo, existe y, además, se puede calcular. Esta densidad será un número racional multiplicado por la llamada constante de Artin. Para 2 y 10, la densidad de las raíces primitivas es A, la constante de Artin en sí.

    Parece que esta secuencia consta de A050229 <1,2>.

    Primes p tales que 1 / p, cuando se escribe en base 2, tiene un período p-1, que es el período más grande posible para cualquier número entero.

    El entero positivo 2 * m-1 está en la secuencia sif A179382 (m) = m-1. - Vladimir Shevelev, 14 de julio de 2010

    Estos son los primos impares p para los cuales el polinomio 1 + x + x ^ 2 +. + x ^ (p-1) es irreductible sobre GF (2). - V. Raman, 17 de septiembre de 2012 [Corregido por N. J. A. Sloane, 17 de octubre de 2012]

    Prime (n) está en la secuencia si (y conjeturalmente solo si) A133954 (n) = prime (n). - Vladimir Shevelev, 30 de agosto de 2013

    Pollack muestra que, en el GRH, hay algo de C tal que a (n + 1) - a (n) & lt C infinitamente a menudo (de hecho, 1 puede ser reemplazado por cualquier número entero positivo). Además, para cualquier m, a (n), a (n + 1),. a (n + m) son números primos consecutivos infinitamente a menudo. - Charles R Greathouse IV, 5 de enero de 2015

    Todos los términos son congruentes con 3 o 5 módulo 8. Si definimos

    luego, por la conjetura de Artin, Q (N)

    2 * C * (Pi (N, 3) + Pi (N, 5)), donde C = A005596 es la constante de Artin.

    Conjetura: si definimos más

    M. Abramowitz e I. A. Stegun, eds., Manual de funciones matemáticas, Oficina Nacional de Matemáticas Aplicadas a los Estándares. Serie 55, 1964 (y varias reimpresiones), pág. 864.

    E. Bach y Jeffrey Shallit, Teoría algorítmica de números, veo p. 221.

    J. H. Conway y R. K. Guy, The Book of Numbers, Copernicus Press, Nueva York, 1996 ver p. 169.

    M. Kraitchik, Recherches sur la Théorie des Nombres. Gauthiers-Villars, París, vol. 1, 1924, vol. 2, 1929, ver vol. 1, pág. 56.

    Lehmer, D. H. y Lehmer, Emma Heuristics, ¿alguien? en Estudios de análisis matemático y temas relacionados, págs. 202-210, Stanford Univ. Prensa, Stanford, California, 1962.

    D. Shanks, Problemas resueltos y no resueltos en teoría de números, 2do. ed., Chelsea, 1978, pág. 81.

    N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (incluye esta secuencia).

    Antti Karttunen, Tabla de n, a (n) para n = 1..10000 (primeros 1000 términos de T. D. Noe)

    M. Abramowitz e I. A. Stegun, eds., Manual de Funciones Matemáticas, Oficina Nacional de Estándares, Matemáticas Aplicadas. Serie 55, Décima Impresión, 1972 [copia escaneada alternativa].

    J. Conde, M. Miller, J. M. Miret y K. Saurav, Sobre la inexistencia de casi dígrafos de Moore de grado cuatro y cinco, Matemáticas en ciencias de la computación, 9 (2) (2015), 145-149.

    K. Dilcher y L. Ericksen, Reducibilidad e irreductibilidad de polinomios de Stern (0, 1), Communications in Mathematics, 22 (2014), 77-102.

    R. Gupta y M. R. Murty, Un comentario sobre la conjetura de Artin, Invent. Matemáticas. 78 (1984), 127-230.

    C. Hooley, Sobre la conjetura de Artin, J. Reine Angewandte Math., 225 (1967), 209-220.

    Robert Jackson, Dmitriy Rumynin y Oleg V. Zaboronski, Un enfoque de RAID-6 basado en grupos cíclicos, Matemáticas aplicadas y ciencias de la información, 5 (2) (2011), 148-170.

    Qifu Tyler Sun, Hanqi Tang, Zongpeng Li, Xiaolong Yang y Keping Long, códigos de red lineal de desplazamiento circular con longitudes de bloque arbitrarias impares, arXiv: 1806.04635 [cs.IT], 2018.

    El mundo de las matemáticas de Eric Weisstein, la constante de Artin.

    Delta (a (n), 2 ^ a (n) * x) = a (n) * Delta (a (n), 2 * x), donde Delta (k, x) es la diferencia entre los números de maldad (A001969 ) y números enteros odiosos (A000069) divisibles por k en el intervalo [0, x). - Vladimir Shevelev, 30 de agosto de 2013

    Seleccione [Prime @ Range @ 200, PrimitiveRoot @ # == 2 & amp] (* Robert G. Wilson v, 11 de mayo de 2001 *)

    Cf. A002326 para el orden multiplicativo de 2 mod 2n + 1. (Alternativamente, el valor menos positivo de m tal que 2n + 1 divide 2 ^ m-1).

    Cf. A216838 (primos impares para los que 2 no es una raíz primitiva).

    Última modificación el 4 de julio a las 16:02 EDT de 2021. Contiene 345745 secuencias. (Ejecutando en oeis4.)


    ¿Cuál es la forma más motivadora de introducir raíces primitivas?

    Estoy enseñando teoría de números elemental a estudiantes de primer año de pregrado. ¿Cómo introducir el orden de un entero módulo ny raíces primitivas? ¿Cómo puedo hacer de este un tema motivador y hay aplicaciones de esta área? Estoy viendo algo que tendrá un impacto.

    Para empezar, ¿puedes decirnos por qué? usted ¿Crees que los órdenes y las raíces primitivas son importantes? Si no lo hace, ¿por qué les enseñaría?

    El pequeño teorema de Fermat & # x27, y más generalmente el teorema de Euler & # x27, son resultados centrales en un curso de teoría de números elemental (espero que estén de acuerdo). La noción de orden de un número en aritmética modular podría considerarse un refinamiento de esto: para primos p y todos a mod p distintos de cero tenemos un p-1 = 1 mod p, y es natural preguntar por cada a cuando su potencias mod p primer alcance 1. Haz una tabla de esto para p = 7 y p = 11 para ver que este & quot; primer golpe & quot varía con a. Ese "primer golpe" es el orden de un mod p.

    El orden tiene una propiedad de divisibilidad muy conveniente cuando intentas encontrarlo: a k = 1 mod n si y solo si el orden de un mod n es un factor de k. Entonces, tan pronto como encuentre a k = 1 mod n para algún k, el orden se puede encontrar entre los factores de k. En particular, el orden de un mod n es siempre un factor de phi (n).

    Una interpretación concreta: el período del decimal para la fracción unitaria 1 / n, cuando n no es divisible por 2 o 5, es del orden de 10 mod n. Por ejemplo, el período es un factor de phi (n).

    Ejemplo: ¿cuál es el período de la expansión decimal de 1/51?

    Respuesta: Necesitamos encontrar el orden de 10 mod 51. Dado que phi (51) = phi (3) phi (17) = (2) (16) = 32, el orden de 10 mod 51 divide 32, por lo que el período de la expansión decimal de 1/51 es 1, 2, 4, 8, 16 o 32. (Incluso antes de ir más allá, ¿no es interesante que sepamos que esos son los valores posibles del período ya?)

    Módulo de trabajo 51, 10 2 = 100 = -2, 10 4 = 4, 10 8 = 16 y 10 16 = 256 = 51 (5) + 1 = 1.

    Por lo tanto, 10 mod 51 tiene el orden 16, por lo que el decimal para 1/51 tiene el período 16. Isn & # x27t it interesante que podríamos resolver eso sin calcular explícitamente el decimal en absoluto? Ni siquiera sabemos cuál es la parte repetida, ¡pero sabemos cuánto tiempo dura! (Por supuesto, puede verificar en un dispositivo informático que la parte que se repite es 0196078431372549, pero eso es simplemente un procesamiento de números). Los estudiantes piensan que los decimales son solo cadenas de dígitos al azar, pero hay estructura en las expansiones decimales de fracciones, y la aritmética modular es la clave para desbloquear esa información de una manera perspicaz.

    Un resultado similar se mantiene en otras bases, por ejemplo, si escribe la expansión binaria de 1 / n y n es impar, su período es del orden de 2 mod n.

    En cuanto a las raíces primitivas, considere la posibilidad de que no sean tan importantes para un primer plato como cree. ¿Hay algún resultado que desee demostrar que necesita raíces primitivas pero que no se trata directamente de raíces primitivas?


    5.1: El orden de números enteros y raíces primitivas - Matemáticas

    En otras palabras, al menos m & gt 0 tal que 2n + 1 divida 2 ^ m-1.

    Número de riffle barajas de 2n + 2 cartas necesarias para devolver un mazo al estado inicial. Un riffle shuffle reemplaza una lista s (1), s (2),. s (m) con s (1), s ((i / 2) +1), s (2), s ((i / 2) +2),. a (1) = 2 porque un riffle shuffle de [1, 2, 3, 4] requiere 2 iteraciones [1, 2, 3, 4] - & gt [1, 3, 2, 4] - & gt [1, 2, 3, 4] para restaurar el orden original.

    Con respecto a la complejidad de calcular esta secuencia, véase, por ejemplo, Bach y Shallit, p. 115, ejercicio 8.

    No es difícil demostrar que si 2n + 1 es primo, entonces 2n es múltiplo de a (n). Pero la conversación no es verdadera. De hecho, se puede probar que a (2 ^ (2t-1)) = 4t. Por lo tanto, si n = 2 ^ (2t-1), donde, para cualquier m & gt 0, t = 2 ^ (m-1) entonces 2n es un múltiplo de a (n) mientras que 2n + 1 es un número de Fermat que, como es bien conocido, no siempre es un primo. Es un problema interesante describir todos los números compuestos para los que 2n es divisible por a (n). - Vladimir Shevelev, 9 de mayo de 2008

    Para obtener un algoritmo de cálculo de a (n), consulte el comentario del autor en A179680. - Vladimir Shevelev, 21 de julio de 2010

    De V. Raman, 18 de septiembre de 2012, 10 de diciembre de 2012: (Inicio)

    Si 2n + 1 es primo, entonces el polinomio (x ^ (2n + 1) +1) / (x + 1) se factoriza en 2n / a (n) polinomios del mismo grado a (n) sobre GF (2).

    Si (x ^ (2n + 1) +1) / (x + 1) es irreducible sobre GF (2), entonces 2n + 1 es primo y 2 es una raíz primitiva (mod 2n + 1) (cf. A001122) .

    Para todo n & gt 0, a (n) es el grado del factor polinomial irreducible más grande para el polinomio (x ^ (2n + 1) +1) / (x + 1) sobre GF (2). (Final)

    a (n) es un factor de phi (2n + 1) (A000010 (2n + 1)). - Douglas Boffey, 21 de octubre de 2013

    Conjetura: si p es un primo impar, entonces a ((p ^ 3-1) / 2) = p * a ((p ^ 2-1) / 2). Porque de lo contrario a ((p ^ 3-1) / 2) & lt p * a ((p ^ 2-1) / 2) iff a ((p ^ 3-1) / 2) = a ((p-1) / 2) para un primo p. Equivalentemente p ^ 3 divide 2 ^ (p-1) -1, pero no se conoce tal primo p. - Thomas Ordowski, 10 de febrero de 2014

    Una generalización de la conjetura anterior: para cada k & gt = 2, si p es un primo impar, entonces a (((p ^ (k + 1)) - 1) / 2) = p * a ((p ^ k-1) / 2). Las pruebas informáticas de esta conjetura generalizada muestran que no existe un contraejemplo para k y p hasta 1000. - Ahmad J. Masad, 17 de octubre de 2020

    E. Bach y Jeffrey Shallit, Teoría algorítmica de números, I.

    T. Folger, "Shuffling Into Hyperspace", Discover, 1991 (vol. 12, no 1), páginas 66-67.

    M. Gardner, & quotCard Shuffles & quot, Mathematical Carnival capítulo 10, páginas 123-138. Nueva York: Vintage Books, 1977.

    L. Lunelli y M. Lunelli, Tavola di congruenza a ^ n == 1 mod K per a = 2,5,10, Atti Sem. Estera. Fis. Univ. Modena 10 (1960/61), 219-236 (1961).

    J. H. Silverman, Una introducción amistosa a la teoría de números, 3ª ed., Pearson Education, Inc, 2006, p. 146, ejerc. 21,3

    N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (incluye esta secuencia).

    M. Baake, U. Grimm, J. Nilsson, Escala de la medida de difracción de Thue-Morse, preprint arXiv arXiv: 1311.4371 [math-ph], 2013.

    Brillhart, John Lomont, J. S. Morton, Patrick. Propiedades ciclotómicas de los polinomios de Rudin-Shapiro, J. Reine Angew. Matemáticas 288 (1976), 37--65. Consulte la Tabla 2. MR0498479 (58 # 16589).

    Steve Butler, Persi Diaconis y R. L. Graham, Las matemáticas del cambio de rumbo y la herradura, arXiv: 1412.8533 [math.CO], 2014.

    Steve Butler, Persi Diaconis y R. L. Graham, Las matemáticas del cambio de sentido y la herradura, The American Mathematical Monthly 123.6 (2016): 542-556.

    A. J. C. Cunningham, Sobre fracciones binales, Matemáticas. Gaz., 4 (71) (1908), circa p. 266.

    P. Diaconis, R. L. Graham, W. M. Kantor, Las matemáticas de la mezcla perfecta, Adv. Apl. Matemáticas. 4 (2) (1983) 175-196

    M. J. Gardner y C. A. McMahan, Cheques de casino Riffling, Matemáticas. Mag., 50 (1) (1977), 38-41.

    V. I. Levenshtein, Códigos para evitar conflictos y sistemas triples cíclicos [en ruso], Problemy Peredachi Informatsii, 43 (núm. 3, 2007), 39-53.

    V. I. Levenshtein, Códigos para evitar conflictos y sistemas triples cíclicos, Problemas de transmisión de información, septiembre de 2007, Volumen 43, Número 3, págs. 199-212 (traducido del ruso)

    Yuan-Hsun Lo, Kenneth W. Shum, Wing Shing Wong, Yijin Zhang, Códigos de pesos tres y cuatro para evitar conflictos multicanal, arXiv: 2009.11754 [cs.IT], 2020.

    Jarkko Peltomäki y Aleksi Saarela, Palabras estándar y soluciones de la ecuación de palabras X_1 ^ 2. X_n ^ 2 = (X_1. X_n) ^ 2, Revista de teoría combinatoria, Serie A (2021) Vol. 178, 105340. Véase también arXiv: 2004.14657 [cs.FL], 2020.

    Vladimir Shevelev, Gilberto García-Pulgarin, Juan Miguel Velasquez-Soto y John H. Castillo, Overpseudoprimes, y números de Mersenne y Fermat como números primos, arXiv preprint arXiv: 1206: 0606 [math.NT], 2012.

    V. Shevelev, G. García-Pulgarin, J. M. Velásquez y J. H. Castillo, Overpseudoprimes, y Mersenne y Fermat Numbers as Primover Numbers, J. Integer Seq. 15 (2012) Artículo 12.7.7

    El mundo de las matemáticas de Eric Weisstein, Riffle Shuffle

    El mundo de las matemáticas de Eric Weisstein, In-Shuffle

    El mundo de las matemáticas de Eric Weisstein, Out-Shuffle

    El mundo de las matemáticas de Eric Weisstein, orden multiplicativo

    a ((b (n) -1) / 2) = n para n impar y n par tal que b (n / 2)! = b (n), donde b (n) = A005420 (n). - Thomas Ordowski, 11 de enero de 2014

    Tenga en cuenta que a (2 ^ n-1) = n + 1 y a (2 ^ n) = 2 * (n + 1). - Thomas Ordowski, 16 de enero de 2014

    Nuestro algoritmo para el cálculo de a (n) en el comentario del autor en A179680 (ver también el programa Sage a continuación) podría representarse en forma de una & quot; fracción continua finita & quot. Por ejemplo, sea n = 8, 2 * n + 1 = 17. Tenemos

    a: = n - & gt `if` (n = 0, 1, numtheory: -order (2, 2 * n + 1)):

    (MAGMA) [1] cat [Modorder (2, 2 * n + 1): n en [1..72]] // Klaus Brockhaus, 03 de diciembre de 2008

    importar Data.List (findIndex)

    importar datos.

    findIndex ((== 0). (`mod` (2 * n + 1))) $ tail a000225_list

    [Mod (2, n) .multiplicative_order () para n en (0..145) si mcd (n, 2) == 1]

    # Algoritmo de Vladimir Shevelev como se describe en A179680 y se presenta en el Ejemplo.

    [A002326VS (n) para n en (0..72)] # (Fin)

    Cf. A024222, A006694 (número de cosets ciclotómicos).

    Cf. A014664 (orden de 2 mod n-ésimo primo).

    Cf. A001122 (números primos para los que 2 es una raíz primitiva).

    Cf. A216838 (números primos para los que 2 no es una raíz primitiva).

    Más términos de David W. Wilson, 13 de enero de 2000

    Última modificación el 4 de julio a las 16:03 EDT de 2021. Contiene 345745 secuencias. (Ejecutando en oeis4.)


    Preguntas similares

    1. ¿Qué expresión es equivalente a (-2) (a + 6)? A. -2a + 6 B. 2a + 12 C. -2a-12 *** D. -2a + 12 2. ¿A qué conjuntos de números reales pertenece el número -22? Elija todos los subconjuntos que correspondan. (Hay dos respuestas correctas) Números enteros

    Álgebra

    1. escribir una expresión algebraica para la frase de palabras: el cociente de r y 12 ar * 12 br / 12 **** cr-12 2. escribir una frase de palabras para la expresión algebraica: 2t - 9 a. Nueve menos que dos veces un número t ***** b. nueve menos que

    Verificación de matemáticas, gracias

    1. ¿Cuál de los siguientes números es un ejemplo de un número entero? 15 * 0,252525. . . 3/5 (fracción) Raíz cuadrada de 7 2. ¿Qué enunciado es falso? Cada entero es un número real. El número cero es un número racional. Cada

    Identifica todos los conjuntos a los que pertenece el número. Elija entre número racional, número irracional, número entero y número entero. 0.23333. A. rational number B. irrational number C. integer, rational number D. whole number, integer,

    identify all the sets to which the number belongs. choose from rational number, irrational number, whole number, and integer. 0.62478916532… A. rational number B.irrational number C.integer, rational number** D.whole number,

    Identify all sets to which the number 3 belongs A. Whole numbers, integers, rational numbers B. Rational numbers C. Integers, rational numbers D. Even numbers, whole numbers, integers, rational numbers I THINK IT'S A

    Álgebra

    Write the number 2.4 in the form , using integers, to show that it is a rational number

    Álgebra

    To Which subset of real numbers does the number 1/5 belong? A irrational numbers B rational numbers c whole numbers, integers, rational number***** d whole numbers, natural numbers, integers

    True or false 1.) The set of integers contains the set of rational numbers 2.)Every repeating decimal is a rational number 3.)Every square root is an irrational number 4.) the set of whole numbers contains the set of rational

    Álgebra

    To which subset of real numbers does the following number belong? square root of 7 A)rational numbers B)irrational numbers****** C)whole numbers, integers, rational numbers D)whole numbers, natural numbers, integers

    Álgebra

    Order the following numbers from least to greatest. √5, -0.1, (-5/3), 0.7, √2 a. 0.7, √2, (-5/3), √5, -0.1 b. √5, √2, 0.7, (-5/3), -0.1 c. (-5/3), -0.1, 0.7, √2, √5 ? D. -0.1, 0.7, √2, √5, (-5/3) To which

    Last questions Ms. Sue please for math

    1. To which subset(s) does the number √42 belong? Rational numbers Irrational numbers Whole numbers, integers, rational numbers While numbers, natural numbers, integers 2. Evaluate the following expression for the values given.


    5.1: The order of Integers and Primitive Roots - Mathematics

    Given a prime . The task is to count all the primitive roots of .
    A primitive root is an integer x (1 <= x < p) such that none of the integers x – 1, x 2 – 1, …., x p – 2 – 1 are divisible by pero x p – 1 – 1 is divisible by .
    Ejemplos:

    Aporte: P = 3
    Producción: 1
    The only primitive root modulo 3 is 2.
    Aporte: P = 5
    Producción: 2
    Primitive roots modulo 5 are 2 and 3.

    Approach: There is always at least one primitive root for all primes. So, using Eulers totient function we can say that f(p-1) is the required answer where f(n) is euler totient function.
    Below is the implementation of the above approach:


    Ver el vídeo: Matemáticas Fundamental I - Operatoria en Números Enteros (Septiembre 2021).