Aritmética modular - Foro fmat.cl

Foro fmat.cl > Sector Preparación Olimpiadas > Sector PreOlímpico > Teoría de Números > Material de Entrenamiento

Aritmética modular, un poquito para aprender

Opciones

ciunhaly Ver Perfil del Miembro Ver los mensajes de este miembro	Jun 1 2007, 03:00 AM Publicado: #1
Maestro Matemático Grupo: Colaborador Silver Mensajes: 128 Registrado: 30-June 06 Desde: En Rio de Janeiro, Brasil Miembro Nº: 1.477 Nacionalidad: Universidad: Sexo:	Aritmética Modular Hecho por Ciunhaly Muchos de los problemas que involucran enteros muy grandes pueden simplificarse con aritmética modular, en la que se utilizan congruencia en vez de ecuaciones. La idea básica es elegir un determinado entero $TEX: $n$$ , llamado módulo y sustituir cualquier entero por el resto de su división entre $TEX: $n$$ . En general, los restos son pequeños y, por tanto, más fácil de trabajar con ellos. Ejemplo: Si contamos 9378 días a partir de hoy (suponer que hoy es jueves), ¿en qué día de la semana caerá? Podemos resolverlo tomando un calendario y comenzar a contar, pero esto resulta muy tedioso. Si nos damos cuenta los días de la semana se repiten cada 7 días, así nuestro $TEX: $n$$ es 7. Por tanto 9378=1339·7+5, el resto resulta ser 5, es así que en 9378 días más el día será Martes. Definición Sea $TEX: $n$$ un entero positivo y sean $TEX: $a$$ y $TEX: $b$$ dos enteros cualesquiera. Se dice que $TEX: $a$$ es congruente con $TEX: $b$$ módulo $TEX: $n$$ si $TEX: $n$$ divide a $TEX: $a-b$$ y lo denotamos por: $TEX: $a\equiv b\pmod{n}$$ Usaremos el algoritmo de la división para expresar $TEX: $a=q\cdot n+r$$ con $TEX: $0 \leq r < n$$ y $TEX: $b=q'\cdot n+r'$$ con $TEX: $0 \leq r' < n$$ , diremos que $TEX: $a\equiv b\pmod{n}$$ si y sólo si $TEX: $r=r'$$ . Así, $TEX: $100\equiv2\pmod{7}$$ ( $TEX: $100=14\cdot 7+2 \wedge 2=0\cdot 7+2$$ , ambos con resto 2). Lema Para cualquier entero dado $TEX: $n\geq 1$$ se tiene que $TEX: $a\equiv b\pmod{n}$$ si y sólo si, $TEX: $n\|(a-b)$$ . Demostración Sea $TEX: $n\in\mathbb{Z}^+$$ y sean $TEX: $a,b\in\mathbb{Z}$$ $TEX: $\Rightarrow$$ Si $TEX: $a\equiv b\pmod{n}$$ , entonces $TEX: $n\|(a-b)$$ . Expresando $TEX: $a=q\cdot n+r$$ y $TEX: $b=q'\cdot n+r'$$ , tenemos que $TEX: $a-b=(q-q')\cdot n+(r-r')$$ con $TEX: $-n<r-r'<n$$ . Si $TEX: $a\equiv b\pmod{n}$$ entonces $TEX: $r=r'$$ , por lo que $TEX: $r-r'=0$$ y $TEX: $a-b=(q-q')\cdot n$$ , por lo que es divisible por $TEX: $n$$ . $TEX: $\Leftarrow$$ Si $TEX: $n\|(a-b)$$ , entonces $TEX: $a\equiv b\pmod{n}$$ Si $TEX: $n$$ divide a $TEX: $(a-b)$$ entonces divide a $TEX: $(a-b)-(q-q')\cdot n=r-r'$$ , como el único entero estrictamente contenido entre $TEX: $-n$$ y $TEX: $n$$ divisible por $TEX: $n$$ es 0, se tiene que $TEX: $r-r'=0$$ , de donde $TEX: $r=r'$$ y, por tanto, $TEX: $a\equiv b\pmod{n}\bullet $$ . Lema $TEX: $()$$ Para cualquier entero fijo $TEX: $n\geq 1$$ se verifican las siguientes propiedades: Reflexiva: $TEX: $a\equiv a\pmod{n}$$ para cualquier entero $TEX: $a$$ . Simétrica: $TEX: $a\equiv b\pmod{n} \Longrightarrow b\equiv a\pmod{n}$$ Transitiva: $TEX: $\displaystyle{\left. {a\equiv b\pmod{n}\atop b\equiv c\pmod{n}}\right\} }\Rightarrow a\equiv c\pmod{n}$$ Demostración* Sea $TEX: $n\in\mathbb{Z}^+$$ y sean $TEX: $a,b\in\mathbb{Z}$$ . Se verifica que $TEX: $n\|(a-a)$$ para cualquiera sea $TEX: $a$$ . Si $TEX: $n\|(a-b)$$ entonces $TEX: $n\|(b-a)$$ . Si $TEX: $n\|(a-b)$$ y $TEX: $n\|(b-c)$$ entonces $TEX: $n\|(a-b)+(b-c)=a-c$$ . Estas tres propiedades definen una relación de equivalencia, por lo que el lema () prueba que, para cada entero $TEX: $n$$ la congruencia de módulo $TEX: $n$$ es una relación de equivalencia en $TEX: $\mathbb{Z}$$ . $TEX: $[a]=\{ a,b\in\mathbb{Z} a \equiv b\pmod{n}\} =\{ ....,a-2n,a-n,a,a+n,a+2n,....\} $$ Cada clase corresponde a uno de los $TEX: $n$$ posibles restos $TEX: $r=0,1,....,n-1$$ de la división entre $TEX: $n$$ , por lo que existen $n$ clases de congruencia. Estas son: $TEX: $ [0]=\{ ....,-2n,-n,0,n,2n,.... \}$$ $TEX: $[1]=\{ ....,1-2n,1-n,1,1+n,1+2n,.... \}$$ $TEX: $\vdots $$ $TEX: $[n-1]=\{ ....,n-1-2n,n-1-n,n-1,n+1n,n-1+2n,.... \}$$ $TEX: $[n-1]=\{ ....,-n-1,-1,n-1,2n-1,3n-1,.... \}$$ No existen más clases de equivalencias, así, por ejemplo $TEX: $[n]\;\;=\;\; \{....,-2n,-n,0,n,2n,.... \}=[0]$$ De forma más general, se tiene que $TEX: $[a]=<b>$$ si y sólo si $TEX: $a\equiv b\pmod{n}$$ Cuando $TEX: $n=1$$ todos los enteros son congruentes, y esta clase es todo $TEX: $\mathbb{Z}$$ , si $TEX: $n=2$$ tenemos dos clases, $TEX: $[0]$$ y $TEX: $[1]$$ ambas con modulo 2, así tenemos los enteros pares e impares, respectivamente. Para cada $TEX: $n\geq 1$$ , el conjunto de las $TEX: $n$$ clases de congruencia de módulo $TEX: $n$$ lo denotamos por $TEX: $\mathbb{Z}_n$$ . Si $TEX: $[a]$$ y $TEX: $[b]$$ son elementos de $TEX: $\mathbb{Z}_n$$ (clases de congruencias módulo $TEX: $n$$ ) definimos la suma, diferencia y producto como las clases: $TEX: $[a]+[b]=[a+b]$$ $TEX: $[a]-[b]=[a-b]$$ $TEX: $[a][b]=[ab]$$ que contienen a los enteros $TEX: $a+b$$ , $TEX: $a-b$$ y $TEX: $ab$$ , respectivamente. [b]Lema $TEX: $()$$ Para cualquier entero $TEX: $n\geq 1$$ , si $TEX: $a'\equiv a\pmod{n}$$ y $TEX: $b'\equiv b\pmod{n}$$ , entonces $TEX: $a'+b'\equiv a+b\pmod{n}$$ , $TEX: $a'-b'\equiv a-b\pmod{n}$$ y $TEX: $a'b'\equiv ab\pmod{n}$$ . Demostración* Si $TEX: $a'\equiv a\pmod{n}$$ , entonces $TEX: $a'=a+kn$$ para algún $TEX: $k\in\mathbb{Z}$$ y análogamente $TEX: $b'\equiv b\pmod{n}$$ , entonces $TEX: $b'=b+l\cdot n$$ para algún $TEX: $l\in\mathbb{Z}$$ ; entonces, $TEX: $a'\pm b'=(a\pm b)+(k\pm l)n$$ y $TEX: $(a\pm b)+(k\pm l)n \equiv (a\pm b)\pmod{n} \Rightarrow a'\pm b'\equiv a\pm b$$ . Además, $TEX: $a'b'=ab+(al+bk+kln)n$$ y $TEX: $ab+(al+bk+kln)n\equiv ab\pmod{n} \Rightarrow a'b'\equiv ab \pmod{n}$$ . Ejemplo: Calculemos el menor resto no negativo de $TEX: $37\times 42 \pmod{46}$$ . Usando los menores restos absolutos tenemos que $TEX: $37\equiv -9\pmod{46}$$ y $TEX: $42\equiv -4\pmod{46}$$ , por Lema () $TEX: $37\times 42 \equiv (-9)\times(-4)\equiv 36 \pmod{46}$$ , así 36 es el menor resto no negativo de $TEX: $37\times 42 \pmod{46}$$ . __________________________________________________________________________________________________ __________________________________________________________________________________________________ Esperando que les sirva.... y para los que quieran el archivo pdf.... se los dejo de regalo y además con un bonus de ejercicios (claro está propuestos, pero es fácil vamos a la sector de problemas y los resolvemos allá) Mensaje modificado por ciunhaly el Jun 1 2007, 07:54 PM Archivo(s) Adjunto(s)** Apuntes_de_aritmetica_modular.pdf ( 63.75k ) Número de descargas: 548 -------------------- _______________________________________________________________ "La primera regla de la enseñanza es saber lo que se debe enseñar. La segunda, es saber un poco más de aquello que se debe enseñar". George Polya Eu sou uma estudante da UFRJ.