Métodos para resolver comparaciones de primer grado. Comparaciones de módulos

En n dan los mismos restos.

Formulaciones equivalentes: a y b comparable en módulo n si su diferencia a - b es divisible por n, o si a se puede representar como a = b + knorte , Dónde k- algún número entero. Por ejemplo: 32 y −10 son comparables módulo 7, ya que

La afirmación “a y b son comparables módulo n” se escribe como:

Propiedades de igualdad de módulo

La relación de comparación de módulo tiene las propiedades

Cualquier dos números enteros a Y b módulo 1 comparable.

Para que los números a Y b eran comparables en módulo norte, es necesario y suficiente que su diferencia sea divisible por norte.

Si los números y son comparables por pares en módulo norte, entonces sus sumas y , así como los productos y también son comparables en módulo norte.

si los numeros a Y b comparable en módulo norte, entonces sus grados a k Y b k también son comparables en módulo norte bajo cualquier naturaleza k.

si los numeros a Y b comparable en módulo norte, Y norte dividido por metro, Eso a Y b comparable en módulo metro.

Para que los números a Y b eran comparables en módulo norte, presentado en forma de su descomposición canónica en factores simples pag i

necesario y suficiente para

La relación de comparación es una relación de equivalencia y tiene muchas de las propiedades de las igualdades ordinarias. Por ejemplo, se pueden sumar y multiplicar: si

Sin embargo, las comparaciones, en general, no se pueden dividir entre sí ni por otros números. Ejemplo: , sin embargo, reduciendo por 2, obtenemos una comparación errónea: . Las reglas de abreviatura para las comparaciones son las siguientes.

Tampoco puede realizar operaciones de comparación si sus módulos no coinciden.

Otras propiedades:

Definiciones relacionadas

clases de deducción

El conjunto de todos los números comparables a a módulo norte llamado clase de deducción a módulo norte , y generalmente se denota [ a] norte o . Por tanto, la comparación es equivalente a la igualdad de clases de residuos. [a] norte = [b] norte .

Desde la comparación de módulos norte es una relación de equivalencia en el conjunto de números enteros, entonces el módulo de clases de residuos norte representar clases de equivalencia; su numero es igual norte. El conjunto de todas las clases de residuos módulo. norte denotado por o.

Las operaciones de suma y multiplicación inducen las operaciones correspondientes en el conjunto:

Con respecto a estas operaciones el conjunto es un anillo finito, y si norte simple - campo finito.

Sistemas de deducción

El sistema de residuos le permite realizar operaciones aritméticas con un conjunto finito de números sin ir más allá de sus límites. Sistema completo de deducciones. módulo n es cualquier conjunto de n enteros que sean incomparables módulo n. Por lo general, los residuos no negativos más pequeños se toman como un sistema completo de residuos módulo n.

o las deducciones más pequeñas absolutas que consisten en números

en caso de impar norte y numeros

en caso de incluso norte .

Resolver comparaciones

Comparaciones de primer grado.

En teoría de números, criptografía y otros campos de la ciencia, a menudo surge el problema de encontrar soluciones a comparaciones de primer grado de la forma:

Resolver dicha comparación comienza con el cálculo del mcd (a,m)=d. En este caso, son posibles 2 casos:

• Si b no es un múltiplo d, entonces la comparación no tiene soluciones.
• Si b múltiple d, entonces la comparación tiene un módulo de solución único metro / d, o, lo que es lo mismo, d soluciones de módulo metro. En este caso, como resultado de reducir la comparación original en d la comparación es:

Dónde a 1 = a / d , b 1 = b / d Y metro 1 = metro / d son números enteros y a 1 y metro 1 son relativamente primos. Por lo tanto el número a 1 se puede invertir en módulo metro 1, es decir, encontrar tal número C, que (en otras palabras, ). Ahora la solución se encuentra multiplicando la comparación resultante por C:

Cálculo práctico del valor. C se puede implementar de diferentes maneras: usando el teorema de Euler, el algoritmo de Euclides, la teoría de fracciones continuas (ver algoritmo), etc. En particular, el teorema de Euler le permite escribir el valor C como:

Ejemplo

Para comparar tenemos d= 2, entonces módulo 22 la comparación tiene dos soluciones. Reemplacemos 26 por 4, comparable a su módulo 22, y luego reduzcamos los 3 números por 2:

Como 2 es coprimo con módulo 11, podemos reducir los lados izquierdo y derecho en 2. Como resultado, obtenemos una solución módulo 11: , equivalente a dos soluciones módulo 22: .

Comparaciones de segundo grado.

Resolver comparaciones de segundo grado se reduce a descubrir si un número dado es un residuo cuadrático (usando la ley de reciprocidad cuadrática) y luego calcular el módulo de raíz cuadrada.

Historia

El teorema del resto chino, conocido desde hace muchos siglos, establece (en lenguaje matemático moderno) que el módulo del anillo residual, el producto de varios números coprimos es

Comparación con una desconocida X parece

Dónde . Si a norte no divisible por metro, así se llama grado comparaciones.

Por decisión la comparación es cualquier número entero X 0 , para cual

Si X 0 satisface la comparación, entonces, de acuerdo con la propiedad de 9 comparaciones, todos los números enteros comparables a X 0 módulo metro. Por lo tanto, todas las soluciones de comparación que pertenecen al mismo módulo de clase de residuo t, lo consideraremos como una solución. Así, la comparación tiene tantas soluciones como elementos del sistema completo de residuos que la satisfacen.

Las comparaciones cuyos conjuntos de soluciones coinciden se llaman equivalente.

2.2.1 Comparaciones de primer grado

Comparación de primer grado con una incógnita X parece

(2.2)

Teorema 2.4. Para que una comparación tenga al menos una solución, es necesario y suficiente que el número b dividido por MCD( a, metro).

Prueba. Primero demostramos la necesidad. Dejar d = MCD( a, metro) Y X 0 - solución de comparación. Entonces , es decir, la diferencia Oh 0 − b dividido por T. Entonces existe tal número entero q, Qué Oh 0 − b = qm. De aquí b= ah 0 − qm. Y desde d, como divisor común, divide números A Y T, luego el minuendo y el sustraendo se dividen por d, y por lo tanto b dividido por d.

Ahora demostremos la suficiencia. Dejar d- máximo común divisor de números A Y T, Y b dividido por d. Entonces, por definición de divisibilidad, existen los siguientes números enteros a 1 , b 1 ,t 1 , Qué .

Usando el algoritmo euclidiano extendido, encontramos una representación lineal del número 1 = mcd( a 1 , metro 1 ):

para algunos X 0 , y 0 . Multipliquemos ambos lados de la última igualdad por b 1 d:

o, lo que es lo mismo,

,

es decir, y es la solución a la comparación. □

Ejemplo 2.10. Comparación 9 X= 6 (mod 12) tiene solución ya que mcd(9, 12) = 3 y 6 es divisible por 3. □

Ejemplo 2.11. Comparación 6x= 9 (mod 12) no tiene soluciones, ya que mcd(6, 12) = 6 y 9 no es divisible por 6. □

Teorema 2.5. Sea la comparación (2.2) solucionable y d = MCD( a, metro). Entonces el conjunto de soluciones de comparación (2.2) consta de d clases de residuos de módulo T, es decir, si X 0 - una de las soluciones, entonces todas las demás soluciones son

Prueba. Dejar X 0 - solución de comparación (2.2), es decir Y , . Entonces existe tal cosa q, Qué Oh 0 − b = qm. Ahora sustituyendo en la última igualdad en lugar de X 0 una solución arbitraria de la forma, donde obtenemos la expresión

, Divisible por metro. □

Ejemplo 2.12. Comparación 9 X=6 (mod 12) tiene exactamente tres soluciones, ya que mcd(9, 12)=3. Estas soluciones: X 0 = 2, x 0 + 4 = 6, X 0 + 2∙4=10.□

Ejemplo 2.13. Comparación 11 X=2 (mod 15) tiene una solución única X 0 = 7, ya que MCD(11,15)=1.□

Le mostraremos cómo resolver comparaciones de primer grado. Sin pérdida de generalidad, asumiremos que MCD( a, t) = 1. Entonces se puede buscar la solución a la comparación (2.2), por ejemplo, utilizando el algoritmo euclidiano. De hecho, utilizando el algoritmo euclidiano extendido, representamos el número 1 como una combinación lineal de números. a Y t:

Multipliquemos ambos lados de esta igualdad por b, obtenemos: b = abq + mrb, dónde abq - b = - mrb, eso es a ∙ (bq) = b(modificación metro) Y bq- solución de comparación (2.2).

Otra solución es utilizar el teorema de Euler. Nuevamente creemos que MCD(a, t)= 1. Aplicamos el teorema de Euler: . Multiplica ambos lados de la comparación por b: . Reescribiendo la última expresión como , obtenemos que es una solución a la comparación (2.2).

Vamos ahora MCD( a, metro) = d>1. Entonces a = atd, metro = metrotd, donde MCD( A 1 , metro 1) = 1. Además, es necesario b = b 1 d, para que la comparación sea resoluble. Si X 0 - solución de comparación A 1 X = b 1 (modificación metro 1), y el único, ya que MCD( A 1 , metro 1) = 1, entonces X 0 será la solución y comparación A 1 xdd = base de datos 1 (modificación metro 1), es decir, la comparación original (2.2). Descansar d- 1 soluciones se encuentran mediante el teorema 2.5.

Introducción

§1. Comparación de módulos

§2. Propiedades de comparación

1. Propiedades de comparación independientes del módulo
2. Propiedades de comparaciones dependientes del módulo

§3. Sistema de deducción

1. Sistema completo de deducciones.
2. Sistema reducido de deducciones

§4. El teorema de Euler y Fermat

1. función de Euler
2. El teorema de Euler y Fermat

Capitulo 2. Teoría de las comparaciones con una variable.

§1. Conceptos básicos relacionados con la resolución de comparaciones.

1. Las raíces de las comparaciones
2. Equivalencia de comparaciones
3. teorema de wilson

§2. Comparaciones de primer grado y sus soluciones.

1. Método de selección
2. Los métodos de Euler.
3. Método del algoritmo de Euclides
4. Método de fracción continua

§3. Sistemas de comparaciones de 1er grado con una incógnita.

§4. División de comparaciones de grados superiores.

§5. Raíces e índices de antiderivadas

1. Orden de clase de deducción
2. Raíces primitivas módulo primo
3. Índices módulo primo

Capítulo 3. Aplicación de la teoría de las comparaciones.

§1. Signos de divisibilidad

§2. Comprobación de los resultados de operaciones aritméticas.

§3. Conversión de una fracción ordinaria a una fracción final

fracción sistemática decimal

Conclusión

Literatura

Introducción

En nuestras vidas a menudo tenemos que lidiar con números enteros y problemas relacionados con ellos. En esta tesis considero la teoría de la comparación de números enteros.

Dos números enteros cuya diferencia es múltiplo de un número natural dado metro se llaman comparables en módulo metro.

La palabra "módulo" proviene del latín módulo, que en ruso significa "medida", "magnitud".

La afirmación “a es comparable a b módulo m” generalmente se escribe comob (mod m) y se llama comparación.

La definición de comparación fue formulada en el libro de K. Gauss "Estudios aritméticos". Esta obra, escrita en latín, comenzó a imprimirse en 1797, pero el libro no se publicó hasta 1801 debido a que el proceso de impresión en ese momento era extremadamente laborioso y largo. La primera sección del libro de Gauss se titula: "Sobre la comparación de números en general".

Las comparaciones son muy convenientes de usar en los casos en que en algunos estudios es suficiente conocer números exactos a múltiplos de un determinado número.

Por ejemplo, si nos interesa saber en qué dígito termina el cubo de un número entero a, entonces nos basta con saber a solo hasta múltiplos de 10 y podemos usar comparaciones módulo 10.

El propósito de este trabajo es considerar la teoría de las comparaciones y estudiar los métodos básicos para resolver comparaciones con incógnitas, así como estudiar la aplicación de la teoría de las comparaciones a las matemáticas escolares.

La tesis consta de tres capítulos, cada capítulo dividido en párrafos y párrafos en párrafos.

El primer capítulo describe cuestiones generales de la teoría de las comparaciones. Aquí consideramos el concepto de comparación de módulos, las propiedades de las comparaciones, el sistema completo y reducido de residuos, la función de Euler, el teorema de Euler y Fermat.

El segundo capítulo está dedicado a la teoría de las comparaciones con lo desconocido. Describe los conceptos básicos asociados con la resolución de comparaciones, considera métodos para resolver comparaciones de primer grado (método de selección, método de Euler, método del algoritmo euclidiano, método de fracciones continuas, uso de índices), sistemas de comparaciones de primer grado. con una incógnita, comparaciones de grados superiores, etc.

El tercer capítulo contiene algunas aplicaciones de la teoría de números a las matemáticas escolares. Se consideran los signos de divisibilidad, la verificación de los resultados de las acciones y la conversión de fracciones ordinarias en fracciones decimales sistemáticas.

La presentación del material teórico va acompañada de una gran cantidad de ejemplos que revelan la esencia de los conceptos y definiciones introducidos.

Capítulo 1. Cuestiones generales de la teoría de las comparaciones.

§1. Comparación de módulos

Sea z el anillo de los números enteros, m un número entero fijo y m·z el conjunto de todos los números enteros que son múltiplos de m.

Definición 1. Se dice que dos números enteros a y b son comparables módulo m si m divide a-b.

Si los números a y b son comparables módulo m, entonces escribe a b (mód m).

Condición a b (mod m) significa que a-b es divisible por m.

a b (mod m)↔(a-b) m

Definamos que la relación de comparabilidad módulo m coincide con la relación de comparabilidad módulo (-m) (la divisibilidad por m equivale a la divisibilidad por –m). Por tanto, sin pérdida de generalidad, podemos suponer que m>0.

Ejemplos.

Teorema. (un signo de comparabilidad de los números espirituales módulo m): Dos números enteros a y b son comparables módulo m si y sólo si a y b tienen los mismos restos cuando se dividen por m.

Prueba.

Sean iguales los restos al dividir a y b por m, es decir, a=mq₁+r,(1)

B=mq₂+r, (2)

Donde 0≤r≥m.

Reste (2) de (1), obtenemos a-b= m(q₁- q₂), es decir, a-b m o a b (mod m).

Por el contrario, dejemos que un b (mód m). Esto significa que a-b m o a-b=mt, t z (3)

Divida b por m; obtenemos b=mq+r en (3), tendremos a=m(q+t)+r, es decir, al dividir a entre m se obtiene el mismo resto que al dividir b entre m.

Ejemplos.

5=4·(-2)+3

23=4·5+3

24=3·8+0

10=3·3+1

Definición 2. Dos o más números que dan restos idénticos cuando se dividen por m se denominan restos iguales o módulo comparable m.

Ejemplos.

Tenemos: 2m+1-(m+1)²= 2m+1 - m²-2m-1=- m², y (- m²) se divide entre m => nuestra comparación es correcta.

1. Demuestre que las siguientes comparaciones son falsas:

Si los números son comparables módulo m, entonces tienen el mismo mcd.

Tenemos: 4=2·2, 10=2·5, 25=5·5

MCD(4,10) = 2, MCD(25,10) = 5, por lo tanto nuestra comparación es incorrecta.

§2. Propiedades de comparación

1. Propiedades de comparaciones independientes del módulo.

Muchas propiedades de las comparaciones son similares a las propiedades de las igualdades.

a) reflexividad: aa (mod m) (cualquier número entero a comparable a sí mismo módulo m);

B) simetría: si un b (mod m), luego b a (mod m);

C) transitividad: si un b (mod m), y b con (mod m), luego a con (mod m).

Prueba.

Por condición m/(a-b) y m/ (c-d). Por lo tanto, m/(a-b)+(c-d), m/(a+c)-(b+d) => a+c b+d (mod m).

Ejemplos.

Encuentra el resto al dividir a las 13.

Solución: -1 (mod 13) y 1 (mod 13), luego (-1)+1 0 (mod 13), es decir, el resto de la división por 13 es 0.

a-c b-d (mod m).

Prueba.

Por condición m/(a-b) y m/(c-d). Por lo tanto, m/(a-b)-(c-d), m/(a-c)-(b-d) => (a-c) bd (mod m).

1. (una consecuencia de las propiedades 1, 2, 3). Puedes sumar el mismo número entero a ambos lados de la comparación.

Prueba.

deja un b (mod m) y k es cualquier número entero. Por la propiedad de la reflexividad.

k=k (mod m), y según las propiedades 2 y 3 tenemos a+k b+k (mod m).

a·c·d (mod m).

Prueba.

Por condición, a-b є mz, c-d є mz. Por lo tanto a·c-b·d = (a·c - b·c)+(b·c- b·d)=(a-b)·c+b·(c-d) є mz, es decir, a·c·d (mód m).

Consecuencia. Ambos lados de la comparación se pueden elevar a la misma potencia entera no negativa: si unb (mod m) y s es un número entero no negativo, entonces a s b s (mod m).

Ejemplos.

Solución: obviamente 13 1 (mod 3)

2 -1 (módulo 3)

5-1 (mod 3), entonces

- · 1-1 0 (mod 13)

Respuesta: el resto requerido es cero y A es divisible por 3.

Solución:

Demostremos que 1+ 0(mod13) o 1+ 0(mod 13)

1+ =1+ 1+ =

Desde 27 1 (mod 13), luego 1+ 1+1·3+1·9 (mod 13).

etc.

3. Encuentra el resto al dividir con el resto de un número a los 24.

Tenemos: 1 (mod 24), entonces

1 (mod 24)

Sumando 55 a ambos lados de la comparación, obtenemos:

(mod. 24).

Tenemos: (mod 24), por lo tanto

(mod 24) para cualquier k є N.

Por eso (mod. 24). Desde (-8)16 (mod 24), el resto requerido es 16.

1. Ambos lados de la comparación se pueden multiplicar por el mismo número entero.

2.Propiedades de las comparaciones según el módulo.

Prueba.

Desde a b (mod t), entonces (a - b) t y desde t n , entonces debido a la transitividad de la relación de divisibilidad(a - b n), es decir, a b (mod n).

Ejemplo.

Calcula el resto de dividir 196 entre 7.

Solución:

Sabiendo que 196= , podemos escribir 196(mod. 14). Usemos la propiedad anterior, 14 7, obtenemos 196 (mod 7), es decir, 196 7.

1. Ambos lados de la comparación y el módulo se pueden multiplicar por el mismo número entero positivo.

Prueba.

Sea a b (mod t ) yc es un número entero positivo. Entonces a-b = mt y ac-bc=mtc, o ac antes de Cristo (mod mc).

Ejemplo.

Determinar si el valor de una expresión es un número entero.

Solución:

Representemos fracciones en forma de comparaciones: 4(mod 3)

1 (módulo 9)

31 (mod 27)

Sumemos estas comparaciones término por término (propiedad 2), obtenemos 124(mod 27) Vemos que 124 no es un número entero divisible por 27, de ahí el significado de la expresióntampoco es un número entero.

1. Ambos lados de la comparación se pueden dividir por su factor común si es coprimo con respecto al módulo.

Prueba.

si ca cb (mod m), es decir, m/c(a-b) y el número Con coprimo a m, (c,m)=1, entonces m divide a-b. Por eso, a b (mod t).

Ejemplo.

60 9 (mod 17), después de dividir ambos lados de la comparación por 3 obtenemos:

20 (mod. 17).

En general, es imposible dividir ambos lados de una comparación por un número que no sea coprimo con respecto al módulo, ya que después de la división se pueden obtener números incomparables con respecto a un módulo dado.

Ejemplo.

8 (mod 4), sino 2 (mod 4).

1. Ambos lados de la comparación y el módulo se pueden dividir por su divisor común.

Prueba.

si ka kb (mod km), luego k (a-b) se divide por km. Por lo tanto, a-b es divisible por m, es decir a b (mod t).

Prueba.

Sea P (x) = c 0 x n + c 1 x n-1 + ... + c n-1 x+ c n. Por condición a b (mod t), entonces

akbk (mod m) para k = 0, 1, 2,…,n. Multiplicando ambos lados de cada una de las n+1 comparaciones resultantes por c n-k, obtenemos:

c n-k a k c n-k b k (mod m), donde k = 0, 1, 2,…,n.

Sumando las últimas comparaciones obtenemos: P (a) P (b) (mód m). Si a (mod m) y c i d i (mod m), 0 ≤ i ≤n, entonces

(mod m). Por lo tanto, en comparación con el módulo m, los términos y factores individuales se pueden reemplazar por números comparables con el módulo m.

Al mismo tiempo, se debe prestar atención al hecho de que los exponentes encontrados en las comparaciones no se pueden reemplazar de esta manera: desde

a n c(mod m) y n k(mod m) no se sigue que a ks (mod m).

La Propiedad 11 tiene varias aplicaciones importantes. En particular, con su ayuda es posible dar una justificación teórica de los signos de divisibilidad. Para ilustrar, como ejemplo, daremos la derivación de la prueba de divisibilidad por 3.

Ejemplo.

Todo número natural N se puede representar como un número sistemático: N = a 0 10 norte + un 1 10 norte-1 + ... + un norte-1 10 + un norte .

Considere el polinomio f(x) = a 0 x n + a 1 x n-1 + ... + a n-1 x+a n . Porque

10 1 (mod 3), luego por propiedad 10 f (10) f(1) (mod 3) o

N = a 0 10 n + a 1 10 n-1 + ... + a n-1 10 + a n a 1 + a 2 +…+ a n-1 + a n (mod 3), es decir, para que N sea divisible por 3, es necesario y suficiente que la suma de las cifras de este número sea divisible por 3.

§3. Sistemas de deducción

1. Sistema completo de deducciones.

Los números restantes iguales o, lo que es lo mismo, módulos comparables m, forman una clase de números módulo m.

De esta definición se deduce que todos los números de la clase corresponden al mismo resto r, y obtenemos todos los números de la clase si, en la forma mq+r, hacemos que q recorra todos los números enteros.

En consecuencia, con m valores diferentes de r, tenemos m clases de números módulo m.

Cualquier número de una clase se llama módulo residual m con respecto a todos los números de la misma clase. El residuo obtenido en q=0, igual al resto r, se denomina residuo no negativo más pequeño.

El residuo ρ, el más pequeño en valor absoluto, se llama residuo absolutamente más pequeño.

Obviamente, para r tenemos ρ=r; en r> tenemos ρ=r-m; finalmente, si m es par y r=, entonces cualquiera de los dos números se puede tomar como ρ y -m= - .

Elijamos de cada clase de módulo de residuos. t un número a la vez. Obtenemos t enteros: x 1,…, x m. El conjunto (x 1,…, x t) se llama sistema completo de deducciones módulo m.

Dado que cada clase contiene un número infinito de residuos, es posible componer un número infinito de sistemas completos diferentes de residuos para un módulo m dado, cada uno de los cuales contiene t deducciones.

Ejemplo.

Compile varios sistemas completos de deducciones de módulo. t = 5. Tenemos clases: 0, 1, 2, 3, 4.

0 = {... -10, -5,0, 5, 10,…}

1= {... -9, -4, 1, 6, 11,…}

Creemos varios sistemas completos de deducciones, tomando una deducción de cada clase:

0, 1, 2, 3, 4

5, 6, 2, 8, 9

10, -9, -8, -7, -6

5, -4, -3, -2, -1

etc.

Los más comunes:

1. Sistema completo de residuos mínimos no negativos: 0, 1, t-1 En el ejemplo anterior: 0, 1, 2, 3, 4. Este sistema de residuos es sencillo de crear: debes anotar todos los residuos no negativos obtenidos al dividir por m.
2. Sistema completo de residuos menos positivos.(la deducción positiva más pequeña se toma de cada clase):

1, 2,…, metro. En nuestro ejemplo: 1, 2, 3, 4, 5.

1. Un sistema completo de deducciones absolutamente mínimas.En el caso de m impar, los residuos más pequeños absolutos se representan uno al lado del otro.

- ,…, -1, 0, 1,…, ,

y en el caso de m par, una de las dos filas

1, …, -1, 0, 1,…, ,

, …, -1, 0, 1, …, .

En el ejemplo dado: -2, -1, 0, 1, 2.

Consideremos ahora las propiedades básicas del sistema completo de residuos.

Teorema 1 . Cualquier colección de m enteros:

x l ,x 2 ,…,x m (1)

módulo m incomparable por pares, forma un sistema completo de residuos módulo m.

Prueba.

1. Cada uno de los números de la colección (1) pertenece a una determinada clase.
2. Dos números cualesquiera x i y x j de (1) son incomparables entre sí, es decir, pertenecen a clases diferentes.
3. Hay m números en (1), es decir, el mismo número que clases de módulo T.

x 1, x 2,…, x t - sistema completo de deducciones módulo m.

Teorema 2. Sea (a, m) = 1, b - entero arbitrario; Entonces sí x 1, x 2,…, x t es un sistema completo de residuos módulo m, entonces la colección de números ax 1 + b, hacha 2 + b,…, hacha m + b es también un sistema completo de residuos módulo m.

Prueba.

Consideremos

Hacha 1 + b, hacha 2 + b,…, hacha m + b (2)

1. Cada uno de los números de la colección (2) pertenece a una determinada clase.
2. Dos números cualesquiera ax i +b y ax j + b de (2) son incomparables entre sí, es decir, pertenecen a clases diferentes.

De hecho, si en (2) hubiera dos números tales que

hacha i +b hacha j + b (mod m), (i = j), entonces obtendríamos eje i eje j (mod t). Dado que (a,t) = 1, entonces la propiedad de las comparaciones puede reducir ambas partes de la comparación en A . Obtenemos x i x j (mod m).

Por condición x i x j (mod t) en (i = j), ya que x 1, x 2, ..., xm - un sistema completo de deducciones.

1. El conjunto de números (2) contiene t números, es decir, tantas como clases haya módulo m.

Entonces, ax 1 + b, ax 2 + b,..., ax m + b - sistema completo de residuos módulo m.

Ejemplo.

Sea m = 10, a = 3, b = 4.

Tomemos algún sistema completo de residuos módulo 10, por ejemplo: 0, 1, 2,…, 9. Compongamos números de la forma hacha + b. Obtenemos: 4, 7, 10, 13, 16, 19, 22, 25, 28, 31. El conjunto de números resultante es un sistema completo de residuos módulo 10.

1. El sistema de deducciones dado.

Demostremos el siguiente teorema.

Teorema 1.

Los números de la misma clase de residuo módulo m tienen el mismo máximo común divisor con m: si un segundo (mod m), entonces (a, m) = (b, m).

Prueba.

Sea a b (mod m). Entonces a = b +mt, donde t є z. De esta igualdad se deduce que (a, t) = (b,t).

De hecho, sea δ un divisor común de a y m, entonces aδ, m δ. Como a = b +mt, entonces b=a-mt, por lo tanto bδ. Por tanto, cualquier divisor común de los números a y m es divisor común de my b.

Por el contrario, si m δ y b δ, entonces a = b +mt es divisible por δ y, por lo tanto, cualquier divisor común de myb es un divisor común de ay m. El teorema ha sido demostrado.

Definición 1. Máximo divisor de módulo común t y cualquier número a de esta clase de deducciones por t llamado el máximo común divisor t y esta clase de deducciones.

Definición 2. Clase de residuo a módulo t llamado coprimo al módulo metro , si el máximo común divisor a y t es igual a 1 (es decir, si m y cualquier número de a son coprimos).

Ejemplo.

deja t = 6. La clase de residuo 2 se compone de los números (..., -10, -4, 2, 8, 14, ...). El máximo común divisor de cualquiera de estos números y módulo 6 es 2. Por lo tanto, (2, 6) = 2. El máximo común divisor de cualquier número de clase 5 y módulo 6 es 1. Por lo tanto, la clase 5 es coprima con respecto al módulo 6 .

Elijamos un número de cada clase de residuos que sea coprimo con módulo m. Obtenemos un sistema de deducciones que forma parte del sistema completo de deducciones. la llamansistema reducido de residuos módulo m.

Definición 3. Un conjunto de residuos módulo m, tomado uno de cada coprimo con t La clase de residuos para este módulo se denomina sistema reducido de residuos.

De la Definición 3 se sigue un método para obtener el sistema reducido de residuos de módulo T: es necesario anotar algún sistema completo de residuos y eliminar de él todos los residuos que no sean coprimos con m. El resto del conjunto de deducciones es el sistema reducido de deducciones. Evidentemente, se puede componer un número infinito de sistemas de residuos módulo m.

Si tomamos como sistema inicial el sistema completo de residuos mínimos no negativos o absolutamente mínimos, entonces usando el método indicado obtenemos, respectivamente, un sistema reducido de residuos mínimos no negativos o absolutamente mínimos módulo m.

Ejemplo.

Si t = 8, entonces 1, 3, 5, 7 es el sistema reducido de residuos no negativos mínimos, 1, 3, -3, -1- el sistema reducido de deducciones absolutamente mínimas.

Teorema 2.

Dejar el número de clases coprimas de m es igual a k.Entonces cualquier colección de k enteros

módulo incomparable m por pares y coprimo a m, es un sistema reducido de residuos módulo m.

Prueba

A) Cada número de la población (1) pertenece a una determinada clase.

1. Todos los números de (1) son incomparables en módulo por pares T, es decir, pertenecen a diferentes clases módulo m.
2. Cada número de (1) es coprimo con T, es decir, todos estos números pertenecen a diferentes clases coprimos al módulo m.
3. Total (1) disponible k números, es decir, tantos como debe contener el sistema reducido de residuos módulo m.

Por tanto, el conjunto de números(1) - sistema reducido de deducciones de módulo T.

§4. Función de Euler.

Teoremas de Euler y Fermat.

1. Función de Euler.

Denotemos por φ(t) el número de clases de residuos módulo m coprimo a m, es decir, el número de elementos del sistema reducido de residuos módulo t.Función φ (t) es numérico. la llamanFunción de Euler.

Elijamos como representantes de las clases de residuos de módulo. t números 1, ..., t - 1, t. Entonces φ (t) - el número de tales números coprimos con t. En otras palabras, φ (t) - el número de números positivos que no exceden m y son primos relativos con respecto a m.

Ejemplos.

1. deja t = 9. El sistema completo de residuos módulo 9 consta de los números 1, 2, 3, 4, 5, 6, 7, 8, 9. De estos, los números 1,2,4, 5, 7, 8 son coprimos a 9. Entonces, dado que el número de estos números es 6, entonces φ (9) = 6.
2. Sea t = 12. El sistema completo de residuos consta de los números 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12. De estos, los números 1, 5, 7, 11 son coprimos de 12. . Esto significa

φ(12) = 4.

en t = 1, el sistema completo de residuos consta de una clase 1. El divisor natural común de los números 1 y 1 es 1, (1, 1) = 1. Sobre esta base, asumimos φ(1) = 1.

Pasemos al cálculo de la función de Euler.

1) Si t = p es un número primo, entonces φ(p) = p-1.

Prueba.

Deducciones 1, 2, ..., p- 1 y solo ellos son primos relativos con un número primo r. Por lo tanto φ (р) = р - 1.

2) Si t = pk - primer poder p, entonces

φ(t) = (pag - 1) . (1)

Prueba.

Sistema completo de deducciones en módulo. t = p k consta de los números 1,..., pag k - 1, pag k Divisores naturales t son grados r. Por lo tanto el número Apuede tener un divisor común con m distinto de 1, sólo en el caso cuandoAdividido porr.Pero entre los números 1, ... , pagk -1 enRsolo los numeros son divisiblesp, 2p, ... , p2 , ... RA, cuyo número es igualRA: p = pk-1. Esto significa que son coprimos cont = pagAdescansarRA-Rk-1=pk-l(p-1)números. Esto prueba que

φ (RA) = pagk-1(pág-1).

Teorema1.

La función de Euler es multiplicativa, es decir, para números primos relativos m y n tenemos φ (mn) = φ(m) φ (n).

Prueba.

El primer requisito en la definición de una función multiplicativa se cumple de forma trivial: la función de Euler está definida para todos los números naturales, y φ (1) = 1. Sólo necesitamos demostrar que sitiponúmeros coprimos, entonces

φ (tp)= φ (t) φ (PAG).(2)

Dispongamos el sistema completo de deducciones módulo.tpcomoPAGXT-matrices

1 2 t

t+1 t+2 2 toneladas

………………………………

(PAG -1) t+1 (PAG -1) m+2 Vie

Porque eltYPAGson primos relativos, entonces el númeroXrecíprocamente solo contpentonces y sólo cuandoXrecíprocamente solo contYXrecíprocamente solo conPAG. pero el numerokilómetros+trecíprocamente solo contsi y solo sitrecíprocamente solo conT.Por lo tanto, los números coprimos con m se ubican en aquellas columnas para las cualestpasa por el sistema reducido de residuos de móduloT.El número de tales columnas es igual a φ(T).Cada columna presenta el sistema completo de deducciones móduloPAG.De estas deducciones φ(PAG)coprime conPAG.Esto significa que el número total de números que son primos relativos y conty con n, igual a φ(t)φ(norte)

(φ (t)columnas, en cada una de las cuales se toma φ(PAG)números). Estos números, y sólo ellos, son coprimos con respecto aetc.Esto prueba que

φ (tp)= φ (t) φ (PAG).

Ejemplos.

№1 . Demostrar la validez de las siguientes igualdades.

φ(4norte) =

Prueba.

№2 . Resuelve la ecuación

Solución:porque(metro)=, Eso= , eso es=600, =75, =3·, entonces x-1=1, x=2,

y-1=2, y=3

Respuesta: x=2, y=3

Podemos calcular el valor de la función de Euler.(m), conociendo la representación canónica del número m:

m=.

Debido a la multiplicatividad(m) tenemos:

(metro)=.

Pero según la fórmula (1) encontramos que

-1), y por lo tanto

(3)

La igualdad (3) se puede reescribir como:

Porque el=m, entonces(4)

La fórmula (3) o, lo que es lo mismo, (4) es la que buscamos.

Ejemplos.

№1 . ¿Cual es la cantidad?

Solución:,

, =18 (1- ) (1- =18 , Entonces= 1+1+2+2+6+6=18.

№2 . Con base en las propiedades de la función numérica de Euler, demuestre que en la secuencia de números naturales existe un conjunto infinito de números primos.

Solución:Suponiendo que el número de números primos es un conjunto finito, asumimos que- el número primo más grande y sea a=es el producto de todos los números primos, según una de las propiedades de la función del número de Euler

Desde a≥, entonces a es un número compuesto, pero dado que su representación canónica contiene todos los números primos, entonces=1. Tenemos:

=1 ,

lo cual es imposible, y así se demuestra que el conjunto de los números primos es infinito.

№3 .Resuelve la ecuación, donde x=Y=2.

Solución:Usamos la propiedad de la función numérica de Euler,

,

y por condición=2.

Expresemos desde=2 , obtenemos, sustituir en

:

(1+ -1=120, =11 =>

Entonces x=, x=11·13=143.

Respuesta:x= 143

2. Teorema de Euler y Fermat.

El teorema de Euler juega un papel importante en la teoría de las comparaciones.

Teorema de Euler.

Si un número entero a es coprimo con m, entonces

(1)

Prueba.Dejar

(2)

hay un sistema reducido de residuos módulo m.

Siaes un número entero coprimo para m, entonces

(3)

Módulo de comparación de números

Preparado por: Irina Zutikova

MAOU "Liceo No. 6"

Clase: 10 "a"

Supervisora ​​científica: Zheltova Olga Nikolaevna

Tambov

2016

• Problema
• Objetivo del proyecto
• Hipótesis
• Objetivos del proyecto y plan para alcanzarlos.
• Comparaciones y sus propiedades.
• Ejemplos de problemas y sus soluciones.
• Sitios y literatura usados.

Problema:

La mayoría de los estudiantes rara vez utilizan la comparación de módulos de números para resolver tareas olímpicas y no estándar.

Objetivo del proyecto:

Muestre cómo puede resolver tareas olímpicas y no estándar comparando módulos de números.

Hipótesis:

Un estudio más profundo del tema "Módulo de comparación de números" ayudará a los estudiantes a resolver algunas tareas olímpicas y no estándar.

Objetivos del proyecto y plan para alcanzarlos:

1. Estudie en detalle el tema “Comparación de módulos de números”.

2. Resuelva varias tareas olímpicas y no estándar utilizando la comparación de números en módulo.

3.Cree una nota para los estudiantes sobre el tema “Comparación de módulos de números”.

4. Realice una lección sobre el tema "Comparación de módulos de números" en el grado 10a.

5.Entregue a la clase tarea sobre el tema “Comparación por módulo”.

6.Compare el tiempo para completar la tarea antes y después de estudiar el tema “Comparación por módulo”.

7.Sacar conclusiones.

Antes de comenzar a estudiar en detalle el tema "Comparación de módulos de números", decidí comparar cómo se presenta en varios libros de texto.

• Álgebra e inicio del análisis matemático. Nivel avanzado. Décimo grado (Yu.M. Kolyagin y otros)
• Matemáticas: álgebra, funciones, análisis de datos. 7mo grado (L.G. Peterson y otros)
• Álgebra e inicio del análisis matemático. Nivel de perfil. 10° grado (E.P. Nelin y otros)
• Álgebra e inicio del análisis matemático. Nivel de perfil. Décimo grado (G.K. Muravin y otros)

Según descubrí, algunos libros de texto ni siquiera tocan este tema, a pesar del nivel avanzado. Y el tema se presenta de la manera más clara y accesible en el libro de texto de L.G. Peterson (Capítulo: Introducción a la teoría de la divisibilidad), así que intentemos comprender la "Comparación de módulos de números", basándonos en la teoría de este libro de texto.

Comparaciones y sus propiedades.

Definición: Si dos números enteros a y b tienen los mismos restos cuando se dividen por algún número entero m (m>0), entonces se dice quea y b son comparables módulo m, y escribe:

Teorema: si y sólo si la diferencia de a y b es divisible por m.

Propiedades:

1. Reflexividad de las comparaciones.Cualquier número a es comparable consigo mismo módulo m (m>0; a,m son números enteros).
2. Comparaciones simétricas.Si el número a es comparable al número b módulo m, entonces el número b es comparable al número a módulo igual (m>0; a,b,m son números enteros).
3. Transitividad de las comparaciones.Si el número a es comparable al número b módulo m, y el número b es comparable al número c módulo el mismo módulo, entonces el número a es comparable al número c módulo m (m>0; a,b,c , m son números enteros).
4. Si el número a es comparable al número b módulo m, entonces el número a norte comparable por el número b norte módulo m(m>0; a,b,m-enteros; n-número natural).

Ejemplos de problemas y sus soluciones.

1. Encuentra el último dígito del número 3. 999 .

Solución:

Porque El último dígito del número es el resto cuando se divide por 10, entonces

3 999 =3 3 *3 996 =3 3 *(3 4 ) 249 =7*81 249 7(mod 10)

(Porque 34=81 1(mod 10);81 n 1(mod10) (por propiedad))

Respuesta: 7.

2.Demuestra que 2 4n -1 es divisible por 15 sin resto. (Phystech2012)

Solución:

Porque 16 1 (mod 15), entonces

16n-1 0(mod 15) (por propiedad); 16n= (2 4) norte

2 4n -1 0(mod 15)

3.Demuestra que 12 2n+1 +11n+2 Divisible por 133 sin resto.

Solución:

12 2n+1 =12*144n 12*11n (mod 133) (por propiedad)

12 2n+1 +11 n+2 =12*11 n +11 n *121=11 n *(12+121) =11 n *133

Número (11 norte *133)se divide sin resto entre 133. Por lo tanto, (12 2n+1 +11n+2 ) es divisible por 133 sin resto.

4. Encuentra el resto del número 2 dividido por 15. 2015 .

Solución:

Desde 16 1(mod 15), entonces

2 2015 8 (mod 15)

Respuesta: 8.

5.Encuentra el resto de la división por el 17 número 2 2015. (Phystech2015)

Solución:

2 2015 =2 3 *2 2012 =8*16 503

Desde 16 -1(mod 17), entonces

2 2015 -8 (mod 15)

8 9 (mod 17)

Respuesta: 9.

6.Demuestra que el número es 11. 100 -1 es divisible por 100 sin resto. (Phystech2015)

Solución:

11 100 =121 50

121 50 21 50 (mod 100) (por propiedad)

21 50 =441 25

441 25 41 25 (mod 100) (por propiedad)

41 25 =41*1681 12

1681 12 (-19) 12 (mod 100) (por propiedad)

41*(-19) 12 =41*361 6

361 6 (-39) 6 (mod 100)(por propiedad)

41*(-39) 6 =41*1521 3

1521 3 21 3 (mod100) (por propiedad)

41*21 3 =41*21*441

441 41(mod 100) (por propiedad)

21*41 2 =21*1681

1681 -19(mod 100) (por propiedad)

21*(-19)=-399

399 1(mod 100) (por propiedad)

Entonces 11 100 1 (mod 100)

11 100 -1 0(mod 100) (por propiedad)

7. Se dan tres números: 1771,1935,2222. Encuentre un número tal que, al dividirlo, los restos de los tres números dados sean iguales. (HSE2016)

Solución:

Sea el número desconocido igual a a, entonces

2222 1935 (mod a); 1935 1771 (mod a); 2222 1771 (mod a)

2222-1935 0(moda) (por propiedad); 1935-17710(moda) (por propiedad); 2222-17710(moda) (por propiedad)

287 0 (mod a); 164 0 (mod a); 451 0 (mod a)

287-164 0(moda) (por propiedad); 451-2870(moda)(por propiedad)

123 0 (mod a); 164 0 (mod a)

164-123 0(mod a) (por propiedad)

41

Una comparación de primer grado con una incógnita tiene la forma:

F(X) 0 (mód. metro); F(X) = Oh + y N. (1)

Resolver comparación- significa encontrar todos los valores de x que lo satisfagan. Dos comparaciones que satisfacen los mismos valores de x se llaman equivalente.

Si la comparación (1) se satisface por cualquier X = X 1, entonces (según 49) todos los números comparables a X 1, módulo metro: x x 1 (mod. metro). Toda esta clase de números se considera una solución. Con tal acuerdo, se puede sacar la siguiente conclusión.

66.C alineación (1) tendrá tantas soluciones como el número de residuos del sistema completo que lo satisfagan.

Ejemplo. Comparación

6X– 4 0 (módulo 8)

Entre los números 0, 1,2, 3, 4, 5, 6, 7, dos números satisfacen el sistema completo de residuos módulo 8: X= 2 y X= 6. Por tanto, esta comparación tiene dos soluciones:

X 2 (mod 8), X 6 (mod 8).

La comparación de primer grado moviendo el término libre (con el signo opuesto) hacia el lado derecho se puede reducir a la forma

hacha b(modificación metro). (2)

Considere una comparación que satisfaga la condición ( A, metro) = 1.

Según 66, nuestra comparación tiene tantas soluciones como residuos del sistema completo que la satisfacen. Pero cuando X recorre todo el sistema de residuos de módulo T, Eso Oh recorre todo el sistema de deducciones (sobre 60). Por lo tanto, para un solo valor X, tomado del sistema completo, Oh será comparable a b. Entonces,

67. Cuando (a, m) = 1 eje de comparación b(modificación metro)tiene una solución.

Vamos ahora ( a, metro) = d> 1. Entonces, para que la comparación (2) tenga soluciones, es necesario (de 55) que b dividido por d, de lo contrario, la comparación (2) es imposible para cualquier número entero x . Suponiendo por lo tanto b múltiplos d, pongamos a = a 1 d, b = b 1 d, metro = metro 1 d. Entonces la comparación (2) será equivalente a esto (abreviado por d): a 1 X b 1 (mod. metro), en el que ya ( A 1 , metro 1) = 1, y por lo tanto tendrá un módulo de solución metro 1 . Dejar X 1 – el residuo no negativo más pequeño de esta solución módulo m 1 , entonces todos los números son x , formando esta solución se encuentran en la forma

X X 1 (mod. metro 1). (3)

Módulo m, los números (3) no forman una solución, sino más, exactamente tantas soluciones como números (3) en la serie 0, 1, 2, ..., metro – 1 menos residuos de módulo no negativos metro. Pero aquí caerán los siguientes números (3):

X 1 , X 1 + metro 1 , X 1 + 2metro 1 , ..., X 1 + (d – 1) metro 1 ,

aquellos. Total d números (3); por lo tanto la comparación (2) tiene d decisiones.

Obtenemos el teorema:

68. Sea (a, m) = d. Comparación hacha b ( modificación m) es imposible si b no es divisible por d. Cuando b es múltiplo de d, la comparación tiene d soluciones.

69. Un método para resolver comparaciones de primer grado, basado en la teoría de fracciones continuas:

Desarrollando a una fracción continua la relación mamá,

y mirando las dos últimas fracciones coincidentes:

según las propiedades de las fracciones continuas (según 30 ) tenemos

Entonces la comparación tiene solución.

encontrar, que es suficiente para calcular p norte– 1 según el método especificado en 30.

Ejemplo. Resolvamos la comparación.

111X= 75 (módulo 321). (4)

Aquí (111, 321) = 3, y 75 es múltiplo de 3. Por lo tanto, la comparación tiene tres soluciones.

Dividiendo ambos lados de la comparación y el módulo por 3, obtenemos la comparación

37X= 25 (mod 107), (5)

que primero debemos resolver. Tenemos

Entonces, en este caso norte = 4, p n – 1 = 26, b= 25, y tenemos una solución a la comparación (5) en la forma

X–26 ∙ 25 99 (mod 107).

Por lo tanto, las soluciones a la comparación (4) se presentan de la siguiente manera:

X 99; 99+107; 99 + 2 ∙ 107 (mod 321),

Xº99; 206; 313 (mod. 321).

Cálculo del elemento inverso por un módulo dado.

70.Si los números son enteros a Y norte son coprimos, entonces hay un número a', satisfaciendo la comparación un ∙ un ′ ≡ 1(mod. norte). Número a' llamado inverso multiplicativo de un módulo n y la notación utilizada para ello es a- 1 (mod. norte).

El cálculo de cantidades recíprocas módulo de un cierto valor se puede realizar resolviendo una comparación de primer grado con una incógnita, en la que X numero aceptado a'.

Para encontrar una solución de comparación

a∙x≡ 1(mod. metro),

Dónde ( soy)= 1,

puede utilizar el algoritmo de Euclides (69) o el teorema de Fermat-Euler, que establece que si ( soy) = 1, entonces

a φ( metro) ≡ 1(mod metro).

X ≡ a φ( metro)–1 (mód. metro).

Grupos y sus propiedades.

Los grupos son una de las clases taxonómicas utilizadas para clasificar estructuras matemáticas con propiedades características comunes. Los grupos tienen dos componentes: un montón de (GRAMO) Y operaciones() definido en este conjunto.

Los conceptos de conjunto, elemento y membresía son los conceptos básicos indefinidos de las matemáticas modernas. Cualquier conjunto está definido por los elementos incluidos en él (que, a su vez, también pueden ser conjuntos). Por tanto, decimos que un conjunto está definido o dado si para cualquier elemento podemos decir si pertenece a ese conjunto o no.

Para dos juegos A, B registros B A, B A, B∩ A, B A, B \ A, A × B significan respectivamente que B es un subconjunto del conjunto A(es decir, cualquier elemento de B también está contenido en A, por ejemplo, el conjunto de los números naturales está contenido en el conjunto de los números reales; además siempre A A), B es un subconjunto propio del conjunto A(aquellos. B A Y B ≠ A), intersección de muchos B Y A(es decir, todos los elementos que se encuentran simultáneamente en A, y en B, por ejemplo, la intersección de números enteros y reales positivos es el conjunto de números naturales), la unión de conjuntos B Y A(es decir, un conjunto que consta de elementos que se encuentran en A, ya sea en B), establecer la diferencia B Y A(es decir, el conjunto de elementos que se encuentran en B, pero no te acuestes A), producto cartesiano de conjuntos A Y B(es decir, un conjunto de pares de la forma ( a, b), Dónde a A, b B). Vía | A| la potencia del conjunto siempre se denota A, es decir. número de elementos en el conjunto A.

Una operación es una regla según la cual dos elementos cualesquiera de un conjunto GRAMO(a Y b) coincide con el tercer elemento de G: un b.

muchos elementos GRAMO con una operación se llama grupo, si se cumplen las siguientes condiciones.