Matematicas - Notas De Divisibilidad Y Congruencia

´ Notas de Aritmetica para la Olimpiada de ´ Matematicas.

1 de febrero de 2002

Aritm´tica e

Karl Friedrich Gauss

´ Pedro Sanchez (drini@math.com)

1

´ndice General I

1 Divisibilidad ´ 1.1 Conceptos basicos. . . . . . . . . . . . . . . . . . . . . . . . . . ´ 1.2 Maximo comun divisor. . . . . . . . . . . . . . . . . . . . . . . . . ´

4 4 7

1.3 M´nimo comun multiplo. . . . . . . . . . . . . . . . . . . . . . . . 10 i ´ ´ 1.4 Ecuaciones lineales diofantinas. . . . . . . . . . . . . . . . . . . 11 1.5 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2 Congruencias. 18

2.1 Congruencias. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 ´ 2.2 Ecuacion lineal de congruencia. . . . . . . . . . . . . . . . . . . 21 2.3 Ejercicios. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 ´ A Formulas e identidades utiles. ´ B Sugerencias y respuestas a ejercicios selectos. 23 25

2

´ Introduccion.
´ Este libro fue creado para el entrenamiento de la seleccion estatal de la Olimpiada de ´ ´ Matematicas en Yucatan. El objetivo que se busca no es crear un curso con el material expuesto, sino que se use como referencia y gu´a. Esto significa que no es necesario i ´ cubrir en clase todo el material que se incluye, pues eso representar´a una perdida i ´ ´ enorme de tiempo de entrenamiento, ademas que se corre el riesgo de enfatizar mas ´ la acumulacion de conocimiento en vez de la habilidad de problemas. El entrenamiento consta de aproximadamente seis meses. Durante los dos ´ primeros, es aconsejable revisar los conceptos de divisibilidad y maximo comun divisor, ´ realizando la mayor cantidad de ejercicios posibles. Se recomienda que al final de los ´ mismos se empiece a usar la terminolog´a de congruencias esporadicamente para que i al abordar el tema a partir del tercer mes ya se tenga una cierta familiaridad con el concepto. El objetivo final de todo el curso es que los alumnos dominen los conceptos ´ y teoremas de