Módulo de comparación de un número natural. Resolver comparaciones y sus aplicaciones Resolver comparaciones

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.

Contenido.

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 es suficiente conocer en cualquier investigación 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 (mód 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 = p k - 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)

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

q
PAG 3

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 en la clasificación de 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.

Consideremos el sistema de comparaciones.

Donde f1(x), f2(x),…. , fs(x)€Z[x].

Teorema 1. Sea M = el mínimo común múltiplo de los números m1,m2,…,ms. Si a satisface el sistema (2), entonces cualquier número de la clase a módulo M satisface este sistema.

Prueba. Sea b€ a la clase a. Dado que a ≡ b(mod M), entonces a ≡b(mod m), i= 1,2,...,s (propiedad de comparación 16). En consecuencia, b, al igual que a, satisface toda comparación del sistema que prueba el teorema. Por lo tanto, es natural considerar la solución del sistema (2) como una clase módulo M.

Definición. Solución del sistema de comparaciones.(2) es la clase de números módulo M = que satisfacen cada comparación del sistema.

12. Observemos inmediatamente que los números impares no satisfacen la segunda comparación. Tomando números pares del sistema completo de residuos módulo 12, por verificación directa estamos convencidos de que los números 2, -2, 6 satisfacen la 2da comparación, y el sistema tiene dos soluciones: x ≡ 2(mod l2), x ≡ - 2 (mod. 12).

Consideremos el sistema de comparaciones de 1er grado (3)

Teorema2. Sea d=(m1,m2), M = .

Si c1 - c2 no es divisible por d, entonces el sistema (3) no tiene soluciones.

Si (c1 -c2):d, entonces el sistema (3) tiene una solución: una clase módulo M.

Prueba. De la primera comparación x = c1+m1t, t€Z. Sustituya en la segunda comparación: с1+ m1t ≡ c2(mod m2) o

m1t ≡ c2-cl (mod m2). Esta comparación tiene solución sólo si (c2 – c1): d.

Y la solución es un módulo de clase (Teorema 4 del §2).

Sea la solución , es decir, donde k€Z.

M== , es decir, x≡c1+m1t0(mod M) es la solución

Ejemplos.

1. :2, el sistema tiene una clase de solución módulo 24. De la primera comparación x =2+6t. Sustituyendo x en la segunda comparación, tenemos: 2 + 6t≡ 4(tnod 8); 6t≡ 2(mod 8); -2t≡2(mod8); t≡-1(mod 4); t=-1+4k; x=2+6(-1+4k); x=-4+24k, es decir x≡-4(mod 24).

2. 7-3 no es divisible por 3, el sistema no tiene soluciones.

Corolario 1. Sistema de comparación (4)

O no tiene soluciones o tiene una solución: una clase módulo M=.

Prueba. Si el sistema de las dos primeras comparaciones no tiene soluciones, entonces (4) no tiene soluciones. Si tiene una solución x ≡ a(mod), entonces al agregar una tercera comparación del sistema a esta comparación, obtenemos nuevamente un sistema de la forma (3), que tiene una solución o no tiene soluciones. Si tiene solución, entonces continuaremos así hasta haber agotado todas las comparaciones del sistema (4). Si hay una solución, entonces esta es una clase módulo M.

Comentario. La propiedad LCM se utiliza aquí: =.

Corolario 2. Si m1,m2,…,ms son coprimos por pares, entonces el sistema (4) tiene una solución: clase de módulo M=m1m2…ms.

Ejemplo:

Dado que los módulos son relativamente simples por pares, el sistema tiene una solución: módulo clase 105 = 5*3*7. De la primera comparación

Sustituimos en la segunda comparación: 2 +5t≡ 0(mod 3) o 2t≡-2(mod3), t=-1+3k, x=2+5(-1+3k), x=-3+15k . Sustituyamos en la tercera comparación:

3+15k≡5(mod7), 15k≡8(mod 7), k=1+7l. entonces x=-3+15(1+7l); x=12+105l; x≡12(mod 105).

vamos a conocer otros método para resolver este sistema (usamos el hecho de que el sistema tiene una solución). Multipliquemos ambas partes y el módulo de la primera comparación por 21, la segunda por 35 y la tercera por 15: de la suma de las primero y tercero restamos el segundo:

(36 -35)x ≡ 75 + 42(modl05); x≡117(mod105); x≡12(mod105).

Consideremos ahora un sistema de comparaciones de primer grado de forma general.

Si alguna comparación de este sistema no tiene soluciones, entonces el sistema no tiene soluciones. Si cada comparación del sistema (5) tiene solución, entonces la resolvemos para x y obtenemos un sistema equivalente de la forma (4):

Donde (Teorema 4, §2).

Según el Corolario 1, el sistema no tiene soluciones o tiene una solución.

Ejemplo:

Resuelta cada comparación del sistema, obtenemos un sistema equivalente

Este sistema tiene una solución: clase módulo 105. Multiplicando la primera comparación y el módulo por 3 y la segunda por 35, obtenemos

Restando la primera comparación multiplicada por 11 de la segunda comparación, obtenemos 2x ≡-62(modl05), de donde x ≡ -31(modl05).

Los problemas que se reducen a la consideración de un sistema de comparaciones de primer grado fueron considerados en la aritmética del matemático chino Sun Tzu, que vivió a principios de nuestra era. Su pregunta se planteó de la siguiente forma: encuentre un número que dé restos dados cuando se divide por números dados. También da una solución equivalente al siguiente teorema.

Teorema (teorema chino del resto). Sean m1,m2,…,ms números coprimos por pares, M = mlm2...ms, β1, β2,…, βs elegidos de modo que

Entonces la solución del sistema

Se verá así x≡x0(mod M).

Prueba. Como obtenemos x0≡

De manera similar, comprobamos que x0≡c2(mod m2),…, x0≡cs(mod ms), es decir, x0 satisface todas

comparaciones de sistemas.

10. Comparaciones de 1er grado. Ecuaciones inciertas

§ 2. Comparaciones de 1er grado. Ecuaciones inciertas

La comparación de primer grado se puede reducir a la forma ax≡b(mod m).

Teorema 4. Si (a,m) = 1, entonces la comparación ax ≡b(mod m) (2) tiene una solución única.

Prueba. Tomemos 0,1,2,...,m-1: un sistema completo de residuos módulo m. Dado que (a,m) = 1, entonces 0,a,2a,...,(m-1)a es también un sistema completo de residuos (Teorema 3, §2, Capítulo 2.). Contiene uno y sólo un número comparable a b módulo m (que pertenece a la misma clase que b). Sea ax 0, es decir, ax 0 € clase b o ax 0 ≡b(mod m). x ≡x 0 (mod m) es la única solución a (2). El teorema ha sido demostrado.

Teorema 5. Si (a, m)= 1, entonces la solución a la comparación ax≡b(mod m) es la clase x 0 ≡a φ (m)-1 b(mod m).

Prueba. Dado que (a,m) = 1, entonces, según el principio de Euler, a φ(m) ≡1(mod m). Es fácil ver que x 0 ≡a φ (m)-1 b (mod m) es la solución a la comparación (2). De hecho,a(a φ (m)-1 b)≡a φ (m) b≡b(mod m). Del Teorema 4 se deduce que esta solución es única.

Consideremos métodos de solución de comparación hacha ≡b(mod m).

1. Método de selección. Tomando el sistema completo de residuos módulo m, seleccionamos números que satisfagan la comparación.

2. Utilizando el teorema de Euler (Teorema 5).

3. Método de conversión de coeficientes. Debemos intentar transformar los coeficientes de modo que el lado derecho pueda dividirse por el coeficiente de x. Las transformaciones en cuestión son las siguientes: sustituir coeficientes por los residuos más pequeños absolutos, sustituir el número b por un número comparable en valor absoluto (sumar un número que sea múltiplo del valor absoluto) para que este último sea divisible por a, pasar de a y b a otros números comparables a ellos, que tendrían un divisor común, etc. En este caso, utilizamos las propiedades de las comparaciones y teoremas en comparaciones equivalentes basadas en ellas.

1) 223x ≡ 115(módulo ll).

Primero, reemplazamos los coeficientes con las deducciones de valor absoluto más pequeñas: 3х ≡ 5(mod 11). Si usamos el teorema

Euler, entonces

x≡3 φ(11)-1 *5=3 9 *5≡(3 3) 3 *5≡(27) 3 *5≡5 3 *5≡125*5≡4*5≡9(modll).

Sin embargo, es más fácil convertir los coeficientes. Reemplacemos la comparación con una equivalente sumando al lado derecho un número que sea múltiplo del módulo:

3x ≡ 5 + 22(mod 11). Dividiendo ambos lados por el número 3, coprimo al módulo, obtenemos x ≡ 9(mod l1).

2) 111x≡ 8(mod 34).

Utilizamos el método de conversión de coeficientes.

(111-3*34)x≡8(mod 34), 9x≡8+34≡42(mod 34), 3x≡14(mod 34), 3x≡14+34≡48(mod 34), x≡16 (mod 34).

Teorema 6. Si (a, m) = d y b no es divisible por d, entonces la comparación (1) no tiene soluciones.

Prueba (por contradicción). Sea la clase x 0 una solución, es decir, ax 0 ≡b (mod m) o (ax 0 -b):m, y, por tanto, (ax 0 -b):d. Pero a:d, entonces b:d es una contradicción. Por tanto, la comparación no tiene soluciones.

Teorema 7. Si (a,m)= d, d>1, b:d, entonces la comparación (1) tiene d

soluciones que constituyen una clase de residuos de módulo y se encuentran mediante las fórmulas

Dónde Con satisface la comparación auxiliar

Comentario. Según el teorema, la comparación (1) se resuelve de la siguiente manera.

1) Habiendo asegurado que (a,m) = d, d> 1 y b:d, dividimos ambas partes en comparaciones (2) por d y obtenemos una comparación auxiliar a 1 x≡b 1 (mod m 1), dónde . La comparación sólo tiene una solución. Sea la clase c la solución.

2) Escribe la respuesta x 0 ≡c(mod m), x 1 ≡c+m 1 (mod m), x 2 ≡c+2m 1 (mod m), … , x d -1 ≡c+(d-1) m1 (mod m).

Prueba. La comparación auxiliar según el teorema 2(3) es equivalente a la comparación original (2). Dado que ( 1, entonces la comparación auxiliar tiene una solución única: la clase módulo m 1 =. Sea x≡c(mod m 1) la solución. La clase de números c módulo m 1 se divide en d clases módulo m: .

De hecho, cualquier número de la clase x0 módulo m 1 tiene la forma x 0 +m 1 t. Divida t con resto por d: t = dq +r, donde 0≤r

Entonces, la comparación (1) tiene d soluciones módulo m: x0, x0+m1,..., x0 +(d-1)m1 (líneas horizontales en la parte superior).

Ejemplos.

1) 20x≡ 15(mod 108). Como (20,108) = 4 y 15 no es divisible por 4, no hay soluciones.

2) 20x≡ 44(mod 108). (20,108) = 4 y 44:4, por lo tanto la comparación tiene cuatro soluciones. Dividiendo ambas partes y el módulo por 4, obtenemos:

5х≡11(mod 27); 5 x≡11-81 ≡ -70(mod27), x ≡ -14 ≡ 13(mod 27). Entonces x≡13 + 27r(mod 108), donde r = 0,1,2,3. yo jj

Respuesta: x≡13(modl08); x ≡ 40(modl08); x ≡ 67(modl08); x≡94(modl08).

Aplicación de la teoría de las comparaciones a la resolución de ecuaciones inciertas.

Consideremos una ecuación indeterminada o, como también se la llama, diofántica de primer grado con dos incógnitas ax + by = c, donde a, b, c € Z. Necesitas resolver esta ecuación en números enteros. Si (a,b)=d y c no es divisible por d, entonces es obvio que la comparación no tiene soluciones en números enteros. Si c es divisible por d, entonces divide ambos lados de la ecuación entre d. Por tanto, basta considerar el caso en el que (a, b) =1.

Dado que ax difiere de c en un múltiplo de b, entonces ax ≡ c(mod b) (sin pérdida de generalidad podemos suponer que b > 0). Resolviendo esta comparación, obtenemos x ≡x1 (mod b) o x=x1+bt, donde t€Z. Para determinar los valores correspondientes de y tenemos la ecuación a(x1 + bt) + by = c, de la cual

Además, - es un número entero, es un valor parcial de la incógnita y, correspondiente a x1 (resulta, como x1, en t = 0). Y la solución general de la ecuación tomará la forma de un sistema de ecuaciones x=x1+bt, y=y1-at, donde t es un número entero cualquiera.

Nota que 1) la ecuación ax + by = c podría resolverse comenzando con la comparación por ≡ c(mod a), ya que by difiere de c en un múltiplo de a;

2) es más conveniente elegir como módulo módulo más pequeño a y B.

Ejemplo, 50x – 42y= 34.

Divide ambos lados de la ecuación por 2.

25x ≡ 17(mod2l); 4x ≡ 17 (mod 21) o 4x ≡ 17-21 ≡ -4 (mod21).

x ≡ -1 (mod 21), es decir, x=-1+21t, t€Z. Sustituyamos la x encontrada en la ecuación. 25(-1 + 21t)- 21y= 17; 21у =-42 + 25* 21t y у =-2 + 25t.