Descarga la aplicación para disfrutar aún más
Vista previa del material en texto
TEORÍA DE NÚMEROS Metodología Problem Solving Con aplicaciones en criptografía y programación Phyton Gerard Romo Garrido Toomates Coolección vol. 6 Toomates Coolección Los libros de Toomates son materiales digitales y gratuitos. Son digitales porque están pensados para ser consultados mediante un ordenador, tablet o móvil. Son gratuitos porque se ofrecen a la comunidad educativa sin coste alguno. Los libros de texto pueden ser digitales o en papel, gratuitos o en venta, y ninguna de estas opciones es necesariamente mejor o peor que las otras. Es más: Suele suceder que los mejores docentes son los que piden a sus alumnos la compra de un libro de texto en papel, esto es un hecho. Lo que no es aceptable, por inmoral y mezquino, es el modelo de las llamadas "licencias digitales" con las que las editoriales pretenden cobrar a los estudiantes, una y otra vez, por acceder a los mismos contenidos (unos contenidos que, además, son de una bajísima calidad). Este modelo de negocio es miserable, pues impide el compartir un mismo libro, incluso entre dos hermanos, pretende convertir a los estudiantes en un mercado cautivo, exige a los estudiantes y a las escuelas costosísimas líneas de Internet, pretende pervertir el conocimiento, que es algo social, público, convirtiéndolo en un producto de propiedad privada, accesible solo a aquellos que se lo puedan permitir, y solo de una manera encapsulada, fragmentada, impidiendo el derecho del alumno de poseer todo el libro, de acceder a todo el libro, de moverse libremente por todo el libro. Nadie puede pretender ser neutral ante esto: Mirar para otro lado y aceptar el modelo de licencias digitales es admitir un mundo más injusto, es participar en la denegación del acceso al conocimiento a aquellos que no disponen de medios económicos, y esto en un mundo en el que las modernas tecnologías actuales permiten, por primera vez en la historia de la Humanidad, poder compartir el conocimiento sin coste alguno, con algo tan simple como es un archivo "pdf". El conocimiento no es una mercancía. El proyecto Toomates tiene como objetivo la promoción y difusión entre el profesorado y el colectivo de estudiantes de unos materiales didácticos libres, gratuitos y de calidad, que fuerce a las editoriales a competir ofreciendo alternativas de pago atractivas aumentando la calidad de unos libros de texto que actualmente son muy mediocres, y no mediante retorcidas técnicas comerciales. Estos libros se comparten bajo una licencia “Creative Commons 4.0 (Atribution Non Commercial)”: Se permite, se promueve y se fomenta cualquier uso, reproducción y edición de todos estos materiales siempre que sea sin ánimo de lucro y se cite su procedencia. Todos los libros se ofrecen en dos versiones: En formato “pdf” para una cómoda lectura y en el formato “doc” de MSWord para permitir y facilitar su edición y generar versiones parcial o totalmente modificadas. ¡Libérate de la tiranía y mediocridad de las editoriales! Crea, utiliza y comparte tus propios materiales didácticos Toomates Coolección Problem Solving (en español): Geometría Axiomática , Problemas de Geometría 1 , Problemas de Geometría 2 Introducción a la Geometría , Álgebra , Teoría de números , Combinatoria , Probabilidad Trigonometría , Desigualdades , Números complejos , Funciones Toomates Coolección Llibres de Text (en catalán): Nombres (Preàlgebra) , Àlgebra , Proporcionalitat , Mesures geomètriques , Geometria analítica Combinatòria i Probabilitat , Estadística , Trigonometria , Funcions , Nombres Complexos , Àlgebra Lineal , Geometria Lineal , Càlcul Infinitesimal , Programació Lineal , Mates amb Excel Toomates Coolección Compendiums: Ámbito PAU: Catalunya TEC Catalunya CCSS Galicia País Vasco Portugal A Portugal B Italia Ámbito Canguro: ESP , CAT , FR , USA , UK , AUS Ámbito USA: Mathcounts AMC 8 AMC 10 AMC 12 AIME USAJMO USAMO Putnam Ámbito español: OME , OMEFL , OMEC , OMEA , OMEM , CDP Ámbito internacional: IMO OMI IGO SMT INMO CMO REOIM Arquimede HMMT BMO Ámbito Pruebas acceso: ACM4 , CFGS , PAP Recopilatorios Pizzazz!: Book A Book B Book C Book D Book E Pre-Algebra Algebra Recopilatorios AHSME: Book 1 Book 2 Book 3 Book 4 Book 5 Book 6 Book 7 Book 8 Book 9 ¡Genera tus propias versiones de este documento! Siempre que es posible se ofrecen las versiones editables “MS Word” de todos los materiales, para facilitar su edición. Descarga en los siguientes enlaces la versión ".doc" de este documento: www.toomates.net/biblioteca/Aritmetica01.doc → http://www.toomates.net/biblioteca/Aritmetica26.doc ¡Ayuda a mejorar! Envía cualquier duda, observación, comentario o sugerencia a toomates@gmail.com ¡No utilices una versión anticuada! Todos estos libros se revisan y amplían constantemente. Descarga totalmente gratis la última versión de estos documentos en los correspondientes enlaces superiores, en los que siempre encontrarás la versión más actualizada. Consulta el Catálogo de libros de la biblioteca Toomates Coolección en http://www.toomates.net/biblioteca.htm Encontrarás muchos más materiales para el aprendizaje de las matemáticas en www.toomates.net Visita mi Canal de Youtube: https://www.youtube.com/c/GerardRomo Versión de este documento: 03/09/2023 http://www.toomates.net/biblioteca/GeometriaAxiomatica.pdf http://www.toomates.net/biblioteca/ProblemasGeometria.pdf http://www.toomates.net/biblioteca/ProblemasGeometria2.pdf http://www.toomates.net/biblioteca/Geometria.pdf http://www.toomates.net/biblioteca/ProblemasAlgebra.pdf http://www.toomates.net/biblioteca/Aritmetica.pdf http://www.toomates.net/biblioteca/Combinatoria.pdf http://www.toomates.net/biblioteca/Probabilidad.pdf http://www.toomates.net/biblioteca/ProblemasTrigonometria.pdf http://www.toomates.net/biblioteca/Desigualdades.pdf http://www.toomates.net/biblioteca/ProblemasNumerosComplejos.pdf http://www.toomates.net/biblioteca/ProblemasFunciones.pdf http://www.toomates.net/biblioteca/Nombres.pdf http://www.toomates.net/biblioteca/Algebra.pdf http://www.toomates.net/biblioteca/Proporcionalitat.pdf http://www.toomates.net/biblioteca/MesuresGeometriques.pdf http://www.toomates.net/biblioteca/GeometriaAnalitica.pdf http://www.toomates.net/biblioteca/GeometriaAnalitica.pdf http://www.toomates.net/biblioteca/CombinatoriaProbabilitat.pdf http://www.toomates.net/biblioteca/Estadistica.pdf http://www.toomates.net/biblioteca/Trigonometria.pdf http://www.toomates.net/biblioteca/Funcions.pdf http://www.toomates.net/biblioteca/NombresComplexos.pdf http://www.toomates.net/biblioteca/AlgebraLineal.pdf http://www.toomates.net/biblioteca/GeometriaLineal.pdf http://www.toomates.net/biblioteca/Calcul.pdf http://www.toomates.net/biblioteca/ProgramacioLineal.pdf http://www.toomates.net/biblioteca/MatesExcel.pdf http://www.toomates.net/biblioteca/Pautec.pdf http://www.toomates.net/biblioteca/Pauccss.pdf http://www.toomates.net/biblioteca/Galiciapau.pdf http://www.toomates.net/biblioteca/Paisvascopau.pdf http://www.toomates.net/biblioteca/Portugal635.pdf http://www.toomates.net/biblioteca/Portugal735.pdf http://www.toomates.net/biblioteca/Italia.pdf http://www.toomates.net/biblioteca/Canguro.pdf http://www.toomates.net/biblioteca/Cangur.pdf http://www.toomates.net/biblioteca/CompendiumKangourou.pdf http://www.toomates.net/biblioteca/CompendiumKangaroo.pdf http://www.toomates.net/biblioteca/CompendiumKangarooUK.pdf http://www.toomates.net/biblioteca/CompendiumKanguru.pdf http://www.toomates.net/biblioteca/CompendiumMathcounts.pdf http://www.toomates.net/biblioteca/CompendiumAMC8.pdf http://www.toomates.net/biblioteca/CompendiumAMC10.pdf http://www.toomates.net/biblioteca/CompendiumAMC12.pdf http://www.toomates.net/biblioteca/CompendiumAIME.pdf http://www.toomates.net/biblioteca/CompendiumUSAJMO.pdf http://www.toomates.net/biblioteca/CompendiumUSAMO.pdfhttp://www.toomates.net/biblioteca/CompendiumPutnam.pdf http://www.toomates.net/biblioteca/CompendiumOME.pdf http://www.toomates.net/biblioteca/CompendiumOMEFL.pdf http://www.toomates.net/biblioteca/CompendiumOMEC.pdf http://www.toomates.net/biblioteca/CompendiumOMEA.pdf http://www.toomates.net/biblioteca/CompendiumOMEM.pdf http://www.toomates.net/biblioteca/CompendiumCDP.pdf http://www.toomates.net/biblioteca/CompendiumIMO.pdf http://www.toomates.net/biblioteca/CompendiumOMI.pdf http://www.toomates.net/biblioteca/CompendiumIGO.pdf http://www.toomates.net/biblioteca/CompendiumSMT.pdf http://www.toomates.net/biblioteca/CompendiumINMO.pdf http://www.toomates.net/biblioteca/CompendiumCMO.pdf http://www.toomates.net/biblioteca/CompendiumREOIM.pdf http://www.toomates.net/biblioteca/CompendiumArchimede.pdf http://www.toomates.net/biblioteca/CompendiumHMMT.pdf http://www.toomates.net/biblioteca/CompendiumBMO.pdf http://www.toomates.net/biblioteca/CompendiumACM4.pdf http://www.toomates.net/biblioteca/CompendiumCFGS.pdf http://www.toomates.net/biblioteca/CompendiumPAP.pdf http://www.toomates.net/biblioteca2/PizzazzBookA.pdf http://www.toomates.net/biblioteca2/PizzazzBookB.pdf http://www.toomates.net/biblioteca2/PizzazzBookC.pdf http://www.toomates.net/biblioteca2/PizzazzBookD.pdf http://www.toomates.net/biblioteca2/PizzazzBookE.pdf http://www.toomates.net/biblioteca2/Pizzazz_pre_Algebra.pdf http://www.toomates.net/biblioteca2/pizzazz_algebra.pdf http://www.toomates.net/biblioteca2/contestproblembooks/TheContestProblemBook1.pdf http://www.toomates.net/biblioteca2/contestproblembooks/TheContestProblemBook2.pdf http://www.toomates.net/biblioteca2/contestproblembooks/TheContestProblemBook3.pdf http://www.toomates.net/biblioteca2/contestproblembooks/TheContestProblemBook4.pdf http://www.toomates.net/biblioteca2/contestproblembooks/TheContestProblemBook5.pdf http://www.toomates.net/biblioteca2/contestproblembooks/TheContestProblemBook6.pdf http://www.toomates.net/biblioteca2/contestproblembooks/TheContestProblemBook7.pdf http://www.toomates.net/biblioteca2/contestproblembooks/TheContestProblemBook8.pdf http://www.toomates.net/biblioteca2/contestproblembooks/TheContestProblemBook9.pdf http://www.toomates.net/biblioteca/Aritmetica01.doc http://www.toomates.net/biblioteca/Aritmetica26.doc http://www.toomates.net/biblioteca.htm http://www.toomates.net/ https://www.youtube.com/c/GerardRomo Índice. Primera parte: Primeros pasos con números enteros. 1 Primeros pasos con los números enteros. → Archivo doc 1.1 Bases de numeración. 1.2 Cuadrados perfectos. Potencias perfectas. 1.3 Orden en los números enteros. Principio de inducción. 2 Primeros pasos con Python. → Archivo doc 3.1 Instalación del IDE spyder. 3.2 Operaciones aritméticas con Python. 3 Problemas de la primera parte. → Archivo doc Segunda parte: Divisibilidad. 4 Divisibilidad. Mcd y mcm. → Archivo doc 4.1 Concepto de divisibilidad. 4.2 Divisibilidad y orden. 4.3 Máximo común divisor y mínimo común múltiplo. 4.4 El Teorema de Bezout (TDB). 4.5 Divisibilidad con números coprimos. 4.6 El algoritmo de Euclides (ADE). 4.7 Máximo común divisor con números coprimos. 4.8 Actividades con Python. 4.9 Problemas de introducción a la divisibilidad. 5 Números primos. → Archivo doc 5.1 Concepto de número primo. 5.2 El Teorema fundamental de la aritmética (TFA) 5.3 Resolución de problemas mediante identidades algebraicas. 6 Problemas de la segunda parte. → Archivo doc Tercera parte: Aritmética modular. 7 Introducción a la aritmética modular. → Archivo doc 7.1 Primer ejemplo: Las horas del día. 7.2 Segundo ejemplo: El conjunto Z7. 7.3 Los conjuntos Zn. 7.4 Aplicación a la criptografía: El cifrado César. 7.5 Aplicación a la criptografía: El cifrado Hill. 7.6 Problemas de aritmética modular básica. 8 Inversos multiplicativos modulares. → Archivo doc 8.1 Concepto de inverso multiplicativo. 8.2 Existencia y unicidad de inversos multiplicativos. 8.3 Inversión mediante el ADE. 8.4 Inversión mediante exponenciación modular. 8.5 Cancelación modular. 8.6 División modular. 8.7 Divisores de cero. 8.8 Actividades con Python. 9 Congruencias y sistemas de congruencias lineales. → Archivo doc 9.1 Congruencias lineales. 9.2 Sistemas de congruencias lineales con módulos coprimos. El TCR. 9.3 Sistemas de congruencias lineales con módulos no coprimos. 9.4 Congruencias lineales mediante sistemas de congruencias lineales. 9.5 Congruencias lineales con dos variables. http://www.toomates.net/biblioteca/Aritmetica01.doc http://www.toomates.net/biblioteca/Aritmetica02.doc http://www.toomates.net/biblioteca/Aritmetica03.doc http://www.toomates.net/biblioteca/Aritmetica04.doc http://www.toomates.net/biblioteca/Aritmetica05.doc http://www.toomates.net/biblioteca/Aritmetica06.doc http://www.toomates.net/biblioteca/Aritmetica07.doc http://www.toomates.net/biblioteca/Aritmetica08.doc http://www.toomates.net/biblioteca/Aritmetica09.doc 10 Congruencias cuadráticas. Residuos cuadráticos. → Archivo doc 10.1 Residuos cuadráticos. 10.2 Símbolos de Legendre y Jacobi. Ley de reciprocidad. Criterio de Euler. 10.3 Congruencias cuadráticas con módulos primos. 10.4 Congruencias cuadráticas con módulos no primos. 10.5 Congruencias con potencias y polinomios. 10.6 El Teorema de Wilson. 10.7 Congruencias mixtas. 11 Problemas de la tercera parte. → Archivo doc Cuarta parte: Exponenciación modular y sus aplicaciones. 12 Exponenciación modular. El problema del logaritmo discreto. → Archivo doc 12.1 Exponenciación modular. 12.2 Exponenciación modular optimizada (EMO). 12.3 El problema del logaritmo discreto (PLD). 12.4 Aplicación a la Criptografía: El sistema Diffie-Hellman (DH). 12.5 Aplicación a la Criptografía: El Criptosistema de ElGamal. 13 El pequeño Teorema de Fermat. El Teorema de Euler. → Archivo doc 13.1 El Pequeño Teorema de Fermat (PTF). 13.2 La función Phi de Euler. El Teorema de Euler. 13.3 Orden de un entero. 14 El problema de la primalidad. Encriptación RSA. → Archivo doc 14.1 El test de primalidad de Fermat. 14.2 Aplicación a la criptografía: El método RSA. 15 Raíces primitivas. Índices modulares. → Archivo doc 16 Problemas de la cuarta parte. → Archivo doc Quinta parte. Aplicaciones. 17 Números factoriales. → Archivo doc 18 Números combinatorios. → Archivo doc 19 Números primos de Fermat y de Mersenne. → Archivo doc 19.1 Números primos de Fermat. 19.2 Números primos de Mersenne. 20 Número y suma de divisores de un entero. → Archivo doc 20.1 Número de divisores de un entero. 20.2 Suma de los divisores de un entero. 20.3 Números perfectos. 21 Encriptación mediante Curvas Elípticas. Encriptación bitcoin. → Archivo doc 21.1 Curvas elípticas sobre cuerpos en general. 21.2 Curvas elípticas sobre cuerpos finitos. 21.3 Protocolo de intercambio de claves Diffie-Hellmann en Curvas Elípticas (ECDH). 22 Ecuaciones diofánticas. → Archivo doc 22.1 Ecuaciones diofánticas lineales. 22.2 Ternas pitagóricas. 22.3 La ecuación diofántica x 2 -y 2 =k. 22.4 La técnica del descenso infinito de Fermat. 22.5 El método de la contradicción modular. 22.6 Resolución de ecuaciones diofánticas mediante factorización. 22.7 Resolución de ecuaciones diofánticas aplicando desigualdades. 22.8 Ecuaciones diofánticas en competiciones olímpicas. 22.9 Cuadrados perfectos. 22.10 Ecuaciones de Frobenius. Problema de las monedas. Soluciones. → Archivo doc (1) , Archivo doc (2) , Archivo doc (3) El capítulo 14 del Libro de Desigualdades està dedicado a la aplicación de las desigualdades en la resolución de ecuaciones. http://www.toomates.net/biblioteca/Aritmetica10.doc http://www.toomates.net/biblioteca/Aritmetica11.doc http://www.toomates.net/biblioteca/Aritmetica12.doc http://www.toomates.net/biblioteca/Aritmetica13.doc http://www.toomates.net/biblioteca/Aritmetica14.dochttp://www.toomates.net/biblioteca/Aritmetica15.doc http://www.toomates.net/biblioteca/Aritmetica16.doc http://www.toomates.net/biblioteca/Aritmetica17.doc http://www.toomates.net/biblioteca/Aritmetica18.doc http://www.toomates.net/biblioteca/Aritmetica19.doc http://www.toomates.net/biblioteca/Aritmetica20.doc http://www.toomates.net/biblioteca/Aritmetica21.doc http://www.toomates.net/biblioteca/Aritmetica22.doc http://www.toomates.net/biblioteca/Aritmetica23.doc http://www.toomates.net/biblioteca/Aritmetica24.doc http://www.toomates.net/biblioteca/Aritmetica25.doc http://www.toomates.net/biblioteca/Desigualdades.pdf 1 Primeros pasos con los números enteros. La "Teoría de números" o "aritmética" estudia las propiedades de los números enteros. Los conceptos teóricos de esta rama de las matemáticas pueden ser complicados, muy complicados y terriblemente complicados. Sin embargo, muchos problemas se resuelven con solo utilizar el sentido común, toda una serie de estrategias y conceptos que, de tan obvios que son, los libros de teoría no dedican tiempo a explicarlos. En este primer apartado se incluyen problemas cuya resolución no necesita ningún concepto teórico previo, sólo el sentido común, la pura lógica, algunas formulitas de la matemática elemental y los conceptos de divibilidad aprendidos en primero de ESO. Sin embargo, no hay que despreciarlos. Es fundamental que el estudiante dedique a cada problema tanto tiempo como sea necesario, y si no llega a resolverlo, estudie detenidamente la solución que se presenta al final del libro. 1.1 Bases de numeración. Definición. Base de numeración. Diremos que n se escribe como 0121 ... aaaaa nnn en base 2b si 01 2 2 1 1 ... ababababan n n n n n n con bai 0 , INai , 0na . Por ejemplo, 3562 en base 7 es el número 13182767573 23 , y se escribe 73562 . 1.1.1 MF ¿Cuál de los siguientes enteros se puede expresar como la suma de 100 enteros positivos consecutivos? (A) 1,627,384,950 (B) 2,345,678,910 (C) 3,579,111,300 (D) 4,692,581,470 (E) 5,815,937,260 ASHME 1997 #20 1.1.2 M Consideremos el entero cifras N 321 99...99..9999999999 Calcula la suma de todas las cifras de N. AIME I 2019 #1 1.1.3 M Para cada entero positivo n , sea nd la cifra de las unidades de n ..321 . Determina el residuo cuando 2017 1n nd se divide entre 1000. AIME I 2017 #3 1.1.4 MF Sea 20 a , 51 a , 82 a , y para cada 2n , define na recursivamente como el residuo cuando 3214 nnn aaa se divide entre 11. Determina 202220202018 aaa . AIME II 2018 #2 1.1.5 F Multiplicamos todos los números pares del 2 al 98 inclusive, excepto aquellos acabados en 0. ¿Cuál será la cifra de las unidades del resultado? (A) 0 (B) 2 (C) 4 (D) 6 (E) 8 AMC10 1999 Sample #14 1.1.6 M Demostrar que si entre los infinitos términos de una progresión aritmética de números enteros hay un cuadrado perfecto, entonces infinitos términos de la progresión son cuadrados perfectos. OME 1993-94 (Primera sesión) #1 1.1.7 MF Un entero positivo N se representa como cba en base 11, y se representa como acb1 , donde cba ,, representan dígitos, no necesariamente distintos. Determina el valor mínimo de N expresado en base 10. AIME I 2020 #3 1.1.8 MF Sean yx , xy dos números enteros de dos dígitos. Demuestra que su suma es un número compuesto. 1.1.9 MF Problema solucionado paso a paso en vídeo. ¿Cuántos números naturales de tres dígitos tienen la propiedad de que cuando sus dígitos se escriben en orden inverso, el resultado es un número de tres dígitos que es 99 más que el número original? (A) 80 (B) 72 (C) 64 (D) 81 (E) 8 Cangur B2 2021 #13, Kangaroo Student 2021 #13 Solución: https://youtu.be/I_xh3ukx5DM 1.1.10 MF Determina la cifra de las unidades del producto (5 5 +1)·(5 10 +1)·(5 15 +1). (A) 6 (B) 5 (C) 3 (D) 1 (E) 0 Cangur B2 2023 #5, Canguro N6 2023 #10 https://youtu.be/I_xh3ukx5DM 1.1.11 F Problema solucionado paso a paso en vídeo. Determina la cantidad de números de dos dígitos con la siguiente propiedad: La suma de dicho número y el número obtenido invirtiendo el orden de sus dígitos es 132. (A) 5 (B) 7 (C) 9 (D) 11 (E) 12 AMC 8 2016 #11 Solución: https://youtu.be/I_xh3ukx5DM 1.1.12 MF La suma a + a + a + b + b + b + b de las siete cifras del número aaabbbb es igual al número de dos cifras ab . ¿Cuánto vale a + b ? (A) 10 (B) 11 (C) 8 (D) 9 (E) 12 Cangur B1 2019 #18, Canguro N5 2019 #18 1.1.13 MF Un palíndromo es un número que se lee de la misma forma hacia delante y hacia atrás. Determina el mayor entero menor de 1000 que es palíndromo tanto si es escrito en base 10 como si es escrito en base 8, por ejemplo, 292=444ocho. AIME II 2023 #2 https://youtu.be/I_xh3ukx5DM 1.2 Cuadrados perfectos. Potencias perfectas. Diremos que un entero n es un cuadrado perfecto cuando podamos encontrar otro entero m tal que 2mn . De la misma forma, diremos que n es un cubo perfecto cuando podamos encontrar otro entero m tal que 3mn . En general, si podemos escribir kmn diremos que n es una potencia perfecta de grado k. Los cuadrados perfectos son un tema recurrente en las competiciones matemáticas, y serán tratados a lo largo de este libro aplicando diversas técnicas. Por ejemplo, en 7.3.9 se ofrece un cuadro de las caracterizaciones de ciertas potencias perfectas cuando se trabaja con aritmética modular. Veamos aquí un problema motivador para que el estudiante analice la relación entre cuadrados perfectos y la cantidad de divisores de un número: 1.2.1 Veinte estudiantes aburridos se dedican a abrir y cerrar las taquillas de un vestuario, numeradas del 1 al 20. El primer estudiante abre todas las taquillas; el segundo estudiante cierra todas las taquillas numeradas 2, 4, 6, 8, 10, 12, 14, 16, 18; El tercer estudiante se dedica a las taquillas numeradas 3, 6, 9, 12, 15 y 18, si las encuentra abiertas, las cierra, y si las encuentra cerradas, las abre. En general, el estudiante número k se dedica a las taquillas múltiples de k: Si las encuentra abiertas, las cierra, y si las encuentra abiertas, las abre. Determina las taquillas que quedarán abiertas después de que hayan pasado los veiente estudiantes. 1.3 Orden en los números enteros. Principio de inducción. Principio de la buena ordenación. Todo conjunto S de números enteros no negativos contiene un elemento mínimo, es decir, existe un elemento Sa tal que ba para todo Sb . 1.3.1 D Demostrar que, si ba, son enteros positivos tales que ab ba 1 22 es un entero, entonces ab ba 1 22 es un cuadrado perfecto. IMO 1988 #6 Teorema. Propiedad arquimediana de los números naturales. Si a y b son números enteros positivos, entonces existe un entero positivo n tal que ban . Demostración. Supongamos que no es cierto, es decir, que existen dos números 0, ba tales que ban para todo 0n . Consideremos el conjunto 0, nanbS . Está claro que es un subconjunto de números enteros positivos, pues nabban 0 , y por tanto le podemos aplicar el Principio de la buena ordenación, es decir, contendrá un elemento mínimo amb , para cierto 0m . Pero, por hipótesis, amb )1( también pertenecerá a S, luego: mabamabamb )1( , pues 1a , luego amb no puede ser el mínimo, llegando a contradicción. Así pues, la propiedad arquimediana de los números naturales debe ser cierta, pues su negación nos lleva a contradicción. Principio de Inducción. Sea S un conjunto de números enteros positivos cumpliendo las dos condiciones siguientes: a) 1 pertenece a S. b) Si Sn , entoncesSn 1 Entonces S es el conjunto de todos los enteros positivos: ...,3,2,1S Demostración. Sea ST ...,3,2,1 , y supongamos que T , es decir, que no está vacío, o lo que es lo mismo, que no se cumple el Principio de Inducción. Aplicando el Principio de la buena ordenación, T contendrá elemento mínimo, llamémosle a . Puesto que T1 , pues por hipótesis, S1 , está claro que 1a , luego aa 10 . El número 1a tampoco pertenecerá a S, pues si SaaSa 111 , contradiciendo la hipótesis. Pero aa 1 , llegando a contradicción, pues habíamos supuesto que a era mínimo. El principio de inducción es una herramienta muy poderosa para demostrar fórmulas que nos serán muy útiles para solucionar una enorme variedad de problemas. Ejemplo. 6 )1)(12( ...321 2222 nnn n para todo ...,3,2,1n Demostración. Sea S el conjunto de números enteros positivos para los que la fórmula anterior es cierta. Está claro que 1 pertenece a S, pues 6 )11)(112(1 112 Supongamos que la fórmula anterior se cumple para un cierto valor n , y veamos que, entonces, se cumplirá también para 1n : (*) 6 )1(6)12( )1( )1( 6 )12( )1()1( 6 )1)(12( 1...321 2 22222 nnn n n nn nn nnn nn )32)(2(672662)1(6)12( 22 nnnnnnnnnn 6 )11)(1)1(2)(1( 6 )32)(2)(1( 6 )32)(2( )1((*) nnnnnnnn n 6 )1)(12( kkk , tomando 1 nk , luego la fórmula también es válida para 1n . Así pues, ...,3,2,1S , es decir, la fórmula es válida para todos los enteros positivos. 2 Primeros pasos con Python. 2.1 Instalación del IDE spyder. Instalación del entorno de programación (IDE) de Phyton “spyder”. Primero descargamos e instalamos en nuestro ordenador la última versión del entorno spyder (178 Mb) de la web https://www.spyder-ide.org/ Una vez instalado el programa, ejecutamos el entorno Spyder: ¿Por qué spyder y no cualquier otro IDE de Python? No hay ningún motivo. Es el primer IDE de Python que he encontrado con Google y he podido instalar correctamente en mi portatil HP Presario CQ57 Notebook con AMD 1.30Ghz y 2 Gb de RAM, con Windows 7 Home Premium 64 bits. Todos los problemas de este libro se pueden ejecutar en cualquier entorno de programación Python. https://www.spyder-ide.org/ El entorno de programación spyder. Al ejecutar spyder nos tiene que aparecer una pantalla como esta: Siempre trabajaremos de la misma manera: Primer paso: Escribiremos el programa en la columna de la izquierda. ↓ Segundo paso: Ejecutaremos el programa pulsando el botón “Play” de la barra de comandos: o pulsando la tecla “F5” ↓ Tercer paso: Vemos el resultado en la columna de la derecha. Programa 1. Visualizar resultados. La función más importante de todo lenguaje de programación es print: Muestra algo por pantalla (un texto, un número, el resultado de una operación…) # # Este es mi primer programa en Phyton # print("Hola a todos") Recuerda los tres pasos: Las tres primeras empiezan con “almohadilla” # y son comentarios: No hacen nada, solo sirven de título. Debemos acostumbrarnos a poner en nuestros programas comentarios, pues hacen que el programa sea más legible y agradable. Programa 2. Los inevitables errores de sintaxis. La única manera de aprender a programar es estudiando ejemplos, copiando ejemplos... y después jugar con ellos: hacer pequeñas modificaciones... Preguntarnos ¿Qué pasaría si cambio esto? Y ver qué pasa... Es inevitable que aparezcan errores, que nos equivoquemos en algo. ¡No pasa nada! Buscamos donde está el error y lo rectificamos, y de esta manera aprendemos. Por ejemplo: Modificamos el programa anterior: # # Este es mi primer programa en Phyton # print("Hola a todo el mundo) Lo ejecutamos y ¡oh! vemos que da error: ¿Qué habrá pasado? Estudiamos el código: Nos hemos equivocado al no cerrar con comillas la frase que queríamos visualizar. La rectificamos y volvemos a ejecutar el programa. Vemos que ahora sí está bien: Practicar es obligatorio. Equivocarse es inevitable. 2.2 Operaciones aritméticas con Python. Utilizaremos el operador "+" para la suma de dos números: print(7+2) Salida: 9 Utilizaremos el operador "+" para la resta de dos números: print(7-2) Salida: 95 Utilizaremos el operador "*" para la multiplicación de dos números: print(7*2) Salida: 14 Utilizaremos el operador "/" para la división con decimales de dos números: print(7/2) Salida: 3.5 Utilizaremos el operador "//" para determinar el cociente de la división exacta de dos números: print(7//2) Salida: 3 Utilizaremos el operador "%" para determinar el residuo de la división exacta de dos números: print(7%2) Salida: 1 Utilizaremos el operador "**" para determinar potencias: print(7**2) Salida: 49 A partir de la versión 3.8 de Python incorpora, a partir de la versión 3.8, una función específica de exponenciación modular: print(pow(2,6,11)) Salida: 9 Programa 3. La operación "residuo de la división". Sabemos que una operación muy importante en criptografía es hacer el residuo de una división entera. En Python esta operación se codifica mendiante el operador %. Observa y ejecuta el siguiente programa: # # Este es mi segundo programa de Python # print(19%5) Una vez ejecutado, te tiene que aparecer en pantalla el resultado: 4 Desde un punto de vista matemático acabamos de hacer 5mod419 Programa 4. Las variables. El objeto más importante de todo lenguaje de programación son las variables. Una variable contiene una partícula de información que el ordenador almacena y puede modificar. Las variables se definen mediante letras o palabras. # # Este es mi tercer programa de Python # n=42 print(n%5) Te tiene que aparecer el resultado correcto: 2. Desde un punto de vista matemático acabamos de hacer 5mod242 Programa 5. Bucles. Mediante un bucle le pedimos al ordenador que repita una determinada acción, dando a una determinada variable un rango: Desde un valor inicial hasta un determinado valor final. Por ejemplo, queremos calcular los equivalentes modulares módulo 5 de todos los números del 0 al 12: # # Los equivalentes modulares módulo 5 del 0 al 12 # for i in range (0,12): print(i%5) print("Final") Programa 6. Mejorando la presentación. La presentación quedará más elegante si añadimos algún texto: # # Los equivalentes modulares módulo 5 del 0 al 12 # for i in range (0,12): print(i," = ", i%5, " (mod 5)") print("Final") Programa 7. Tabla de la suma modular. Podemos hacer un programa que calcule la tabla de la suma de un determinado número. # # Tabla de la suma módulo 7 de un número. # a=3 print("La tabla de la suma del ",a," módulo 7") for i in range (0,6): print(a,"+", i, "=" ,(a+i)%7 , " (mod 7)") print("Final") Programa 8. Tabla de la multiplicación modular. Para la operación multiplicar se utiliza el símbolo asterisco: * El siguiente programa muestra la tabla de multiplicar módulo 7 de un determinado número. # # Tabla de la multiplicación módulo 7 de un número. # a=3 print("La tabla de la suma del ",a," módulo 7") for i in range (0,6): print(a,"*", i, "=" ,(a*i)%7 , " (mod 7)") print("Final") 2.2.1 Ejercicio. Realiza un programa Python que genere la tabla de la suma módulo 13 del número 4. 2.2.2 Ejercicio. Modifica el programa anterior para que genere la tabla de la multiplicación módulo 13 del número 4. 3 Problemas de la primeraparte. 3.1 F Tenemos tres cartulinas y en cada una se ha escrito un número de cinco cifras. Como se ve en la figura tres de las cifras están tapadas. La suma de los tres números es 57263. ¿Cuáles son las cifras ocultas? A) 0, 2 y 2 B) 1, 2 y 9 C) 2, 4 y 9 D) 2, 7 y 8 E) 5, 7 y 8 Canguro N5 2019 #10, Cangur B1 2019 #10 3.2 F Los enteros positivos a, b y c tienen cada uno tres cifras, y en cada entero la primera cifra es la misma que la última. También cumplen que 12 ab y 12 bc . ¿Cuántos valores distintos hay para el entero a? A) 0 B) 1 C) 2 D) 3 E) más de 3 Canguro N5 2019 #26, Cangur B1 2019 #26 3.3 F Tenemos tres cartulinas y en cada una se ha escrito un número de cuatro cifras. Como se ve en la figura tres de las cifras están tapadas. La suma de los tres enteros de cuatro cifras es 11126. ¿Cuáles son las cifras ocultas? A) 1, 4 y 7 B) 1, 5 y 7 C) 3, 3 y 3 D) 4, 5 y 6 E) 4, 5 y 7 Canguro N6 2019 #6, Cangur B2 2019 #6 3.4 F ¿Cuál es la primera cifra (la situada más a la izquierda) del número entero positivo más pequeño cuyas cifras suman 2019? A) 2 B) 3 C) 4 D) 5 E) 6 Canguro N6 2019 #7, Cangur B2 2019 #7 3.5 F Un gráfico consta de 16 vértices y algunos segmentos que los conectan, como en la imagen. Ahora hay una hormiga en el vértice A. En cada movimiento, puede caminar desde un vértice a cualquier vértice vecino a lo largo de un segmento de conexión. ¿En cuál de los vértices P, Q, R, S, T puede estar la hormiga después de 2019 movimientos? A) sólo P, R o S, no Q y T B) sólo P, R, S o T, no Q C) sólo Q D) sólo T E) en cualquiera Canguro N5 2019 #25, Cangur B1 2019 #25 3.6 M Dado un entero positivo n , sea )(nf la suma de los dígitos de la representación de n en base cuatro, y sea )(ng la suma de los dígitos de la representación de )(nf en base ocho. Por ejemplo: 84 1210133210)2020( ff , y 321)2020( g . Determina el valor mínimo de n de forma que la representación en base 16 de )(ng no pueda ser representada usando solo los dígitos 0 a 9. AIME II 2020 #5 3.7 MF Los 25 enteros entre -10 y 14, inclusive, se pueden organizar para formar un cuadrado de 5 por 5 en el que la suma de los números de cada fila, de cada columna y de las dos diagonales sumen lo mismo. ¿Cuál es el valor de esta suma común? (A) 2 (B) 5 (C) 10 (D) 25 (E) 50 AMC 12A 2020 #5 3.8 M Determina el número de pares ordenados ),( yx de enteros que satisfacen la ecuación yyx 222020 (A) 1 (B) 2 (C) 3 (D) 4 (E) hay infinitos pares AMC 12B 2020 #8 3.9 M Sean a y b números reales positivos cumpliendo la condición 100loglogloglog baba y en donde los cuatro términos de la izquierda son enteros positivos, denotando por log el logaritmo en base 10. Determina ab . (A) 5210 (B) 10010 (C) 14410 (D) 16410 (E) 20010 AMC 12A 2019 #15 3.10 F Determina la cantidad de números enteros no negativos que se pueden escribir de la forma 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 33333333 aaaaaaaa donde 1,0,1ia para todo 70 i . (A) 512 (B) 729 (C) 1094 (D) 3281 (E) 59048 AMC 12A 2018 #13 3.11 M Sea el triángulo ABC de lados 9AB , 35BC y 12AC . Marcamos los puntos BPPPPA 2450210 ,...,,, en el segmento AB de forma que kP se encuentra entre 1kP y 1kP para todo 2449,...,2,1k , y marcamos los puntos CQQQQA 2450210 ,...,,, en el segmento AC de forma que kQ se encuentra entre 1kQ y 1kQ para todo 2449,...,2,1k . Además, todo segmento kkQP , con 2449,...,2,1k , es paralelo a BC . Estos segmentos cortan el triángulo en 2450 regiones, consistiendo en 2449 trapecios y un triángulo. Todas estas 2450 regiones tienen el mismo área. Determina el número de segmentos kkQP , con 2450,...,2,1k cuya longitud es racional. AIME II 2018 #7 3.12 F Se toma aleatoriamente un número m del conjunto 19,17,15,13,11 , y se toma aleatoriamente un número n del conjunto 2018...,,2001,2000,1999 . Determina la probabilidad de la cifra de las unidades de nm sea 1. (A) 5 1 (B) 4 1 (C) 10 3 (D) 20 7 (E) 5 2 AMC 10A 2018 #19 3.13 D Utilizando la igualdad 129753473 22 , escribe 1297 como suma de dos cuadrados. 3.14 M Determina la expresión equivalente a 646432321616884422 32323232323232 (A) 127127 23 (B) 6363127127 233223 (C) 128128 23 (D) 128128 33 (E) 1275 AMC 10A 2021 #10 3.15 MF La suma de los cinco números de tres cifras ABC, BCD, CDE, DEA y EAB es 2664. ¿Cuál es el valor de la suma de las cifras A, B, C, D y E? A) 4 B) 14 C) 24 D) 34 E) 44 Canguro N6 2020 #5, Cangur B2 2020 #5 3.16 MF Sean a, b y c enteros que satisfacen cba 1 y 1000000 cba . ¿Cuál es el mayor valor posible de b? A) 100 B) 250 C) 500 D) 1000 E) 2000 Canguro N6 2020 #7, Cangur B2 2020 #7 3.17 F Sean a, b y c tres números enteros. ¿Cuál de los siguientes valores nunca puede ser igual a 222 )()( accbba ? A) 0 B) 1 C) 2 D) 6 E) 8 Canguro N6 2020 #14, Cangur B2 2020 #14 3.18 F El número entero 29...... tiene 100 cifras. ¿Cuántas cifras tiene su cuadrado? A) 101 B) 199 C) 200 D) 201 E) no se puede saber Canguro N6 2020 #15, Cangur B2 2020 #15 3.19 F La sucesión nf viene dada por 11 f , 32 f y 12 nnn fff para 1n . ¿Cuántos de los primeros 2020 términos de la sucesión son pares? A) 673 B) 674 C) 1010 D) 1011 E) 1347 Canguro N6 2020 #18, Cangur B2 2020 #18 3.20 MF En los cálculos mostrados, cada letra representa una cifra y se usan para formar algunos números de dos cifras. Los dos números de la izquierda suman 79. ¿Cuál es la suma de los cuatro números de la derecha? A) 79 B) 158 C) 869 D) 1418 E) 7979 Canguro N5 2020 #5, Cangur B1 2020 #5 3.21 MF La suma de cuatro enteros consecutivos es 2. ¿Cuál es el menor de estos enteros? A) -3 B) -2 C) -1 D) 0 E) 1 Canguro N5 2020 #6, Cangur N5 2020 #6 3.22 MF Los años 2020 y 1717 se forman con un número de dos cifras repetido dos veces. ¿Cuántos años transcurrirán a partir de 2020 para encontrarnos en el siguiente año que tenga esta misma propiedad? A) 20 B) 101 C) 120 D) 121 E) 202 Canguro N5 2020 #7, Cangur B1 2020 #1, Kangaroo Junior 2020 #7 3.23 MF El camino más corto para ir de A a C pasa por B. Paseando por este camino de A a C, primero encontramos en el lado izquierdo del camino el poste de señales que se muestra a la izquierda de la figura, y después, en el lado derecho del camino el otro poste. ¿Qué distancia estaba escrita en el cartel roto? A) 1 km B) 2 km C) 3 km D) 4 km E) 5 km Canguro N5 2020 #13, Cangur N5 2020 #13 3.24 F En cada una de las nueve celdas de la figura se escribe un número de modo que la suma de los tres números en cada diámetro es 13 y la suma de los ocho números en la circunferencia es 40. ¿Qué número debe escribirse en la celda central? A) 3 B) 5 C) 8 D) 10 E) 12 Canguro N5 2020 #15, Cangur B1 2020 #15 3.25 MF Lucas comienza un viaje de 520 km en coche con 14 litros de combustible en el depósito. Su automóvil consume 1 litro de combustible por cada 10 km. Después de conducir 55 km, lee una señal de tráfico que muestra las distancias desde ese punto hasta cinco estaciones de servicio en la carretera. Estas distancias son 35 km, 45 km, 55 km, 75 km y 95 km. La capacidad del depósito de combustible del coche es de 40 litros y Lucas quiere detenerse solo una vez para llenarlo. ¿A qué distancia está la estación deservicio donde debe repostar? A) 35 km B) 45 km C) 55 km D) 75 km E) 95 km Canguro N5 2020 #18, Cangur B1 2020 #18 3.26 F Carmen etiquetó los vértices de una pirámide de base cuadrada con los números 1, 2, 3, 4 y 5, uno para cada vértice. Para cada cara calculó la suma de los números en sus vértices. Cuatro de estas sumas son 7, 8, 9 y 10. ¿Cuál es la quinta suma? A) 11 B) 12 C) 13 D) 14 E) 15 Canguro N5 2020 #25, Cangur B1 2020 #25 3.27 F En cada una de las celdas de una tabla se escribe un número, de manera que las sumas de los 4 números en cada fila y en cada columna sean iguales. ¿Qué número tiene la celda sombreada? A) 5 B) 6 C) 7 D) 8 E) 9 Canguro N5 2020 #27, Cangur B1 2020 #27 3.28 F Determina las soluciones enteras de la ecuación 4 3111 cba con cba 1 Olimpiada Matemática de Chile 2011 3.29 MD Sea 100n un entero. Iván escribe cada uno de los números n , n+1 , . . . , 2n en un naipe diferente. Después de barajar estos n+1 naipes, los divide en dos pilas distintas. Probar que al menos una de esas pilas contiene dos naipes tales que la suma de sus números es un cuadrado perfecto. IMO 2021 #1 3.30 F Determina la cifra de las unidades de 200313 . (A) 1 (B) 3 (C) 7 (D) 8 (E) 9 AMC 10A 2003 #16 Nota: En el apartado 7.6 aparecen más problemas del tipo “Determina la cifra de las unidades de...” 3.31 MF ¿Cuál es la última cifra del número 12345 54321 + 1 (A) 1 (B) 5 (C) 6 (D) 2 (E) 0 Canguro N4 2002 #1 3.32 MF Sean p y q dos números primos tales que 36522 qp . ¿Cuánto vale qp ? (A) 20 (B) 21 (C) 22 (D) 23 (E) 24 Canguro N4 2013 #4 3.33 M Determina la raíz cuadrada del número de 4044 dígitos siguiente: 98...8884...444 20212022 dígitosdígitos 3.34 D Sean cba ,, números naturales tales que 32223222 cbaabcacbacbcabcab Demostrar que al menos uno de los números cba ,, es un cuadrado perfecto. OMEFL Castilla y León 2021 #1 3.35 MF ¿De cuantas formas diferentes se pueden combinar billetes de 5$ y de 2$ para obtener 17$, sin importar el orden? (A) 2 (B) 3 (C) 4 (D) 5 (E) 6 AMC 8 2002 #2 3.36 F Julia divide el número cifras2004 1...111 entre 3. El número de ceros que obtendrá será de (A) 670 (B) 669 (C) 668 (D) 667 (E) 665 Cangur N1 2004 #27 3.37 M Determina el entero positivo de tres dígitos cba cuya representación en base nueve es 9(acb , donde a, b y c son dígitos no necesariamente distintos. AIME I 2022 #1 3.38 M Sean ihgfedcba ,,,,,,,, enteros diferentes entre 1 y 9. El menor valor positivo posible de ihg fedcba se puede escribir como n m , donde m y n son enteros positivos y coprimos. Determina nm . AIME I 2022 #7 3.39 F Los números del 1 al 10 se escriben en los círculos de la figura, uno en cada círculo. La suma de los números de la fila superior es 24, la suma de los números de la fila inferior también es 24, y la suma de los números de la columna de la izquierda es 25. ¿Cuál es el número que puede figurar en el círculo con la interrogación? (A) 6 (B) 5 (C) 4 (D) 2 (E) Ninguno de los valores anteriores Cangur B2 2022 #23 3.40 F Problema solucionado paso a paso en vídeo. Determina la cantidad de parejas ordenadas cb, de enteros positivos para los que ni 02 cbxx ni 02 bcxx tienen dos soluciones reales distintas. (A) 4 (B) 6 (C) 8 (D) 12 (E) 16 AMC 12A Fall 2021 #17, AMC 10A 2021 #20 Solución: https://youtu.be/01bMBnbkUmc 3.41 F Sea N el entero positivo más pequeño cuya suma de sus dígitos sea 2021. ¿Cuál es la suma de los dígitos de N + 2021? (A) 2021 (B) 2026 (C) 10 (D) 4042 (E) 12 Cangur B1 2021 #23, Kangaroo Junior 2021 #23 3.42 MF ¿Cuántos números de 3 dígitos se pueden formar utilizando los dígitos 1,3 y 5 y que sean divisibles por 3? Puedes utilizar un dígito más de una vez. (A) 6 (B) 27 (C) 18 (D) 7 (E) 9 Cangur B2 2021 #8, Kangaroo Student 2021 #8 https://youtu.be/01bMBnbkUmc 3.43 MF David escribe, en orden creciente, todos los números enteros del 2 al 2022 que usan solo 0 y 2. ¿Cuál es el número que se encuentra en el medio de su lista? (A) 200 (B) 220 (C) 222 (D) 2000 (E) 2002 Cangur B2 2022 #6, Kangaroo Student 2022 #8 3.44 M Un gimnasio tiene doce pesas diferentes de 1 kg a 12 kg, todas de números enteros. Las divide en tres grupos de cuatro pesas cada uno. El peso total del primer grupo es de 41 kg y del segundo de 26 kg. ¿Cuál de las siguientes pesas está en el mismo grupo que la pesa de 9 kg? (A) 3 kg (B) 7 kg (C) 5 kg (D) 10 kg (E) 8 kg Cangur B1 2022 #26, Kangaroo Junior 2022 #25 3.45 F Para un entero positivo N, denotamos por p(N) el producto de los dígitos de N cuando se escriben en forma decimal. Por ejemplo, p(23) = 2 × 3 = 6. ¿Cuál es el valor de la suma p(10) + p(11) + p(12) + ... + p(99) + p(100) ? (A) 5050 (B) 4050 (C) 5005 (D) 2025 (E) 4500 Cangur B2 2021 #16 3.46 F Los números 1, 2, 7, 9, 10, 15 y 19 están escritos en una pizarra. Dos jugadores se alternan para eliminan un número hasta que solo quede un número en la pizarra. La suma de los números eliminados por uno de los jugadores es el doble de la suma de los números eliminados por el otro jugador. ¿Cuál es el número que queda? (A) 7 (B) 10 (C) 9 (D) 19 (E) 15 Cangur B2 2021 #22, Kangaroo Student 2021 #22 3.47 F Los números del 1 al 6 se colocan en los círculos en las intersecciones de tres anillos circulares. Se muestra la posición del número 6. Las sumas de los números de cada anillo son las mismas. ¿Qué número se coloca en el círculo con el signo de interrogación? (A) 5 (B) 1 (C) 3 (D) 2 (E) 4 Cangur B1 2021 #13, Kangaroo Junior 2021 #13 3.48 F En una cuadrícula 5×5 como se muestra, la suma de los números en cada fila y en cada columna es la misma. Hay un número en cada celda, pero algunos de los números no se muestran. ¿Cuál es el número en la celda marcada con un signo de interrogación? (A) 23 (B) 8 (C) 10 (D) 18 (E) 12 Cangur B2 2021 #17, Kangaroo Junior 2021 #17 3.49 F ¿Cuántos enteros positivos de tres cifras abc hay, tales que (a+b) c es un entero de tres cifras que además es una potencia de 2? (A) 15 (B) 16 (C) 18 (D) 20 (E) 21 Canguro N6 2017 #29, Cangur B2 2017 #29, Kangaroo Student 2017 #29 3.50 F Ocho equipos participan en un torneo de fútbol. Cada equipo juega contra otro equipo exactamente una vez. En cada partido, el ganador obtiene 3 puntos y el perdedor no obtiene ningún punto. Si se empata un partido, cada equipo obtiene 1 punto. Al final del torneo el número total de puntos obtenidos por todos los equipos es de 61. ¿Cuál es el mayor número de puntos que podría haber obtenido el equipo campeón? (A) 21 (B) 19 (C) 18 (D) 17 (E) 16 Cangur B1 2022 #22, Kangaroo Junior 2022 #29 3.51 MF La suma de las dos últimas cifras del resultado del producto 1 · 2 · 3 · 4 · 5 · 4 · 3 · 2 · 1 es: (A) 8 (B) 2 (C) 16 (D) 4 (E) 6 Cangur B2 2020 #1, Canguro N6 2020 #1 3.52 F Determina todos los enteros positivos n para los cuales 652 nn es un cuadrado perfecto. OME Fase local Catalunya 2023 #1 3.53 MF Julia tira 5 dados y obtiene un total de 19 puntos. ¿Cuál es el número máximo de seises que puede haber obtenido? (A) 0 (B) 1 (C) 2 (D) 3 (E) 4 Cangur B2 2023 #2, Canguro N6 2023 #2 3.54 MF Determina el número de enteros positivos x, y que satisfacen la ecuación 1022 yx . (A) 2 9 −1 (B) 2 9 (C) 2 9 +1(D) 2 9 +2 (E) 0 Cangur B2 2023 #7, Canguro N6 2023 #6 3.55 MF Encima de un reloj se pone un círculo gris con dos agujeros, tal y como se puede ver en la figura. Hacemos girar este círculo alrededor de su centro de forma que el número 10 aparece en uno de sus agujeros. ¿Qué otros dos números pueden aparecer en el otro agujero? (A) El 2 o el 6 (B) El 3 o el 7 (C) El 3 o el 6 (D) El 1 o el 9 (E) El 2 o el 7 Cangur B1 2023 #1, Canguro N5 2023 #1 3.56 MF Si m y n son dos números enteros positivos impares, ¿Cual de los siguientes números es también impar? (A) m·(n+1) (B) (m+1)·(n+1) (C) m+n+2 (D) m·n+2 (E) m+n Cangur B1 2023 #3, Canguro N5 2023 #3 3.57 MF Las edades de una familia formada por cinco miembros suman 80 años. Las dos personas más jóvenes tienen 6 y 8 años. ¿Cuál era la suma de las edades de los miembros de esta familia hace 7 años? (A) 35 (B) 36 (C) 45 (D) 46 (E) 66 Cangur B1 2023 #7, Canguro N5 2023 #7 3.58 F Después de haber jugado 200 partidas de ajedrez, he ganado exactamente un 49%. ¿Cuál es el mínimo número de partidas adicionales que tendré que jugar para que mi porcentaje de partidas ganadas pueda aumentar hasta un 50%? (A) 1 (B) 2 (C) 3 (D) 4 (E) 6 Cangur B1 2023 #10, Canguro N5 2023 #10 3.59 MF Una cerca de madera está construida con tablones verticales y horizontales. Cada dos tablones verticales consecutivos están unidos por 4 tablones horizontales. ¿Cuál de las siguientes cantidades puede corresponder al número de tablones de la cerca? (A) 95 (B) 96 (C) 97 (D) 98 (E) 99 Cangur B1 2023 #8, Canguro N5 2023 #8 3.60 M Determina todos los números primos que se pueden expresar como suma y diferencia de dos números primos. New Zeland M.O. Camp 2013 4 Divisibilidad, máximo común divisor y mínimo común múltiplo. 4.1 Concepto de divisibilidad. Definición. Divisor de un número. Dados dos números enteros ba, , diremos que a divide a b, o que b es divisible entre a, y escribiremos ba | , cuando exista un tercer número entero c tal que bca . Puesto que 00 a , todo número entero es divisor de cero, incluso 0|0 . Proposición. Propiedades básicas de la divisibilidad. a) aa | para todo entero a (propiedad reflexiva) b) ba | y c|b ca | (propiedad transitiva) c) cybxaayba |c|| para cualquier par de enteros yx, d) bdacdcyba ||| . En particular, cbaba || . e) ba | y cacba || Observación. naa | , y por tanto cacan || , por la propiedad transitiva: cacaa n ||| Criterios básicos de divisibilidad. Entre 2: Cuando acaba en cero o cifra par. Entre 3: Cuando la suma de sus cifras es múltiplo de 3. Entre 4: Cuando el número formado con sus dos últimas cifras es un múltiplo de 4. Entre 5: Cuando acaba en 0 o en 5. Entre 9: Cuando la suma de sus cifras es múltiplo de 9. Entre 11: Cuando la diferencia entre la suma de sus cifras pares y la suma de sus cifras impares sea 0 o múltiplo de 11. Teorema. Algoritmo de la división. Para todo Za y Nb , existen Zq y br 0 únicos, llamados respectivamente cociente y residuo de la división, tales que rbqa Problema resuelto. Aplicando el Algoritmo de la división, demuestra que todo cuadrado perfecto es siempre de la forma k4 o 14 k . Solución. Aplicando el Algoritmo de la división, todo número n será de la forma 1)1(414434,24,14,4 bbbnbnbnbn . Veamos su cuadrado, caso por caso: )144(4416162424 1)24(418161414 4444 2222 2222 222 bbbbbnbn bbbbbnbn bbnbn Sea cual sea el caso, siempre es de la forma k4 o 14 k . Nota: Este resultado es muy útil para resolver muchos problemas de ecuaciones diofánticas. Nota: Ver 7.3.9 para más resultados como este, utilizando el lenguaje de la aritmética modular. 4.1.1 MF El número de dígitos de 251654 (cuando está escrito en la base 10 usual) es (A) 31 (B) 30 (C) 29 (D) 28 (E) 27 AHSME 1984 #9 4.1.2 F Demuestra que el cuadrado de un número impar es siempre de la forma 18 k OPOS BALEARES 2018 4.1.3 F El perímetro de un triángulo equilátero excede el perímetro de un cuadrado en 1989 cm. La longitud de cada lado del triángulo excede la longitud de cada lado del cuadrado en d cm. El cuadrado tiene perímetro mayor que 0. ¿Cuántos posibles enteros positivos no son válidos para d? (A) 0 (B) 9 (C) 221 (D) 663 (E) infinitos ASHME 1989 #17 4.1.4 F ¿Cuántos números en base 10, dcbaN satisfacen todas las tres condiciones siguientes? (i) 60004000 N (ii) N es múltiplo de 5 (iii) 63 cb (A) 10 (B) 18 (C) 24 (D) 36 (E) 48 AHSME 1995 #12 4.1.5 F La profesora Walter corrige un examen de matemáticas de sus cinco alumnos. Entra en orden aleatorio las puntuaciones en una hoja de cálculo, que va recalculando la media de la clase después de cada puntuación (sobre el número de alumnos ya introducidos, no sobre el total de 5). La profesora se da cuenta de que, después de cada puntuación, la media es siempre un entero. Las puntuaciones (presentadas en orden ascendente) son 71, 76, 80, 82 y 91. ¿Cuál fue la última puntuación que introdujo la profesora Walter? (A) 71 (B) 76 (C) 80 (D) 82 (E) 91 AMC12 2000 #9 4.1.6 F Determina los valores enteros de x para los cuales la expresión xx 62 es un cuadrado perfecto, es decir, el cuadrado de un entero. 4.1.7 M Determina la suma de todos los números enteros positivos 1000b tal que el número b36 (escrito en base b) es un cuadrado perfecto y el número b27 (también escrito en base b) es un cubo perfecto. AIME II 2018 #3 4.1.8 F Determina la suma de todos los enteros positivos n tales que 2017852 nn es un entero. AIME II 2017 #6 4.1.9 F Demuestra que ningún número de la forma ...,11111,1111,111,11 es un cuadrado perfecto. Indicación: Todo número de la forma 111...111 se puede escribir como 343108...111111...111 k . 4.1.10 MF ¿Para cuantos enteros n entre 1 y 100 el polinomio nxx 2 factoriza en el producto de dos factores lineales con coeficientes enteros? (A) 0 (B) 1 (C) 2 (D) 9 (E) 10 ASHME 1989 #8 4.1.11 F Sea S el número de pares ordenados de enteros ),( ba con 1001 a y 0b tales que el polinomio baxx 2 pueda ser factorizado como producto de dos (no necesariamente distintos) factores lineales con coeficientes enteros. Determina el residuo cuando S se divide entre 1000. AIME I 2018 #1 4.1.12 F Una sucesión pucelana es una sucesión crecientes de dieciséis números impares positivos consecutivos, cuya suma es un cubo perfecto. ¿Cuántas sucesiones pucelanas tienen solamente números de tres cifras? OME 2010 #1 4.1.13 M a) Demuestra que el producto de dos números consecutivos es par. b) Demuestra que el producto de tres números consecutivos es divisible entre 6. c) Demuestra que nn 5 es divisible entre 30. 4.1.14 F Determina la suma de todos los números primos entre 1 y 100 tal que sean simultáneamente 1 mayor que un múltiplo de 4 y 1 menor que un múltiplo de 5 ASHME 1999 #4 4.1.15 MF ¿Cuántos enteros positivos b existen con la propiedad de que 729log b sea un entero positivo? (A) 0 (B) 1 (C) 2 (D) 3 (E) 4 AMC12 2000 #7 4.1.16 F Aplicando el Algoritmo de la división, demuestra que: a) Un cuadrado perfecto es siempre de la forma k3 o 13 k . b) Un número de la forma 13 2 a nunca puede ser un cuadrado perfecto. 4.1.17 F ¿Para cuántos enteros N entre 1 y 1990 la fracción impropia 4 72 N N no es irreducible? ASHME 1990 #19 4.1.18 MF Sea r el residuo cuando 1059, 1417 y 2312 se dividen entre 1d . Determina el valor de rd . AHSME 1976#15 4.1.19 F Demuestra que existen infinitos números enteros n tales que 232 n es divisible por 24. 4.1.20 M Determina todos los enteros positivos d tales que d divide 12 n y 1)1( 2 n para algún entero n. 4.1.21 F Determina todos los enteros positivos n tales que el número que se obtiene eliminando el último dígito es un divisor de n . 4.1.22 F Calcula la suma de todos los enteros positivos n para los cuales la expresión 1 7 n n es un entero. HMMT 2021 #1 4.2 Divisibilidad y orden. Proposición. Divisibilidad implica desigualdad. a) Si ba | y 0b ba . Y por tanto, si a y b son positivos: b) 11| aa c) baba | d) ba | y ab | ba e) baba | 4.2.1 F Sean ndddd k ...1 321 los divisores del entero positivo n. Encuentra todos los números n tales que 3 3 2 2 ddn . México 2008 4.2.2 M Sea 1931 32n . Determina el número de enteros positivos de 2n que sean menores que n y que no sean divisores de n . AIME 1995 #6 Indicación: Distribución de los divisores de 2n . Un dato que puede ser útil es que n es el divisor central de 2n , es decir, el número de divisores de 2n menores que n es igual al número de divisores de 2n mayores que n. 4.2.3 D Encontrar las ternas nba ,, de números enteros positivos tales que ba n ba 11 . 4.2.4 M Dado INn , calcula la longitud del lado BC en el triángulo que se muestra en la siguiente figura. ¿Existe algún valor de n para el que la longitud BC sea entero? 4.2.5 F Sea n un número de cinco dígitos, y sean q y r el cociente y el residuo, respectivamente, cuando n se divide entre 100. ¿Para cuántos valores de n se cumple que rq es divisible entre 11? (A) 8180 (B) 8181 (C) 8182 (D) 9000 (E) 9090 AMC12A 2003 #18 4.2.6 D Determina todos los enteros 0n tales que existen enteros ba, con la propiedad ban 2 y 223 ban Romanian Mathematical Olympiad 2004 4.2.7 MD Dado un entero 3n , demuestra que siempre es posible, eliminando a lo sumo dos elementos del conjunto n,...,2,1 de forma que la suma de los restantes números sea un cuadrado perfecto. Romanian Mathematical Olympiad 2003 4.2.8 D Determina todos los enteros positivos cba ,, tales que abcacbcab 4.2.9 F Sea n un entero positivo. Cada uno de los números 1,2,3,...,2023 se pinta de algún bonito color pero verificando la siguiente propiedad: si (a,b) es un par de enteros diferentes tales que a es divisor de b, sus colores son diferentes. Encontrar el mínimo número de colores que se precisa para que esa propiedad se cumpla. OME Fase Local Extremadura 2023 #1 4.3 Máximo común divisor y mínimo común múltiplo. Definición. Máximo común divisor. Números coprimos. Mínimo común múltiplo. Dados dos números positivos ba, , el conjunto de divisores comunes de ambos no está vacío, pues 1 es divisor de los dos, y está acotado superiormente, pues todo divisor común es menor o igual que ),min( ba . Luego tiene sentido definir el máximo común divisor de a y b como el mayor divisor positivo común a ambos, que denotaremos por ba, . Diremos que dos números son coprimos cuando sus únicos divisores comunes sean 1 y 1 , es decir, cuando 1, ba . Dados dos números positivos ba, , el conjunto de múltiplos comunes a ambos no está vacío, pues ba es un múltiplo común, y está acotado inferiormente por ),max( ba . Luego tiene sentido definir el mínimo común múltiplo de a y b como el menor de los múltiplos comunes a ambos, y se denotará por ba, . Proposición. Algunas propiedades básicas del mcd y del mcm. a) bababa ,|,|, . b) bababababa ,),max(,),min(, . Interpretación geométrica del máximo común divisor. El máximo común divisor de a y b indica el número de puntos ),( yx con coordenadas enteras en el segmento que une los puntos )0,0( y ),( ba , sin contar el inicial )0,0( . Por ejemplo, 3)6,15( , y por tanto el segmento que une los puntos )0,0( y )6,15( pasa por tres puntos con coordenadas enteras, aparte del propio )0,0( : )6,15()24,510( )4,10()22,55( )2,5( 2 3 6 5 3 15 4.3.1 F Diremos que un punto ),( yx del plano es “punto entero” cuando sus coordenadas sean enteras. ¿Cuántos de estos puntos de este tipo hay (incluyendo ambos extremos) en el segmento que cuyos extremos son )17,3( y )281,48( ? ASHME 1989 #16 4.3.2 MF Demostrar que kknn |),( , independientemente del valor de n . En particular, 1)1,( nn 4.3.3 M Sean cba ,, enteros positivos tales que 23 cba y 9),(),(),( acMcdcbMcdbaMcd Determina la suma de todos los valores distintos de 222 cba . (A) 259 (B) 438 (C) 516 (D) 625 (E) 687 AMC 12B Fall 2021 #16 4.3.4 F Determina el máximo común divisor de todos los números de la forma 33333 )4()3()2()1( nnnnn donde n es un entero positivo. (A) 3932 (B) 336 532 (C) 369 532 (D) 328 532 (E) 339 532 Cangur B2 2023 #27, Canguro N6 2023 #27 4.4 El Teorema de Bezout (TDB). Lema. ),( ba divide a cualquier combinación lineal de a y b . Demostración. Sea byax una combinación lineal de a y b . byaxba bybabba axbaaba |),( |),(|),( |),(|),( Teorema. Teorema de Bezout (TDB). Dados dos números enteros ba, no ambos cero, el máximo común divisor de ba, se caracteriza por ser el elemento mínimo del conjunto no vacío 0,,, byaxZyxbyaxA Luego existe, es único y siempre se puede escribir como combinación lineal de a y b : Existen enteros yx, tales que byaxba ),( Demostración. Consideremos el conjunto anterior 0,,, byaxZyxbyaxA . Es un conjunto no vacío pues al menos 022 babbaa pertenece a A (estamos en todo momento suponiendo que ba, no son ambos cero). Por el Principio de buena ordenación, A tendrá un mínimo, al que llamaremos d . Vamos a demostrar que ),( bad . Supongamos que 011 ybxad para ciertos enteros 11, yx . Por el Algoritmo de la división, existirán enteros rq, tales que rqda con dr 0 . Si 0r , entonces qybqxaqybqxaaqybxaadqar 111111 )1()(0 y por tanto, r pertenece al conjunto A, tomando qyyqxx 1212 ,1 . Pero dr , lo cual contradice la hipótesis de d como elemento mínimo. Luego 0r y por tanto qda , es decir, d divide al número a. Con el mismo razonamiento se demuestra que d divide al número b, y por tanto d es común divisor de a y b. Veamos que es el máximo común divisor. Sea m otro común divisor de a y b, entonces, aplicando el lema anterior, dmdmdybxam || 11 . Corolario. Si nxx ,...,1 son números enteros y a es cualquier número entero positivo, nn xxaxaxa ,...,,..., 11 Demostración. Sean nxaxad ,...,1 y nxxe ,...,1 . Luego deadeaxaeaxe ii ||| . Por el TDB, nnnn axkaxkeaxkxke ...... 1111 Es decir, ae es combinación lineal de nxaxa ,...,1 , y por tanto es un múltiplo de d , luego dae . Y, puesto que anteriormente hemos demostrado que dea , llegamos a dea . Corolario. 1),( ba Existe una combinación lineal 1 byax Demostración. Es el TDB. 1),(1|),(1|),( bababyaxba 4.4.1 M Demuestra que la fracción 314 421 n n es irreducible para todo número natural n. IMO 1959 #1 4.4.2 M Los números de la sucesión ...,116,109,104,101 son de la forma 2100 nan , ...,2,1n Para cada n , sea 1, nnn aad . Determina nn d1max . AIME 1985 Teorema. Si naaad ...,,, 21 entonces 1...,,, 21 d a d a d a n Demostración. dkaadaaad iiin |...,,, 21 . Sea d a d a d a d n...,,,' 21 ysupongamos que 1'd . dddaddddkadk d a d a d d a d a d a d iiii iin |'|'''''|'...,,,' 21 Lo cual es imposible suponiendo 1'd . Luego 1'd . 4.5 Divisibilidad con números coprimos. Teorema. Si 1),( ba , entonces: a) cab cb ca | | | b) cabca || c) cd bcd acd | | | d) ced bed acd | | | Demostración. a) cabyaxbabbyaaaxbbcbycaxbyaxccc byaxba bbccb aacca |)''('')(1 11),( '| '| b) cakkckaakkackbckackcbkakba dkbcbcd akbcbca |11),( | | 1431434343 2 1 Por el TDB, byaxba 11),( para ciertos enteros yx, . Luego bcyacxc , y puesto que trivialmente acxa | y por hipótesis bcya | , se deduce cbcyacxa | . c) cdkkkkddkkdkkbckackcbkakba dkbcbcd dkacacd |)(11),( | | 241324134343 2 1 d) ced ecbdbed ceadacd | )(|| )(|| aplicando el apartado anterior. Observación. El apartado a) del teorema anterior se puede generalizar: Si naaa ,...,, 21 son enteros tales que 1),( ji aa si ji , entonces ba |1 , ba |2 , ..., ban | baaa n |...21 4.5.1 D Sean nm, dos enteros positivos diferentes. Demostrar que 1)2,2()1,1(),( nmnmnmnm Indian National Mathematical Olympiad 2019 #3 (parcial) 4.6 El algoritmo de Euclides (ADE). Lema. ),(),( cacaba Demostración. Sean ),( caban y ),( cam . ycbyxaycabyxacabyxancaban )()(),( , luego nca |),( . Y por otro lado, ncabamcabm cm abmam cam ),(|| | || ),( . Así pues, mn | y nm | , y por tanto mn . Teorema. Algoritmo de Euclides (ADE). El algoritmo de Euclides es un método efectivo para calcular el máximo común divisor de dos números a y b que se basa en el algoritmo de la división y en la proposición anterior: Si ckab , entonces ),(),(),( cackaaba Suponiendo ba , podemos dividir a entre b para expresar rkba , con br y así ),(),(),( brbrbkba Este mismo proceso repetiremos una y otra vez, con números más y más pequeños, hasta que el máximo común divisor se haga evidente. Ejemplo 1. Calcula 23,29 mediante el Algoritmo de Euclides. Solución. )23,6()23,6231()23,29(623129 )6,5()6,563()6,23(56323 1)5,1()5,151()5,6(1516 Así pues, 123,29 Ejemplo 2. Calcula 246,3456 mediante el Algoritmo de Euclides. Solución. )246,158()246,15824613()246,3456( )88,158()881581,158()246,158( Y de la misma manera: 2)16,2()18,16()70,18()88,70()88,158( Luego 2246,3456 Proposición. a) bac bc ac ,| | | b) cba cb ca |, | | Demostración. a) Por el TDB, bacybxacycbxcabyaxba ,|)''('', Por transitividad: acababac ||),(),,(| b) Sea bak , . Supongamos que 0k , (es decir, que 0, ba ) Por reducción al absurdo, supongamos que ck | . Entonces existirán q y kr 0 tales que rkqc . Luego kqcr múltiple común de a y b , pues lo son c y k , pero kr , contradiciendo la hipótesis de k como menor múltiple común de a y b . Por transitividad: c|,|c,|, abaaba . Corolario. dcba db ca ,|),( | | Demostración. ),(|),( ||),( ||),( dcba dbba caba 4.7 Máximo común divisor con números coprimos. Proposición. ),(),(1),( cbcabca Demostración. Por el TDB, 1),( ca implica que existen dos enteros yx, tales que cyax 1 . Sea ),( cbg y ),( cabh . Los valores hg, no son negativos. hcabg ccbg abbcbg ),(| |),( ||),( bbcyaxbcbyabxh cbyccabh abxabcabh 1)(| ||),( ||),( gcbh bh ccabh ),(| | |),( Llegamos a gh | y hg | , y puesto que no son negativos, se deduce que hg . Corolario. 1),( 1),( 1),( cab cb ca Demostración. Por la proposición anterior, 1),(),(1),( cbcabca . 11),(| | || dcabd cd abdad , luego 1),( ca , y con un razonamiento similar se demuestra que 1),( cb Observación. Esta propiedad se puede generalizar fácilmente por inducción: 1),...(1),(...),(),( 2121 caaacacaca nn Teorema. El Lema de Euclides. ca ba bca | 1),( | Demostración. ),(| | | bcaa aa bca Por otro lado, por 4.8, ),(),(1),( cabcaba . Luego ccabcaa |),(),(| , es decir, ca | . Corolario. Si 0c , ),(),( baccbca Demostración. c y ),( ba son no negativos, luego ),( bac es no negativo. Luego, aplicando 4.6a ),(|),( |),(|),( |),(|),( cbcabac cbbacbba cabacaba Por otro lado, aplicando el TDB, existirán enteros yx, tales que byaxba ),( . ),(|),(),()(|),( ||),( ||),( baccbcabacbyaxccbycaxcbca cbycbcbca caxcacbca Así pues, ),(|),( cbcabac y ),(|),( baccbca , y puesto que ambos son no negativos, llegamos a ),(),( baccbca . Corolario. Si a y b son enteros positivos, ),(),)(,(1),( abcbcacba Demostración. Floor and arithmetic functions (Darij Grinberg, 2016) pág. 12 4.8 Actividades con Python. El Algoritmo de Euclides Extendido (ADE). def egcd(a, b): if a == 0: return (b, 0, 1) else: g, y, x = egcd(b % a, a) return (g, x - (b // a) * y, y) print(egcd(117,244)) Salida: (1, 73, -35) 4.9 Problemas de introducción a la divisibilidad. 4.9.1 Eduardo colecciona 2004 piezas conicas. Las coloca en montones de 5 cada uno. ¿Cuántos montones de 5 piezas tiene? (A) 5 (B) 400 (C) 401 (D) 402 (E) 404 Cangur N1 2004 #5, Canguro N1 2004 #5 4.9.2 Tenemos 16 lápices, 12 gomas de borrar y 5 tijeras. Con este material queremos hacer paquetes como el que indica la figura. ¿Qué objetos faltan para hacer paquetes completos? (A) 1 lápiz y 1 goma (B) 2 lápices y 1 goma (C) 2 lápices y 1 tijera (D) 2 lápices y 2 gomas (E) 2 gomas y 2 tijeras. Cangur P5 2016 #7 4.9.3 La cabina de pasajeros de un avión tiene 108 asientos. Hay un asiento vacío por cada dos asientos ocupados. ¿Cuántos pasajeros hay en el avión? (A) 36 (B) 42 (C) 56 (D) 64 (E) 72 Cangur N1 2001 #5, Canguro N1 2001 #5 4.9.4 En una tienda se venden los globos en paquetes de 5 globos, o de 10 globos o de 25 globos. Mateo quiere comprar 70 globos. ¿Cuál es el menor número de paquetes que comprará? (A) 3 (B) 4 (C) 5 (D) 6 (E) 7 Cangur P6 2017 #7 4.9.5 Claudia tiene 10 hojas de papel y corta alguna en cinco partes cada una. Después de hacerlo le quedan 22 piezas en total. ¿Cuántas hojas ha cortado? (A) 3 (B) 2 (C) 6 (D) 7 (E) 8 Cangur P6 2020 #9 4.9.6 Miguel quiere preparar 24 madalenas para su fiesta de aniversario. Para cocinar seis madalenas necesita dos huevos. Los huevos se venden en cajas de seis. ¿Cuántas cajas tiene que comprar Miguel, como mínimo? (A) 2 (B) 8 (C) 4 (D) 1 (E) 3 Cangur E1 2020 #4 4.9.7 María eligió un número entero y lo multiplicó por 3. ¿Cuál de los siguientes números no pudo ser el resultado obtenido? (A) 103 (B) 105 (C) 204 (D) 444 (E) 987 Canguro N1 2005 #9, Cangur N1 2005 #10 4.9.8 Éste es un trozo de una tabla de multiplicar y éste es otro, donde, desafortunadamente, han desaparecido algunos números. ¿Cuál es el número en la casilla con la interrogación? (A) 54 (B) 56 (C) 65 (D) 36 (E) 42 Cangur N1 2008 #9, Canguro N1 2008 #7 4.9.9 ¿Cuál es el menor entero positivo divisible por 2, 3, y 4? (A) 1 (B) 6 (C) 12 (D) 24 (E) 36 Cangur N1 2003 #4, Canguro N1 2003 #4 4.9.10 ¿Cuántos números de 2 cifras son divisibles por 2 y por 7? (A)8 (B) 7 (C) 6 (D) 5 (E) 4 Canguro N1 2000 #12, Cangur N1 2000 #11 4.9.11 Determina la probabilidad de que, tomando aleatoriamente un múltiple de 864, sea también divisible entre 1944. HMMT 2002 4.9.12 Se forma un número de nueve cifras colocando aleatoriamente los dígitos del 1 al 9. ¿Cuál es la probabilidad de que el número resultante sea divisible por 18? (A) 1/2 (B) 4/9 (C) 5/9 (D) 1/3 (E) 3/4 Canguro N5 2020 #21, Kangourou J 2020 #19 4.9.13 MF ¿Cuál es el máximo común divisor de 20222021 22 y 20222021 33 ? (A) 20212 (B) 1 (C) 2 (D) 6 (E) 12 Cangur B2 2022 #13, Kangaroo Student 2022 #13 4.9.14 MF ¿Cuántos números enteros positivos de tres dígitos son divisibles por 13? (A) 68 (B) 69 (C) 70 (D) 76 (E) 77 Cangur B2 2022 #2, Kangaroo Student 2022 #2 4.9.15 MF Una vez conocí a seis hermanos cuyas edades eran seis números enteros consecutivos. Le hice a cada uno de ellos la pregunta: “¿Cuántos años tiene tu hermano mayor?”. ¿Cuál de las siguientes podría no ser la suma de sus seis respuestas? (A) 233 (B) 205 (C) 167 (D) 125 (E) 95 Cangur B1 2022 #13 4.9.16 MF ¿Cuántos polígonos regulares hay cuyos ángulos (en grados) son números enteros? (A) 17 (B) 18 (C) 22 (D) 25 (E) 60 Cangur N4 2015 #25, Canguro N6 2015 #24, Kangaroo Student 2015 #24 4.9.17 MF ¿De cuántas formas diferentes podemos dar valores enteros positivos a la pareja de números a y b de forma que la igualdad b a 7 5 sea cierta? (A) 0 (B) 1 (C) 2 (D) 3 (E) 4 Cangur B1 2023 #9, Canguro N5 2023 #9 4.9.18 MF Cada tercer escalón de una escalera de 2023 peldaños está pintado de negro. Los siete primeros peldaños se muestan en la siguiente figura: Anna sube la escalera de uno en uno comenzando por el pie derecho o por el pie izquierdo, y alternándolos en cada paso. Determina el número de peldaños negros que habrá pisado con el pie derecho. (A) 333 (B) 336 (C) 337 (D) 674 (E) Depende del pie con el que comience Cangur B1 2023 #17, Canguro N5 2023 #17 4.9.19 MF Un número de dos cifras se llama sp (sin potencias) si ninguna de sus cifras se puede escribir como una potencia de exponente mayor que 1 de un número entero. Por ejemplo, 53 es sp y 54 no lo es porque 4 = 2² . ¿Cuál de los siguientes números es divisor común del más grande y del más pequeño de los números sp de dos cifras? (A) 3 (B) 5 (C) 7 (D) 11 (E) 13 Cangur B1 2023 #18, Canguro N5 2023 #18 5 Números primos. 5.1 Concepto de número primo. Definición. Número primo. Todo número es divisible por sí mismo y por la unidad. Diremos que un número natural 1p es primo cuando sus únicos divisores positivos sean él mismo y la unidad. Por ejemplo, son primos los números 5, 13, 59 o 397. Llamamos compuestos a los números que no son primos. El número 1 no se considera ni primo ni compuesto. Proposición. Algunas propiedades de los números primos. a) Si p es primo y pa | , entonces pa ,1 . b) Si p y q son primos, entonces qpqp | . c) Todos los primos son impares excepto el 2. d) El 2 y el 3 son los únicos primos cuya diferencia es 1. e) Si p es primo y Nba , , entonces apap b || . 5.1.1 Problema resuelto. Demuestra que si 3p es primo, entonces 1|24 2 p . Solución. Por el algoritmo de la división, todo número se puede representar como n6 , 16 n o 26 n . Si es primo, la única opción aceptable es 16 n , pues las otras son divisibles entre 2 o 3. Luego: )13(1212361112361616 22222 nnnnpnnnpnp Está claro que o bien n es par o bien 13 n es par, luego 1|24 2 p . 5.1.2 Problema resuelto. Determina la suma de todos los números primos entre 1 y 100 que son simultáneamente 1 más que un múltiplo de 4 y 1 menos que un múltiplo de 5. AHSME 1999 #3 Solución. 1101)2(52|25|2 122451514 15 14 ccpcbbb aabba bp ap Con 110 cp ya tenemos un conjunto de candidatos suficientemente pequeño como para proceder a testearlos, uno por uno: 911101 pc (no es primo) 3441912102 pc 1742913103 pc 3943914104 pc 4915105 pc 31445916106 pc 6917107 pc 31947918108 pc 12248919109 pc 991101010 pc Luego la suma es 29+89=118. Corolario. Corolario al Lema de Euclides. Si p es primo y abp | entonces ap | o bp | . Demostración. Basta aplicar el Lema de Euclides teniendo en cuenta que 1),(),( bpap . 5.1.3 M Sean yx, enteros. Demostrar que yx 32 es divisible entre 17 si y solo si yx 59 es divisible entre 17. Corolario. a) a es par si y solo si na es par b) a es impar si y solo si na es impar. Demostración. a) nnnn kkaka 122)2(2 Basta aplicar el Lema de Euclides con 2p . b) n k knn k k n kaka 1 21)12(12 impar. Por el apartado a, si a es par entonces na es par, luego si na es impar, necesariamente a debe ser par. Corolario. Hay infinitos números primos. Demostración. Entre otras muchas demostraciones de este resultado, la de Euclides es un ejemplo de elegancia: Supongamos, por el contrario, que existe una cantidad finita de números primos. Sean estos nppp ...1 21 Consideremos el número 121 npppn . No puede ser primo, pues npn , luego existirá al menos un k tal que npk | , pero también se cumple trivialmente nk pppnp 211| , y por tanto 11|1)1(| kkk ppnnp lo cual es imposible. Así pues, no es posible que exista un número finito de primos. Observación. La densidad de los números primos (es decir, la proporción de números primos respecto al total de naturales) es un resultado que se conoce desde hace 100 años, y es un teorema de la llamada teoría de números analítica: 1 log/ lim nn n n Donde n denota el número de primos menores o iguales a n. Este resultado fue demostrado por Hadamard y de la Vallé Poussin en 1896. 5.1.4 F Determina cuántos números primos hay en los primeros diez números de la secuencia 121, 11211, 1112111... (A) 0 (B) 1 (C) 2 (D) 3 (E) 4 AMC 12B 2022 #3 5.1.5 MF ¿Cuál es el número entero más pequeño que podemos obtener como resultado de calcular una media aritmética de cinco números primos diferentes? (A) 6 (B) 5 (C) 12 (D) 2 (E) 30 Cangur B1 2023 #20, Canguro N5 2023 #20 5.2 El Teorema fundamental de la aritmética (TFA). Teorema. Teorema fundamental de la aritmética (TFA). a) Todo entero 1n se puede representar como producto de números primos. b) Ordenando los ip , obtenemos lo que denomina descomposición canónica del número n : ka k aa pppn ...21 21 con kppp ...21 y ia0 Por ejemplo: 23218 , 73284 2 , 131124576 , 8179232716 La descomposición canónica de un número es única. Demostración. a) Sea 1n . Si n es primo, ya hemos acabado. Supongamos que n es compuesto y sea 1p su menor divisor. Está claro que 1p tiene que ser primo. Luego 11npn , para cierto nn 11 . De nuevo, si 1n es primo ya hemos acabado. Supongamos que es compuesto y sea 2p su menor divisor. Está claro que 2p tiene que ser primo, y 221 nppn para cierto nnn 121 . Este proceso no puede continuar indefinidamente, pues antes de n pasos debemos encontrar un xp primo, y spppn ...21 . b) Supongamos que ts a t bba s aa qqqpppn ...... 2121 2121 . Por el Corolario al Lema de Euclides, todo ip será un jq y todo jq será un ip . Esto implica que ts . Puesto que, además, sppp ...21 y sqqq ...21 , tenemos que ii qp para todo si 1 : ss a s bba s aa ppppppn ...... 2121 2121 Veamos que también
Compartir