clase 12 congruencias

SAVE OFFLINE

Congruencia – Función de Euler – Teorema de Fermat

Cálculo del Resto

Ecuaciones Lineales de Congruencia

Congruencia Módulo n – Función de Euler La relación “congruencia módulo m”, que es una relación de equivalencia, clasifica a los números enteros según su resto en la división por n. •

Reflexiva:  a  Z: m I a – a  a  a (m)  a R a

•

Simétrica:  a, b  Z: a R b  a  b (m)  b  a (m)  b R a

•

Transitiva:  a, b, c  Z: a R b  b R c  a  b (m)  b  c (m)  a  c (m)  a R C

Las clases de equivalencia Cla = { m.q + a, a  Z } El conjunto cociente se escribe Zm = { Cl0, Cl1, Cl2, …., Cl(m – 1) }

Propiedades

𝑎 ≡ 𝑐 𝑚ó𝑑 𝑚 ∧ 𝑏 ≡ 𝑑

𝑚ó𝑑 𝑚

⇒𝑎 ± 𝑏≡𝑐 ± 𝑑

𝑎≡𝑐

𝑚ó𝑑 𝑚

⇒𝑎⋅𝑏 ≡𝑐⋅𝑑

𝑚ó𝑑 𝑚

∧𝑏 ≡𝑑

𝑚ó𝑑 𝑚

𝑚ó𝑑 𝑚

𝑎 ≡ 𝑐 𝑚ó𝑑 𝑚 ⇒ 𝑎 ⋅ 𝑘 ≡ 𝑐 ⋅ 𝑘 𝑚ó𝑑 𝑚⋅ 𝑎≡𝑏

𝑚ó𝑑 𝑚

𝑎≡𝑏

𝑚

∧𝑎 ≡𝑏

⇒ 𝑎𝑛 ≡ 𝑏 𝑛

⇒𝑎≡𝑏

𝑚ó𝑑 𝑠 𝑚

𝑚ó𝑑

mcm { 𝑚,𝑠}

∀𝑛 ∈ ℤ+

𝑎 ⋅ 𝑘 ≡ 𝑐 ⋅ 𝑘 𝑚ó𝑑 𝑚⋅ ∧ 𝑑 = 𝑚𝑐𝑑 𝑘, 𝑚 ⇒ 𝑎 ≡ 𝑐

𝑚 𝑑

𝑎 ⋅ 𝑘 ≡ 𝑐 ⋅ 𝑘 𝑚ó𝑑 𝑚⋅ ∧ 1 = 𝑚𝑐𝑑 𝑘, 𝑚 ⇒ 𝑎 ≡ 𝑐 𝑚ó𝑑 𝑚 𝑎 ⋅ 𝑘 ≡ 𝑐 ⋅ 𝑘 𝑚⋅𝑘 ⇒ 𝑎 ≡ 𝑐

𝑚

Aritmética en ℤ𝑚 Dados dos enteros cualesquiera a y b, definimos la suma en ℤ𝑚 en la forma siguiente: [a] + [b] = [a + b]

Dados dos enteros cualesquiera a y b, definimos el producto en ℤ𝑚 en la forma siguiente: [a] . [b] = [a . b] El elemento neutro [e] para la suma en ℤ𝑚 es la clase [0]. Esto es [e] + [a] = [a] Elemento opuesto. Si [a] es cualquiera de ℤ𝑚 , entonces su opuesto es [−a] El elemento neutro para la multiplicación en ℤ𝑚 es la clase [1]. Un elemento [a] de ℤ𝒎 admite inverso si, y solo si, a y m son coprimos Si n es un número primo p, entonces todos los elementos de ℤ𝑝 salvo el cero tienen inverso.

Un elemento [a] de ℤ𝒎 admite inverso si, y solo si, a y m son coprimos Demostración _

_

𝑎 ∗ 𝑎 1 = 𝑎 1 ∗ 𝑎 = 𝑒 definición de elemento inverso (simétrico) 𝑎 ⋅ 𝑎−1 = 1 ⇒ 𝑎 ⋅ 𝑎−1 = 1

⇒ 𝑎 ⋅ 𝑎−1 ≡ 1 𝑚

Dos clases iguales son congruentes

⇒ 𝑎 ⋅ 𝑎−1 = m ⋅ 𝑞 + 1

Def. de congruencia

⇒ 𝑎 ⋅ 𝑎−1 − m ⋅ 𝑞 = 1

Ec. diofántica

Esta ecuación lineal con coeficientes enteros tiene solución si, y sólo si m.c.d.(𝑎, m) = d y d |1, entonces d = 1 es decir, si a y m son primos entre sí.

Ejemplo en

ℤ6

SISTEMAS DE RESTOS Un conjunto de números enteros forma un sistema de números

incongruentes respecto a un módulo m, cuando cada uno de ellos produce un resto distinto al dividirlo entre n (son incongruentes dos a dos). Por ejemplo, 13, 26, 36 y 78 forman un sistema de números incongruentes

módulo 12, pues producen los restos 1, 2, 0 y 6 respectivamente. Los restos módulo m sólo pueden ser los elementos del conjunto {0, 1,2,...m -1} que constituyen un sistema completo de restos. ❖ El conjunto cociente constituye un sistema completo de restos módulo m

❖ La totalidad de restos r tales que 1  r  m , coprimos con m, forma un sistema reducido de restos módulo m

Un sistema completo de restos módulo 8 es, por ejemplo, el conjunto:

Sist. completo = {0, 1, 2, 3, 4, 5, 6, 7} Un sistema reducido de representantes módulo 8 podría ser el siguiente: Sist. reducido = {1, 3, 5, 7}. Función de Euler La función de Euler, que se indica  (n) es el cardinal del conjunto de estos restos. Formalmente,

 (m) = { x  N / x  m  mcd ( x, m) = 1}

𝜑(2) = 𝑥 ∈ ℕΤ𝑥 < 2 ∧ 𝑥, 2 = 1 = 1 = 1

Ejemplos:

𝜑(3) = 𝑥 ∈ ℕΤ𝑥 < 3 ∧ 𝑥, 3 = 1 = 1,2 = 2 𝜑(4) = 𝑥 ∈ ℕΤ𝑥 < 4 ∧ 𝑥, 4 = 1 = 1,3 = 2 𝜑(12) = 𝑥 ∈ ℕΤ𝑥 < 12 ∧ 𝑥, 12 = 1 = 1,5,7,11 = 4

1. Si p es un número primo,  (p) = p – 1,

Propiedades

Ejemplo: si p = 3, primo   (3) = 2 2. Si n  IN y p es un número primo se tiene que:

Ejemplo:  (343) =

φ (pn) = pn - 1 ( p – 1 )

 (73) = 73 -1 ( 7 – 1 ) = 49 . 6 = 294

3. Si n y m  IN y ( m, n ) = 1 

 (n . m) =  (n) .  (m)

Ejemplo: si n = 5 y m = 4

( 5, 4 ) = 1

 (20) =  (5 . 4) =  (5) .  (4) = 4 . 2 = 8 4. n = p1 k1 ⋅ p2 k2 ⋅ p3 k3 ⋅⋅⋅⋅ pr kr pi divisores primos de n 1 1 1 1 𝜙(𝑛) = 𝑛 ⋅ 1 − ⋅ 1− ⋅ 1− ⋅⋅⋅⋅ 1 − 𝑝1 𝑝2 𝑝3 𝑝𝑟 Ejemplo: si p = 48 los divisores primos de 48 son 2 y 3

𝜑 ( 48 ) = 48

1 1− 2

1 1− 3

1 2 = 48 . . = 16 2 3

Pequeño Teorema de Fermat

Sean a, p  Z y p es primo, si ( a, p ) = 1  ap -1  1 (p)

Colorario

Si p es primo  ap  a (p) Teorema de Euler – Fermat Si ( a, n ) = 1  aφ(n)  1 (n) Observación

aφ(n)  1 (n) a . aφ(n) - 1  1 (n)

a - 1 = aφ(n) - 1

Cálculo del Resto

Ejemplo: Calcular el resto de dividir a) r ( 5417, 3 ) p = 3 primo

( 5, 3 ) = 1

417 = 2 . 208 + 1

417

2

Teniendo en cuenta que ap-1  1 (p)

17

208

52  1 (3)

1

52  1 (3)  52.208  1 (3)  52.208 . 5  1 . 5 (3)  52.208 + 1  5 (3)

 5417  5 (3)  5417  2 (3) Resto = 2

b) r ( 477385, 17 )

p = 17 primo

Teniendo en cuenta que ap-1  1 (p) 4716  1 (17) 4716

 1 (17)  

4716.461



4716.461 .

1461 479

( 47, 17 ) = 1

7385

16

98

461

25 9

(17)

1

.

479

(17)

7385 = 16 . 461 + 9

 4716.461 + 9  479 (17) 47  13 (17) 472  47 . 13 (17)  13 . 13 (17)  16 (17) 474  16 . 16 (17)  1 (17) 478  1 . 1 (17)  1 (17)

479  47 . 1 (17)  13 (17)

Resto = 13

Ecuaciones Lineales de Congruencia Una expresión de la forma 𝑎

.𝑥𝑏

(𝑛) con 𝑎,

𝑏∈𝑍 𝑦 𝑛>1

se denomina ecuación lineal de congruencia Condición necesaria y suficiente para que una ecuación de congruencia tenga solución Para que la ecuación

𝑎.𝑥𝑏

(𝑛)

admita una solución es que (𝑎, 𝑛) | 𝑏

La cantidad de soluciones es (𝑎, 𝑛) Ejemplo:

33 . 𝑥  24 (𝟏𝟓)

Como el (33, 15) = 3

La ecuación tiene 3 soluciones

y

3 | 24

Sean a y b dos enteros, con 𝑚𝑐𝑑 𝑎, 𝑛 = 1 , entonces la ecuación

𝑎.𝑥𝑏

posee solución

Demostración

𝑥  𝑎𝜑

𝑎.𝑥𝑏

𝑛 −1

(𝑛)

.𝑏

(𝑛)

𝑎−1 . 𝑎 . 𝑥  𝑎−1 . 𝑏 𝑥  𝑎−1 . 𝑏

(𝑛)

𝑥  𝑎−1 . 𝑏

(𝑛)

𝑥  𝑎𝜑

𝑎, 𝑛 = 1 ⟹ 𝑎 tiene inverso

(𝑛)

𝑛 −1

𝑎−1 . 𝑎  1 y 1 . 𝑥  x 𝑎 - 1  𝑎 φ(n) - 1

.𝑏

Si 𝑚𝑐𝑑 𝑎, 𝑛 = 𝑑 > 1 con d | b, es solución cualquier

𝑛 𝑥 ≡ 𝑥0 + 𝑘 𝑑

𝑚𝑜𝑑 𝑛

con k = 0, 1, 2,..., d − 1 donde 𝑥0 es solución de la ecuación

𝑎 𝑏 𝑥≡ 𝑑 𝑑

𝑛 𝑑

Ejemplo: a) 5x  14 (18)

𝑥  𝑎𝜑

𝑛 −1

( 5, 18 ) = 1

1 | 14 hay solución

. 𝑏 (𝑛)

1 𝜑 18 = 18 1 − 2

1 1− 3

1 2 = 18 . . = 6 2 3

𝑥  56 − 1 . 14 (18)

𝑥  3125 .14 = 43750 (18) 𝑥  10

(18)

43750

18

77

2430

55 10

𝑏𝑢𝑠𝑐𝑜 𝑚𝑐𝑑 33,15 = 3

33𝑥 ≡ 24 15

𝑦 3|24

𝐿𝑎 𝑒𝑐𝑢𝑎𝑐𝑖ó𝑛 𝑡𝑖𝑒𝑛𝑒 3 𝑠𝑜𝑙𝑢𝑐𝑖𝑜𝑛𝑒𝑠 11𝑥 ≡ 8 5

𝑑𝑖𝑣𝑖𝑑𝑜 𝑡𝑜𝑑𝑜 𝑝𝑜𝑟 𝑚𝑐𝑑

𝑐𝑜𝑚𝑜 𝑒𝑙 𝑚𝑐𝑑 11,8 = 1 𝑙𝑎 𝑠𝑜𝑙𝑢𝑐𝑖ó𝑛 𝑒𝑠 𝑥 ≡ 𝑎𝜑 𝑥 ≡ 11𝜑

5 −1

𝑥 ≡ 113 ⋅ 8 5

⋅8

5

𝑛 −1

⋅𝑏

𝑚𝑜𝑑 𝑛

𝑐𝑎𝑙𝑐𝑢𝑙𝑜 𝜑 5 = 4

𝑐𝑜𝑚𝑜 11 ≡ 1 5 → 113 ≡ 1 5

𝑥 ≡1⋅8 5 →𝑥 ≡3 5

∴ 𝑥0 ≡ 3 15

𝑚 𝐿𝑢𝑒𝑔𝑜 𝑙𝑎𝑠 𝑑𝑒𝑚𝑎𝑠 𝑠𝑜𝑙𝑢𝑐𝑖𝑜𝑛𝑒𝑠 𝑠𝑜𝑛 𝑥 ≡ 𝑥0 + 𝑘 𝑑 15 𝑥 = 3+𝑘 → 𝑥 =3+5⋅𝑘 3

𝑥1 = 3 + 5 = 8 ∧ 𝑥2 = 3 + 5 ⋅ 2 = 13

𝑚𝑜𝑑 𝑚

𝑆 = 3, 8, 13