Ejercicios preparación olimpiada de matemáticas

Aritmética modular
Definición.
Sean a y b dos números enteros, y será m un entero distinto de cero. Decimos que a es congruente con b módulo m si y sólo si m divide a a-b. Esto se escribe como:

a  b(mod m)  m a  b
Nota: La idea de módulos puede extenderse a los números reales en general, pero en este material y en general, en lo referente a las olimpiadas de matemáticas, trabajaremosúnicamente con números enteros. Nótese además que a partir de la definición podemos saber que el módulo 1 no sirve para nada… Espero no seas lo suficientemente despistado para preguntar por el módulo 0…

Por ejemplo:      8 ≡ 23 (mod 5) porque 8 – 23 = -15 y 5 | -15 19 – 3 =16 y 4 | 16, entonces 19 ≡ 3 (mod 4) 15 - 13= 2 pero 7 ¬| 2 entonces 15 ¬≡ 13 (mod 7) 54 ¬≡ 36 (mod 11) porque 54 – 36 =18 y 11 ¬| 18 -9 ≡ 7 (mod 16) porque -9 – 7 = -16 y 16 | -16

Una de las ventajas de las congruencias es que podemos manejarlas en muchos sentidos como si fueran ecuaciones algebraicas, aquí están las reglas que se deben seguir para ello:

Propiedades.
Si a, b, c, d, n, m son enteros y no entonces: i. a ≡ a (mod n) Ejemplo: 5 – 5 = 0 y 7 | 0 entonces 5 ≡ 5 (mod 7) Si a ≡ b (mod n) entonces b≡ a (mod n) Por los ejemplos de arriba tenemos que 19 ≡ 3 (mod 4), y notamos que 3 – 19= (16) y 4 | -16 entonces 3 ≡ 19 (mod 4). Si a ≡ b (mod n) y b ≡ c (mod n) entonces a ≡ c (mod n) Ejemplo: 8 ≡ 23 (mod 5) y 23 ≡ 3 (mod 5) entonces 8 ≡ 3 (mod 5) a ≡ 0 (mod n)  n | a Si a ≡ b (mod n) y c ≡ d (mod n) entonces: José Alberto de la Paz Espinosa. alberto_ nay@hotmail.com Marlet Morales Franco Tepic,Nayarit ; 2011

ii.

iii.

iv. v.

a) a + c ≡ b + d (mod n) Por ejemplo 19 ≡ 3 (mod 4) y 2 ≡ 6 (mod 4) entonces 19+2 ≡ 3+6 (mod 4) debe ser cierto, notamos que si lo es porque 21 – 9 = 12 y 4 | 12 b) ac ≡ bd (mod n) Tomamos las mismas dos congruencias, entonces 19•2 ≡ 3•6 (mod 4) debe ser cierto, notamos que si lo es porque 38 – 18 = 20 y 4 | 20 vi. Por el punto anterior, si a ≡ b (mod n),si x es un entero: a) a + x ≡ b + x (mod n) Notamos que 15 ≡ 4 (mod 11) y también que 17 ≡ 6 (mod 11) con x=2 b) ax ≡ bx (mod n) Si 23 ≡ 5 (mod 6) notamos que también 69 ≡ 15 (mod 6) con x=3 c) ax ≡ bx (mod n) Si 5 ≡ 2 (mod 3) notamos que también 125 ≡ 8 (mod 3) con x=3

vii.

Si a ≡ b (mod n) y d | n entonces a ≡ b (mod d) Ejemplo: 47 ≡ 2 (mod 15), notemos que 3|15, así que 47 ≡ 2 (mod 3),que se cumple. Si n = n’m donde m=(n,x), ax ≡ bx (mod n)  si y sólo si a ≡ b (mod n’) Ejemplo: Tenemos 28 = 7•4 donde 4=(28,8), 40≡ 96 (mod 28)  5 ≡ 12 (mod 7) Si a ≡ b (mod n) y a ≡ b (mod m) y (m,n)=1 entonces a ≡ b (mod mn) Ejemplo: 38≡ 8 (mod 3) y 38 ≡ 8 (mod 5), tenemos que 38 ≡ 8 (mod 15) Todo número es congruente módulo n al residuo resultante de dividirlo por n Ejemplo:19 – 3 =16 y 4 |16, entonces 19 ≡ 3 (mod 4)

viii.

ix.

x.

xi.

Si p(x) es un polinomio de coeficientes enteros, entonces a ≡ b (mod n) implica que p(a) ≡ p(b) (mod n) Ejemplo: Tenemos que 8 ≡ 2 (mod 6), Si p(x)=2x2+3x-7, tenemos que p(8)=2(8)2+3(8)-7=128+24-7=145, y p(2)= 2(2)2+3(2)-7=8+6-7=7, y sabemos que 145 ≡ 7 (mod 6)

Principio de Sustitución
Existe una propiedad muy importante derivada de lasanteriores conocida como el principio de sustitución que dice: José Alberto de la Paz Espinosa. alberto_ nay@hotmail.com Marlet Morales Franco Tepic, Nayarit ; 2011

“Para hacer operaciones (sumar y multiplicar) en una congruencia, cualquier cantidad puede sustituirse por otra a la que ésta sea congruente sin alterar la validez de la congruencia.”

¿Cuándo se pueden usar los módulos?
Losmódulos se pueden usar en muchos tipos de problemas de teoría de números, combinatoria y demás, la experiencia va facilitando el ver cuando pueden ser útiles, aquí hay algunos casos en que pueden ser útiles:        Cuando te piden que demuestre que algo divide a otra cosa, ya sea una expresión algebraica, alguno numero, una expresión aritmética algo extensa, etc. Demostrar y hacer...