Congruencias olímpicas

Traballo Fin de Grao CONGRUENCIAS OLÍMPICAS Marcos Arias Fernández Curso Académico: 2021/2022 UNIVERSIDADE DE SANTIAGO DE COMPOSTELA GRAO DE MATEMÁTICAS Traballo Fin de Grao CONGRUENCIAS OLÍMPICAS Marcos Arias Fernández Setembro, 2022 UNIVERSIDADE DE SANTIAGO DE COMPOSTELA Traballo proposto Área de Coñecemento: Álxebra Título: Congruencias olímpicas Breve descrición do contido Trátase de facer unha revisión dos principais conceptos sobre congruencias que aparecen nos problemas das distintas fases da Olimpíada Matemática Española (sistemas de números congruentes, Teorema pequeno de Fermat, Teorema de Euler, Teorema de Wilson, ecuacións polinómicas módulo un primo, teorema chinés dos restos, raíces primitivas, criterios de divisibilidade, etc.), facer unha recollida de enunciados e presentar unha escolma de problemas resoltos. Recomendacións Outras observacións iii Índice xeral Resumo vii Introdución ix 1. Congruencias 1 1.1. Conceptosiniciais............................. 1 1.2. Criterios de divisibilidade . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Congruencias de primeiro grao 7 2.1. Teoremasiniciais ............................. 7 2.2. Resolución de congruencias de primeiro grao . . . . . . . . . . . . . . 12 3. Problemas 21 3.1. Olimpíadas Matemáticas nacionais . . . . . . . . . . . . . . . . . . . 22 3.2. Olimpíada matemática internacional . . . . . . . . . . . . . . . . . . 26 3.3. Outrosproblemas............................. 29 Bibliografía 33 v Resumo No presente traballo de fin de grao tratarase de dar un contexto teórico a determinados problemas das Olimpíadas Matemáticas, ademais de presentar solución a unha selección deles. Na parte teórica tratarase de definir que é unha congruencia, como resolver as congruencias e sistemas de congruencias de primeiro grao. Na práctica resolveranse problemas de congruencias das Olimpíadas Matemáticas a niveis nacionais e internacionais ademais de algúns problemas de interese. Abstract The present final degree project will give a theorical context to some of the olympiad problems, It will also present a solution to a selection of them. In the theoretical part It will be defined what a congruence is, how first degree congruences and systems can be solved. In the practical part some problems of congruences from the mathematical olympiads in a national and international levels with some other interesting problems will be solved. vii 4CAPÍTULO 1. CONGRUENCIAS 1.2. Criterios de divisibilidade Como regra xeral para deducir os criterios de divisibilidade basta con observar que os números da forma anan−1... a1a0se poden escribir da forma an·10n+an−1· 10n−1+... +a1·10 + a0e usar axeitadamente as propiedades anteriores, en especial é necesario ver con que número é congruente o 10 e as súas sucesivas potencias. A continuación veranse algúns exemplos. Teorema 1.17 (Congruencia módulo 2).Todo número é congruente coa súa cifra das unidades módulo 2. Demostración. Tomemos o número an·10n+an−1·10n−1+... +a1·10 + a0, entón como 10 ≡0 (m´od 2),an·10n+an−1·10n−1+... +a1·10 + a0≡a0(m´od 2). Exemplo 1.18. 3427 ≡7≡1 (m´od 2) Teorema 1.19 (Congruencia módulo 3).Tódo número é congruente coa suma de todas as súas cifras en módulo 3. Demostración. Tomemos o número an·10n+an−1·10n−1+...+a1·10+a0. Como 10 ≡1 (m´od 3), entón 10n≡1n= 1 (m´od 3), entón an·10n+an−1·10n−1+...+a1·10+a0≡ an·1 + an−1·1 + ... +a1·1 + a0=an+an−1+... +a1+a0(m´od 3). Exemplo 1.20. 3427 ≡3 + 4 + 2 + 7 = 16 ≡7≡1 (m´od 3). Teorema 1.21 (Congruencia módulo 4).Todo número é congruente módulo 4 coa suma de o dobre da segunda cifra e a última. Demostración. Se o número é da forma an·10n+an−1·10n−1+... +a1·10 + a0, como 10 ≡2 (m´od 4) e10i≡0 (m´od 4) para todo i∈N,i≥2an·10n+an−1· 10n−1+... +a1·10 + a0≡2·a1+a0(m´od 4). Exemplo 1.22. 3427 ≡2·2 + 7 = 11 ≡3 (m´od 4). Teorema 1.23 (Congruencia módulo 5).Todo número é congruente coa súa última cifra módulo 5. Demostración. Se o número é da forma an·10n+an−1·10n−1+... +a1·10 + a0, como 10 ≡0 (m´od 5),an·10n+an−1·10n−1+... +a1·10 + a0≡a0(m´od 5). Exemplo 1.24. 3427 ≡7≡2 (m´od 5). 1.2. CRITERIOS DE DIVISIBILIDADE 5 Teorema 1.25 (Congruencia módulo 6).Todo número da forma an·10n+an−1· 10n−1+... +a1·10 + a0é congruente con Pn i=0[(−2)imod 6] ·aimódulo 6. Demostración. Se o número é da forma an·10n+an−1·10n−1+...+a1·10+a0, como 10 ≡ −2 (m´od 6), polo tanto an·10n+an−1·10n−1+... +a1·10+a0≡Pn i=0[(−2)i mod 6] ·ai(m´od 6). Exemplo 1.26. 3427 ≡(−2) ·3 + 4 ·4 + (−2) ·2 + 7 = −6 + 16 −4 + 7 ≡13 ≡1 (m´od 6). Teorema 1.27 (Congruencia módulo 7).Todo número da forma an·10n+an−1· 10n−1+... +a1·10 + a0é congruente con 3·(an·10n−1+an−1·10n−2+... +a1− 2·a0) (m´od 7). E se queremos comprobar se aé divisible entre 7 basta con ver se an·10n−1+an−1·10n−2+... +a1−2·a0≡0 (m´od 7). Demostración. Se o número é da forma an·10n+an−1·10n−1+... +a1·10 + a0, como 10 ≡3 (m´od 7) e1≡ −6 (m´od 7), entón 10 ·(an·10n−1+an−1·10n−2+ ... +a1) + a0≡3·(an·10n−1+an−1·10n−2+... +a1−2·a0) (m´od 7). Ademais, no caso de que o número sexa divisible entre 7, como temos que 3·(an·10n−1+an−1· 10n−2+... +a1−2·a0)≡0 (m´od 7), como 7non divide a 3 temos que 7 divide a an·10n−1+an−1·10n−2+...+a1−2·a0, polo tanto an·10n−1+an−1·10n−2+...+a1−2·a0≡ 0 (m´od 7). Exemplo 1.28. Vexamos se 3427 é múltiplo de 7.342−2·7 = 328,32−2·8 = 16 ≡2 (m´od 7), polo que non é múltiplo de 7. Exemplo 1.29. Vexamos se 23989 é múltiplo de 7.2398 −2·9 = 2380,23 −16 = 7≡0 (m´od 7), polo que é múltiplo de 7. Teorema 1.30 (Congruencia módulo 8).Todo número da forma an·10n+an−1· 10n−1+... +a1·10 + a0é congruente con 4·a2−2·a1+a0módulo 8. Demostración. Se o número é da forma an·10n+an−1·10n−1+... +a1·10 + a0, como 10 ≡ −2 (m´od 8), entón 102≡4 (m´od 8) e10i= 103·10i−3≡0 (m´od 8) para todo i∈N, entón an·10n+an−1·10n−1+... +a1·10 + a0≡4·a2−2·a1+a0 (m´od 8). Exemplo 1.31. 3427 ≡(−2)2·4+(−2) ·2 + 7 = 16 −4+7≡7≡1 (m´od 3). 6CAPÍTULO 1. CONGRUENCIAS Teorema 1.32 (Congruencia módulo 9).Todo número da forma an·10n+an−1· 10n−1+... +a1·10 + a0é congruente con Pn i=0 aimódulo 9. Demostración. Se o número é da forma an·10n+an−1·10n−1+... +a1·10 + a0, como 10 ≡1 (m´od 9), entón an·10n+an−1·10n−1+... +a1·10 + a0≡Pn i=0 ai (m´od 9). Exemplo 1.33. 3427 ≡3 + 4 + 2 + 7 = 16 ≡7 (m´od 9). Teorema 1.34 (Congruencia módulo 10).Todo número da forma an·10n+an−1· 10n−1+... +a1·10 + a0é congruente con a0módulo 10. Demostración. Se o número é da forma an·10n+an−1·10n−1+...+a1·10+a0como 10 ≡0 (m´od 10), entón an·10n+an−1·10n−1+...+a1·10+a0≡a0(m´od 10). Exemplo 1.35. 3427 ≡7 (m´od 10). Teorema 1.36 (Congruencia módulo 11).Todo número da forma an·10n+an−1· 10n−1+... +a1·10 + a0é congruente con Pn i=0(−1)iaimódulo 11. Demostración. Se o número é da forma an·10n+an−1·10n−1+...+a1·10+a0como 10 ≡ −1 (m´od 11), entón an·10n+an−1·10n−1+... +a1·10 + a0≡Pn i=0(−1)iai (m´od 11). Exemplo 1.37. 3427 ≡ −3+4−2 + 7 = 16 ≡6 (m´od 11). Capítulo 2 Congruencias de primeiro grao 2.1. Teoremas iniciais Definición 2.1 (Divisor e múltiplo).Dicimos que cé divisor de aou aé múltiplo de c, con aec∈N, se c≥1ec≤ae existe n∈Ztal que a=c·n, é dicir a≡0 (m´od c). Definición 2.2 (Números primos relativos ou coprimos).Dicimos que aeb,ae b∈N, son coprimos ou primos relativos cando non existe cdivisor común a aeb distinto de 1. Exemplo 2.3. 36 e35 son primos relativos. Definición 2.4 (Números primos e compostos).Dicimos que p, con p∈N−{0,1}, é un número primo cando non existe cdivisor de pdistinto de 1ep. No caso de que exista cdistinto de 1ou xtal que c|x, diremos que xé composto. Definición 2.5 (Mínimo común múltiplo).Diremos que Mé o mínimo común múltiplo de a1,a2,... ,anse Mé o menor número que é múltiplo de a1,a2,... ,aná vez. Definición 2.6 (Máximo común divisor).Diremos que mé o máximo común divisor de a1,a2,... ,anou (a1,a2,... ,an)se Mé o maior número que é divisor de a1,a2, ... ,aná vez. Teorema 2.7 (Algoritmo de Euclides para o cálculo do máximo común divisor). Para calquera par de números a, b ∈N, b > 0, tense que (a, b)=(amod b, b). 7 8CAPÍTULO 2. CONGRUENCIAS DE PRIMEIRO GRAO Demostración. Se r=amod b, tense que a=q·b+r, q ∈N. Polo tanto, todo divisor común a berdividirá tamén a a, polo que (b, r)≤(a, b). Por outra banda, dado que r=a−q·b, todo divisor común a aebtamén dividirá ar, polo tanto (a, b)≤(b, r). Exemplo 2.8. Calculemos o máximo común divisor de 364 e748.(748,364) = (748 mod 364,364) = (20,364) = (20,364 mod 20) = (20,4) = (20 mod 4,4) = (0,4) = 4. Teorema 2.9 (Teorema de Bézout ou algoritmo de Euclides extendido).Para calquera par de números a, b ∈Ncon algún deles distinto de 0, existen s, t ∈Ztal que (a, b) = s·a+t·b Demostración. Sexa co menor enteiro positivo da forma c=x·a+y·b,x, y ∈Z. Como (a, b)|a, b, entón (a, b)|ce, polo tanto, (a, b)≤c. Agora vexamos se c|a, b. Supoñamos que c-a, e a=q·c+r, 0≤r < c. Entón a>r=a−q·c= (1 −q·x)·a+y·b, o cal non pode ser xa que aé o menor enteiro positivo que cumpre a propiedade. Teorema 2.10. Se un primo divide ao produto de dous números, entón dito primo divide a algún deses números. [2] Demostración. Supoñamos que p|a·bpero p-a.E entón a=p·q+rcon 1≤r≤ p−1, e a·b=p·q·b+r·b; ademais, polo teorema de Bezout temos que como p-a, entón (a, p) = 1 = α·p+β·acon α, β ∈Z, entón b=α·p·b+β·a·bque como p|a·bpodemos afirmar que p|b. Exemplo 2.11. 6|4·21 = 84 pero 6-4,21. Exemplo 2.12. 3|4·21 = 84 e, polo tanto, 3|4ou 3|21, neste caso, 3|21. Corolario 2.13. O produto de dous números distintos de 0máis pequenos que un primo dado non pode ser múltiplo dese primo. [2] Teorema 2.14 (Teorema fundamental da aritmetica).Todo número enteiro ou é primo, ou se pode descompoñer de forma única, salvo orde, en factores primos. [2] 2.1. TEOREMAS INICIAIS 9 Demostración. Primeiro observemos que ningún número natural pode poñerse como produto infinito de factores distintos a 1, xa que se así fora m=Y I aicon i∈Ie |I|infinito, entón m=Y I ai≥Y I 2o cal non pode ser un número natural porque diverxe. Supoñamos agora que existe alo menos un número composto que se pode descompoñer en factores primos de dous ou mais xeitos. Como todo subconxunto de N ten que ter un mínimo, ten que existir un número composto con múltiples factorizacións en factores primos distintas que sexa o mais pequeno e denominaremolo a. Dito aterá estas duas factorizaciones primas distintas pn1 1·... pns seqm1 1·... qmt tcon n1, ... , ns, m1, ... mt∈N−{0}. Sexa pprimo, se p|pn1 1·... pns s, entón p|qm1 1·... qmt t, polo que os primos que hai na primeira factorización teñen que ser os mesmos que os da segunda e viceversa, entón qm1 1·... qmt t=pm1 1·... pms s. Como as factorizacións son distintas podemos supoñer sen perda de xeralidade que n1< m1, polo que pn2 2·... pns s=pm1−n1 1·pm2 2·... pms s= a/pn1< a o cal non pode ser xa que aé o menor número composto con múltiples factorizacións en factores primos distintas. Teorema 2.15. É equivalente dicir que Mé o mínimo común múltiplo de a1,a2, ... ,ana dicir que Mé igual ao produto de todos os factores primos de a1,a2,... , anelevados ao maior dos exponentes das factorizacións. Demostración. Que Mé un múltiplo é trivial xa que basta con dividir Mentre cada un dos aipara todo i∈ {1,2,...,n}e ver que ao facelo se cancelan todos os factores primos de ai. Agora témos que ver que é o menor, e para iso supoñamos que existe M0múltiplo de a1,a2,... ,anmenor estricto que M. Ao factorizalo en factores primos vemos que non pode haber ningún factor distinto aos factores primos de a1,a2,... ,anxa que se así fora podes definir M00 con todos os factores primos de M0menos aqueles que non sexan factores primos de aipara todo i∈ {1,2,...,n}que tamén sería múltiplo de estes. Polo tanto podemos dicir que os factores primos de M0tamén están en M. Como M0< M alo menos un dos factores primos de M0ten que ter exponente menor ao mesmo factor primo en M. Dito exponente do primo en Mé igual ao exponente do mesmo primo para a factorización de certo aj, polo tanto, M0non pode ser múltiplo dese ai. 10 CAPÍTULO 2. CONGRUENCIAS DE PRIMEIRO GRAO Teorema 2.16. É equivalente dicir que mé o máximo común divisor de a1,a2,... , ana dicir que mé igual ao produto de todos os factores primos comúnes de a1,a2, ... ,anelevados ao menor exponente. Demostración. Que mé un divisor é trivial xa que basta con dividir cada un dos ai para todo i∈ {1,2,...,n}entre me ver que ao facelo se cancelan todos os factores primos de m. Agora témos que ver que é o maior, e para iso supoñamos que existe m0o maior divisor de a1,a2,... ,anmaior estricto que m. Ao factorizalo en factores primos vemos que non pode haber ningún factor primo distinto aos factores primos comúns de a1,a2,... ,anxa que se así fora podes non sería divisor de aipara todo i∈ {1,2, ...,n}. Polo tanto podemos dicir que os factores primos de m0tamén están en m. Como m<m0un dos factores primos de m0ten que ter exponente maior ao mesmo factor primo en m. Dito exponente do primo en mé igual ao exponente do mesmo primo para a factorización de certo aj, polo tanto, m0non pode ser divisor dese ai. Teorema 2.17. Se a1,a2,...,anson primos relativos de αse, e só se, a1·a2·...·an eαtamén son primos relativos. Demostración. Basta con darse conta que a factorización en factores primos de a1· a2·... ·ané a mesma que o produto de todos os factores primos de cada un dos ai e, polo tanto, non haberá ningún factor primo en común con α. Teorema 2.18. Se a1,a2,...,anson primos relativos entre si e todos son divisores de α, entón a1·a2·... ·antamén divide a α. Demostración. Basta con darse conta que a factorización en factores primos de cada un dos a1,a2,...,anao ser divisores de αestá formada so por algúns dos factores primos con exponente menor ou igual ao de αe sen ter primos en común co resto de aipolo feito de ser coprimo destes. Disto seguese que o produto de todos eles tamén terán os mesmos primos que αcon expoñente menores ou iguais aos da factorización de dito α. Teorema 2.19. Tomemos A=aα1 1·aα2 2·... ·aαn nonde todo aié primo. Se A=ks, entón αidivide a spara todo i∈ {1,2, ... , n}. [2] 2.1. TEOREMAS INICIAIS 11 Demostración. Como a factorización en factores primos de Aé única, knterá a mesma factorización. Ao factorizar kpodemos observar que consta de exactamente os mesmos primos que a factorización de A, xa que se no fose así, se houbera algún primo bfactor de k,btamén sería factor primo de kse non de A, e se algún ainon fora factor primo de ke por tanto tampouco o sería de ks. Digamos que a factorización en factores primos de k é k=aα0 1 1·aα0 2 2·... ·aα0 n n, entón ks=as,·α0 1 1·as·α0 2 2·... ·as·α0 n n. Polo tanto para todo i∈ {1,2, ... , n}, αi=s·α0 i, entón sdivide a αi. Corolario 2.20. Se A=a1·a2·... ·an, onde todos os aison coprimos, e A=kn. Entón n √ai∈N. Demostración. Basta con observar que os ai, ao ser coprimos, non comparten ningún primo na súa factorización, polo que podemos aplicar o teorema anterior e observaremos que os expoñentes de cada un deses primos é divisible entre n. Teorema 2.21. Sexa Ade xeito que sexa divisible entre αeβque son coprimos. Entón Aserá divisible entre α·β. Demostración. Basta con ver que os factores primos de αeβson distintos, polo que os expoñentes dos factores primos de α·βnon superarían aos de A, xa que tampouco ocorre en αnin en β. Exemplo 2.22. 6,4|12 pero 6·4-12. Exemplo 2.23. 3,4|12 e como son coprimos, entón 3·4|12. Corolario 2.24. Se aebson divisibles entre ke son a súa vez congruentes módulo nsendo kencoprimos, entón a k≡b k(m´od n). Demostración. Basta con observar que se a≡b(m´od n), entón a−bé divisible entre ne como aebson a súa vez divisibles entre k,a−btamén o será. Polo tanto podemos aplicar o teorema anterior e concluiremos que a−b=k·n·mpara algún m∈Z, entón a−b k=a k−b k=n·m, entón a k≡b k(m´od n). 12 CAPÍTULO 2. CONGRUENCIAS DE PRIMEIRO GRAO Teorema 2.25. Sexan αencoprimos e sexan aebtales que a6≡ b(m´od n), entón α·a6≡ α·b(m´od n). Demostración. Supoñamos nas condicións do teorema que α·a≡α·b(m´od n). Entón α·a−α·b=m·ncon m∈Zeα·(a−b) = m·n. Como αenson coprimos, αdivide únicamente a m, é dicir m α=s∈Z, entón a−b=s·nea≡b(m´od n), o cal contradice as hipóteses do teorema. Corolario 2.26. Sexan a, n ∈Zson coprimos, existe x∈Zde xeito que a·x≡b (m´od n). Ademais sexan x0, x00 tales que a·x0≡b(m´od n)ea·x00 ≡b(m´od n), entón x0mod n=x00 mod n. Demostración. Definamos R= 0,1, ... n −1os posibles restos de dividir calquera número entre n. Supoñamos agora sen perda de xeralidade que para todo x∈R, a · x−b6≡ c(m´od n), entón a·x6≡ c−b≡i(m´od n), i ∈R. Se x1, x2∈R, x16=x2, entón a·x16≡ a·x2(m´od n), entón o coxunto de todos os elementos aos que equivale a·xvai ser exactamente Ro cal non pode ser xa que non exclue a i. Corolario 2.27. A expresión a·x+bpodemos facela congruente con calquera valor en módulo nse, e só se, aenson coprimos. 2.2. Resolución de congruencias de primeiro grao Definición 2.28 (Congruencia de primeiro grao).Chamamos congruencia de primeiro grao as congruencias entre polinómios de grao 1. Ditas congruencias pódense reducir de xeito trivial a a·x+b≡c(m´od n). Corolario 2.29. Se aensón coprimos a congruencia de primeiro grao a·x+b≡c (m´od n)sempre é resoluble e a solución é única para valores de xentre 0en−1. Demostración. Basta con observar que sempre existe xcongruente con b−cmódulo n. Teorema 2.30 (Polinomios de módulo primo).Dado o polinomio An·xn+An−1· xn−1+... A1·x+A0= 0, con Ai∈Zpara todo i∈ {0,1, ... , n},α∈Zé solución de An·xn+An−1·xn−1+... A1·x+A0= 0 se, e só se, αmod pé solución de An·xn+An−1·xn−1+... A1·x+A0≡0 (m´od p)para todo pprimo. 2.2. RESOLUCIÓN DE CONGRUENCIAS DE PRIMEIRO GRAO 13 Demostración. Se x=αé solución de An·xn+An−1·xn−1+... A1·x+A0= 0, entón An·xn+An−1·xn−1+... A1·x+A0= (x−α)·g(x)≡0 (m´od p), entón x−α≡0 (m´od p)ex≡α(m´od p) Por outra banda supoñamos que x=αmod pé solución da congruencia An· xn+An−1·xn−1+... A1·x+A0≡0 (m´od p), e sexa Qs i=1(x−as)·g(x)a factorización do polinomio con todas as raíces enteiras deste. αten que ser congruente a algunha desas raíces enteiras módulo pxa que se non fora así g(α)≡0 (m´od p), entón existe a∈Ztal que a=p·q+α, entón aé raíz de go cal non é posible. Teorema 2.31. Se o máximo común divisor de aendivide a c−b, a congruencia a·x+b≡c(m´od n)é resoluble e ten (a, n)solucións entre 0en−1. Non haberá solución en caso contrario. [2] Demostración. Sexa αo máximo común divisor de aen, entón a·x≡c−b(m´od n), entón a α·x≡c−b α(m´od n α)que induce a unha congruencia que é resoluble cunha única solución x0∈ {0,1, ... , n α}, entón para todo i∈ {0,1, ... α −1}x0+i·n αtamén serán solucións e serán todas as que se encontran entre 0en−1. Para ver se hai solución en caso contrario basta con supoñer que esta existe. Sexa βdita solución, polo tanto para certo m∈Zpodemos dicir que a·β−(c−b) = m·n, entón c−b=a·β−m·no cal non pode ser xa que αdivide a a·β−m·npero non pode dividir a c−b. Teorema 2.32 (Formulación clásica do teorema pequeno de Fermat).Se aepson coprimos, con pprimo, ou o que é o mesmo, pnon divide a a, entón ap−1−1≡0 (m´od p). [2] Demostración. Sexa a∈Ze sexan a, 2·a, ... (p−1) ·aos primeiros p−1múltiplos. Os residuos de a, 2·a, ... (p−1) ·ason 1,2, ... p −1, non necesariamente neste orde, polo tanto, a·2·a·...·(p−1)·a=ap−1·(p−1)! ≡(p−1)! (m´od p), entón ap−1≡1 (m´od p). Corolario 2.33 (Teorema pequeno de Fermat).Sexa p primo, para todo a∈Z, ap− a≡0 (m´od p). [2] 20 CAPÍTULO 2. CONGRUENCIAS DE PRIMEIRO GRAO Exemplo 2.64. No exemplo anterior as solucións son da forma x= 22·3 + k·7 mod 21 para k∈ {0,1,2}, o que da como solucións 12,19,5. Teorema 2.65 (Sistemas de congruencias de primeiro grao).Sexa un sistema de congruencias de primeiro grao da forma:        x≡a1(m´od n1) . . . x≡as(m´od ns) Podemos obter a solución se esta existe, e esta estará garantida se o módulos son coprimos dous a dous. Demostración. Que a existencia está garantida se os módulos son coprimos polo teorema chinés dos restos. Para ver os casos nos que hai solución basta con observar o algoritmo de resolución. Da primeira congruencia podemos deducir que x=a1+k1·n1, e utilizando isto na seguinte obtemos que a1+k1·n1≡a2(m´od n2)que terá solución se (n1, n2) divide a a2−a1. Iterando o proceso, ao resolver a última congruencia obterase a solución sempre que se cumpra a condición arriba descrita. Exemplo 2.66. Resolvamos: (x≡3 (m´od 4) x≡5 (m´od 9) Como x≡3 (m´od 4) entón x= 4 ·q1+ 3. E como x≡5 (m´od 9) temos que 4·q1+ 3 ≡5 (m´od 9), entón 4·q1≡2 (m´od 9) e como Ord9(4) = 3, entón q1= 42·2, e, polo tanto, x= 4 ·42·2 + 3 = 131 Capítulo 3 Problemas Introduciomos aquí unha selección de problemas extraídos das Olimpíadas Matemáticas a niveles locais, nacionais e internacionais, ademais de algúns problemas de interese. Respecto as Olimpíadas Matemáticas a nivel local e nacional, extraense de multiples paises, como a Unión Sovietica o Estados Unidos e, especialmente, as Olimpíadas Matemáticas Españolas. A hora de afrontar as Olimpíadas Matemáticas Españolas deberase ter en conta a estructura: Fase local, de distrito ou fase autonómica: Celebrase ao final do primeiro trimestre en cada Comunidade Autónoma ou Distrito Universitario e consta dun total de 6 problemas repartidos en duas probas escritas. Os participantes deberán estar cursando a ensinanza secundaria e poderán presentarse voluntariamente sen requisito previo. Fase Nacional: Celebrase a finais de febreiro e consta dun total de 6 problemas comprendidos en duas probas escritas de 3 horas de duración cada unha. Cada unha destas probas constan de 3 problemas, é dicir, un total de 6 propostos por un tribunal. Por outra banda se o aspirante vaise a enfrentar ás Olimpíadas Matemáticas internacionais, debe saber que celébranse a mediados de Xullo e consta de duas probas de 4 horas de duración cada unha, tendose que enfrentar o aspirante a un total de 6 problemas repartidas en 3 problemas por proba. [6] 21 22 CAPÍTULO 3. PROBLEMAS 3.1. Olimpíadas Matemáticas nacionais Problema 3.1 (Olimpíada Matemática Española (OME) 2004 Problema 9).Achar todas las formas de expresar 2003 como la suma dos cadrados dos números enteiros. [4] Solución Sexa x2, y2cadrados perfectos e como x, y ≡ {0,1,2,3}(m´od 4), entón x2, y2≡ {0,1}, polo tanto x2+y2≡ {0,1,2}. Como 2003 ≡3 (m´od 4), entón x2+y26= 2003,para todo x, y ∈Z Problema 3.2 (All Soviet Union Mathematical Olympiad 1970 Problema 13).Se os números que van de 11111 ao 99999 colócase en algún orde formando un número de 444445 cifras, demostrar que dito número non é unha potencia de 2. [4] Solución Sexan S1, ... , S88889 todos os números que van do 11111 ao 99999 de xeito que N=P88889 i=1 105·(i−1) ·Si. Obsérvese que 105−1 = 99999 = 9 ·11111, entón 105≡1 (m´od 11111), é dicir, N≡PP88889 i=1 Si(m´od 11111). Obsérvese ademais que, por ser 11111 primo, todo elemento de Z11111 ten inversa coa suma. Ademais obsérvese que os restos dos números do 11111 ao 99999 recorren exactamente 9veces todos os elementos de Z11111, polo tanto N≡0 (m´od 11111) e, polo tanto, non pode ser potencia de 2. Problema 3.3 (OME fase local 2004 Problema 4).Existe algunha potencia de 2tal que ao escribila no sistema decimal teña todos os seus díxitos distintos de cero e sexa posible reordenar os mesmos para formar con eles outra potencia de 2? [4] Solución Sexan AeBpotencias de 2 tales que cumpren as condicións do problema. Se A < B teremos que ou B= 2 ·Aou B= 4 ·Aou B= 8 ·Axa que como todas as cifras teñen que ser distintas de 0, AeB, teñen que ter o mesmo número de cifras significativas. Ademais como os seus díxitos son os mesmos, A≡B(m´od 9), entón B−A≡0 (m´od 9), entón A≡0 (m´od 9) ou 3·A≡0 (m´od 9) ou 7·A≡0 (m´od 9) e ningún destes casos son posibles. Problema 3.4 (United States Mathematical Olympiad junior 2011 Problema 1). Achar todos os números naturais tales que 2n+ 12n+ 2011né un cadrado perfecto. [4] 3.1. OLIMPÍADAS MATEMÁTICAS NACIONAIS 23 Solución Se n= 0 temos que 20+ 120+ 20110= 3 o cal non é un cadrado perfecto. Para n= 1 temos que 21+ 121+ 20111= 2025 = 452. Vexamos agora para n > 1.2n+ 12n+ 2011n≡(−1)n+ 0 + 1 (m´od 3), é dicir, se n par 2n+12n+2011n≡2 (m´od 3) e se n impar 2n+12n+2011n≡0 (m´od 3), polo tanto para que a expresión sexa un cadrado perfecto, nten que ser impar xa que x2≡ {0,1}(m´od 3). Ademais 2n+ 12n+ 2011n≡(2)n+ 0 + 1 (m´od 4), é dicir, se n > 1,2n+ 12n+ 2011n≡3n(m´od 4) que sendo n impar temos que 2n+ 12n+ 2011n≡3 (m´od 4), pero como x2≡ {0,1}(m´od 4) non existe n > 1 para o cal 2n+ 12n+ 2011né un cadrado perfecto. Problema 3.5 (OME 1965 Problema 2).Un número de tres cifras escríbese xyz no sistema de base 7 e zyx no sistema de base 9. Cal é ese número? [7] Solución Se temos que xyz escribese en base 7, teremos que o número en base 10 será x·72+y·7 + z. Do mesmo xeito como o mesmo número en base 9 é zyx, será en base 10 z·92+y·9 + x. Polo tanto x·72+y·7 + z=z·92+y·9 + x, entón 80·z+2·y−48·x= 0, entón 40·z+y−24·x= 0 e, polo tanto, 8·(3·x−5·z) = y. Ademais obsérvese que 8·(3 ·x−5·z)≡y(m´od 9), entón 5·z−3·x≡y (m´od 9), entón 5·z−y≡3·x(m´od 9), polo tanto 5·z−yé un múltiplo de 3, entón 5·z−y≡0 (m´od 3) e, polo tanto, y+z≡0 (m´od 3), entón ou y+z≡0 (m´od 9) ou y+z≡3 (m´od 9) ou y+z≡6 (m´od 9) así que distingamos casos: Se y+z≡0 (m´od 9), entón 3·x≡6·z(m´od 9), entón x≡2·z≡y (m´od 3). Como 0≤x, y, z ≤6temos que se x=y,x=y+ 3 se 0≤y≤3ou y=x+ 3 se 0≤x≤3. Se x=y, entón 40 ·z= 23 ·x, entón x=y=z= 0. Se x=y+ 3, entón 40 ·z= 23 ·x+ 3 que no ten solución natural para x∈ {3,4,5,6}. Se y=x+ 3, entón 40 ·z= 23 ·x−3que no ten solución natural para x∈ {3,4,5,6}. Se y+z≡3 (m´od 9), entón 3·x≡6z+3 (m´od 9), entón x≡2·z+1 ≡y+1 (m´od 3). Como 0≤x, y, z ≤6temos que se x=y+ 1 se 0≤y≤5,x=y+ 4 se 0≤y≤2ou y=x+ 2 se 0≤x≤4. 24 CAPÍTULO 3. PROBLEMAS se x=y+ 1 non ten solución en ningún caso. se x=y+ 4 non ten solución en ningún caso. se y=x+ 2 non ten solución en ningún caso. Se y+z≡6 (m´od 9), entón 3·x≡6z+6 (m´od 9), entón x≡2·z+2 ≡y+2 (m´od 3). Como 0≤x, y, z ≤6temos que se x=y+ 2 se 0≤y≤4,x=y+ 5 se 0≤y≤1ou y=x+ 1 se 0≤x≤5. se x=y+ 2 non ten solución en ningún caso. se x=y+ 5 ten solución para y= 0,x= 5 ez= 3. se y=x+ 1 non ten solución en ningún caso. Problema 3.6 (OME 1976 Problema 4).Demostrar que a suma de 5 cadrados perfectos consecutivos non pode ser un cadrado perfecto. [7] Solución A suma de cadrados perfectos consecutivos sería da forma (n−2)2+ (n−1)2+ n2+ (n+ 1)2+ (n+ 2)2= 5 ·n2+ 10 = 5 ·(n2+ 2), polo que para que esta suma sexa un cadrado perfecto es condición necesaria que 5|(n2+ 2), é dicir n2+ 2 ≡0 (m´od 5). Vemos que para ningún n∈Z5cúmprese a congruencia, polo que queda demostrado. Problema 3.7 (OME 1987 Problema 3).Probar que os binomios 25 ·x+ 31 ·ye 3·x+ 7 ·yson múltiplos de 41 para os mesmos valores de xey. [7] Solución Sexan aebenteiros tales que 25·a+31·b≡0 (m´od 41) se, e só se, multiplicando por 2 temos que 50 ·a+ 62 ·b≡0 (m´od 41), se, e só se, 9·a+ 21 ·b≡0 (m´od 41) se, e só se, 3·a+ 7 ·b≡0 (m´od 41). Problema 3.8 (OME 1971 Problema 7).Demostrar que para todo enteiro positivo n, o número 5n+ 2 ·3n−1+ 1 é múltiplo de 8. [7] Solución Se n= 1 temos que 5 + 2 + 1 = 8 que trivialmente é un múltiplo de 8. Para n > 1impar 5n+2·3n−1+1 ≡(−3)n+2·3n−1+1 ≡3n−1·[2+(−1)n−1·(−3)]+1 (m´od 8). Como n−1≥2par e 32≡1 (m´od 8), entón 3n−1·[2+(−1)n−1·(−3)]+1 ≡ −1+1≡0 (m´od 8). 3.1. OLIMPÍADAS MATEMÁTICAS NACIONAIS 25 Para npar 5n+ 2·3n−1+ 1 ≡(−3)n+2 ·3n−1+1 ≡3n−1·[2 + (−1)n−1·(−3)]+ 1 (m´od 8). Como n−1≥2par e 32≡1 (m´od 8), entón 3n−1·[2+(−1)n−1·(−3)]+1 ≡ 3·5+1≡16 ≡0 (m´od 8). Problema 3.9 (OME 1993 Problema 4).Demostrar que todo número primo distinto de 2 e 5 ten infinitos múltiplos escritos só con uns. [7] Solución Sexa pprimo distinto de 2 e 5, polo tanto (10n, p)=1para todo n∈N, entón como 10ϕ(p)≡1 (m´od p), entón 10ϕ(p)−1≡0 (m´od p)ou o que é o mesmo 10p−1−1≡0 (m´od p), entón pdivide a 99 ···9 |{z} p−1 , entón para pdistinto de 3 sabemos que p|11 ···1 |{z} p−1 . Para p= 3 basta con ver que 1+1+1≡0 (m´od 3), polo tanto 3|111. Ademais obsérvese que para todo pprimo distinto de 2, 3 e 5 p|11 ···1 |{z} n·(p−1) e 3|11 ···1 |{z} n·3 , polo que queda demostrada a premisa do problema. Problema 3.10 (OME 2002 Problema 1).Probar que para calquera primo pdistinto de 2 e 5 existe un múltiplo cuxas cifras son todos noves. [7] Solución É unha demostración análoga ao problema anterior. Problema 3.11 (OME Fase local 2014 Problema 2).Encontrar as 3últimas cifras de 72014. [7] Solución Vexamos canto vale 72014 mod 1000. Polo teorema de Euler, como 7 e 1000 son coprimos, temos que 7ϕ(1000) ≡1 (m´od 1000), como 1000 = 23·53temos que ϕ(1000) = 22·4·52= 400, entón 72014 = (7400)5·714 ≡714 = 849 (m´od 1000). Polo tanto, as 3 últimas cifras de 72014 són 849. Problema 3.12 (OME 2013 Problema 6).Dado un número enteiro nescrito no sistema de numeración decimal, formamos o número enteiro krestando do número formado polas tres últimas cifras de n o número formado polas cífras anteriores restantes. Demostrar que né divisible por 7,11 e13 se, e só se, ktamén o é. [7] Solución Sexa Ao número formado polas 3 últimas cifras de neBo número formado polas cifras restantes. Entón n= 1000 ·B+Aek=A−B. Temos, polo tanto, que 26 CAPÍTULO 3. PROBLEMAS n−k= 1001 ·B= 7 ·11 ·13 ·B. Polo tanto nekson congruentes módulo 7,11 e 13. Problema 3.13 (OME 2012 Problema 1).Determine razoadamente se o número √3·n2+ 2 ·n+ 2 é irracional para todo n enteiro non negativo. [7] Solución Vexamos se existe anatural distinto de 0 tal que 3·n2+ 2 ·n+ 2 = a2. Como a2 mod 8 ∈ {0,1,4}vexamos os valores que toma 3·n2+ 2 ·n+ 2 mod 8 respecto a n. nmod 8=0: 3·n2+ 2 ·n+ 2 mod 8 = 2 nmod 8=1: 3·n2+ 2 ·n+ 2 mod 8 = 7 nmod 8=2: 3·n2+ 2 ·n+ 2 mod 8 = 2 nmod 8=3: 3·n2+ 2 ·n+ 2 mod 8 = 3 nmod 8=4: 3·n2+ 2 ·n+ 2 mod 8 = 2 nmod 8=5: 3·n2+ 2 ·n+ 2 mod 8 = 7 nmod 8=6: 3·n2+ 2 ·n+ 2 mod 8 = 2 nmod 8=7: 3·n2+ 2 ·n+ 2 mod 8 = 3 Polo tanto 3·n2+ 2 ·n+ 2 non é un cadrado perfecto. 3.2. Olimpíada matemática internacional Problema 3.14 (IMO shortlist 1994 Problema 24).Dicimos que un número enteiro positivo é un número ondulante se os seus díxitos en base 10 son alternativamente cero e distinto de cero, sendo o díxito das unidades distinto de cero. Determinar todos os enteiros positivos que non dividen a ningún número ondulante. [5] Solución É sinxelo ver que os números divisibles entre 10 e25 non poden dividir aos números ondulantes xa que ditos números acaban en 0e25 respectivamente, polo tanto, nin 10 nin 25 poden dividir a ningún divisor dun número ondulante. 3.2. OLIMPÍADA MATEMÁTICA INTERNACIONAL 27 Vexamos o caso de que nin 2nin 5dividen ao candidato a divisor n: Como xa sabemos (2, n) = (5, n) = 1, entón (10k, n)=1, obsérvese ademais que (10k− 1,10k)=1xa que se non fora así podemos tomar ddivisor común de 10k−1e10ktal que 10k−1≡10k(m´od d), entón −1≡0 (m´od d)o cal é imposible. Polo teorema de Euler tense que (10k)ϕ(n)≡1 (m´od n), ademais temos que 10k−1|10k·ϕ(n), entón 10k·ϕ(n)−1≡0 (m´od 10k−1), entón (10k)ϕ(n)−1 = t0·ne(10k)ϕ(n)−1 = t00 ·(10k−1) e como n e 10k−1son coprimos podemos tomar t000 =t0/(10k−1) de xeito que (10k)ϕ(n)−1 = t0·n=t000 ·(10k−1) ·n, entón (10k)ϕ(n)−1≡0 (m´od 10k−1) ·n, entón A(k, n) = (10k)ϕ(n)−1/10k−1é un múltiplo de nque está formado por uns separados por k−1ceros, polo que para k= 1 temos un número ondulante múltiplo de n. Se 5|nrecordando que nin 10 nin 25 poden dividir a nxa que nese caso xa sabemos que non é posible, A(2, n/5) é un múltiplo ondulante de n/5, entón 5·A(2, n/5) é un múltiplo ondulante de n. Vexamos agora se n= 22·r+1 ten un múltiplo ondulante. Primeiro vexamos que 8é un múltiplo ondulante de 8, polo que sabemos que para t= 1,22·t+1 ten un múltiplo ondulante de 2·t−1cifras. Supoñamos que isto e certo para t=ke vexamos que pasa para t=k+ 1. Sexa Amúltiplo ondulante de 22·k+1 con 2·k−1 cifras, polo tanto B(k+ 1) = 102·k·b+Aé un número ondulante para b∈ {1, ... , 9} e102·k·b+A= 102·k·b+22·k+1 ·b0= 22·k·(52·k·b+2·a). Polo tanto para que B(k+1) sexa múltiplo de 22·k+3 tense que cumprir que 52·k·b+ 2 ·a≡0 (m´od 8) e como 52≡2 (m´od 8) temos que 2·b+ 2 ·a≡0 (m´od 8), entón b+a≡0 (m´od 4). Por último obsérvese que os números da forma 22·k+1 ·mpara rnatural e m non é múltiplo de 5 o produto de A(2 ·k+ 1, m)·B(k)é un múltiplo ondulante de 22·k+1 ·m. Problema 3.15 (IMO 1959 Problema 1).Proba que 21n+4 14n+3 é irreducible para todo n∈N. [5] Solución Supoñamos que 21n+4 14n+3 é reducible para algún n∈N, entón 21n+ 4 ≡0 (m´od s)e14n+ 3 ≡0 (m´od s)para algún s6= 1 divisor común de 21n+ 4 e 14n+ 3. Polo tanto podemos dicir que 21n+ 4 −(14n+ 3) = 7n+ 1 ≡0 (m´od s) e por tanto 7n≡ −1 (m´od s). Agora temos que 3·(7n−1) ≡0 (m´od s)é dicir 21n−3≡0 (m´od s)e como 21n−4≡0 (m´od s)e aplicando a propiedade transitiva, obtemos que: 21n−4≡21n−3 (m´od s)se, e só se, −4≡ −3 (m´od s)se, e só se, −1≡0 28 CAPÍTULO 3. PROBLEMAS (m´od s). [3] Problema 3.16 (IMO 1960 Problema 1).Determinar todo-los números de 3 díxitos Ndivisibles entre 11 e que N 11 é igual a suma dos cadrados dos díxitos de N. [5] Solución Digamos que N=abc = 100a+ 10b+ce sabemos que 100a+ 10b+c≡0 (m´od 11). Como 10 ≡ −1 (m´od 11) aplicando el corolario 1.13 podemos dicir que a−b+c≡0 (m´od 11) e disto seguese que, ou b=a+cou b=a+c−11 xa que −9≤a−b+c≤18. Caso b=a+c: 100a+10(a+c)+c 11 =110a+11c 11 = 10a+c=N 11 =a2+ (a+c)2+c2= 2a2+ 2ac + 2c2, entón 2a2+ (2c−10)a+ (2c2−c) = 0, entón a=10−2c±√(2c−10)2−4·2·(2c2−c) 4= 10−2c±√−12c2−32c+100 4. Como −12c2−32c+ 100 só é positivo para c= 0 ec= 1 e para c= 1 −12c2−32c+ 100 = 66 con raíz irracional c= 0, entón a= 0 ou a= 5. Se a= 0, entón b= 0, polo que o número resultante será o 000 e se a= 5, entón b= 5, polo que o número resultante será o 550 Caso b=a+c−11: 100a+10(a+c−11)+c 11 =110a+11c−110 11 = 10a+c−10 = N 11 =a2+ (a+c−11)2+c2= 2a2+ 2ac + 2c2−22a−22c, entón 2a2+ (2c−32)a+ (2c2−23c+ 131) = 0, entón a=32−2c±√(2c−32)2−4·2·(2c2−23c+131) 4=32−2c±√−12c2−56c−24 4. Como −12c2−56c−24 só é positivo para c= 1,c= 2,c= 3 ec= 4. Para c= 1 −12c2−56c−24 = 24 con raíz irracional, para c= 2 −12c2−56c−24 = 40 con raíz irracional, para c= 3 −12c2−56c−24 = 36 con raíz 6e para c= 4 −12c2−56c−24 = 8 con raíz irracional, entón c= 3, entón a= 8 oa= 5. Se a= 8, entón b= 0 resultando no número 803 e se a= 5, entón b=−3, polo que non é posíbel. [3] Polo tanto as solucións ó problema salvo a trivial serán 550 e803. Problema 3.17 (IMO 1975 Problema 4).Cando 44444444 escríbese en notación decimal dicimos que a suma dos seus díxitos é A. Sexa ademais Ba suma dos díxitos de A. Calcula a suma dos díxitos de B. [5] Demostración. Notemos primeiro que como 44444444 <100004444 = 1017776, polo que 44444444 ten como moito 17776 cifras de xeito que A < 9·17775 = 159975, entón B≤45 e, polo tanto, a suma das cifras de Bé como moito 12. 3.3. OUTROS PROBLEMAS 29 Ademais sabemos que 44444444 ≡A≡B(m´od 9) ademais vexamos que 4444 ≡ 7 (m´od 9),44442≡4 (m´od 9) e44443≡1 (m´od 9) e ademais 4444 = 3·1481+1, polo tanto 44444444 ≡4444 ≡7 (m´od 9), entón a suma dos díxitos de Bda 7. [3] Problema 3.18 (IMO 1978 Problema 1978).Sexan menenteiros positivos tales que 1≤m<n. Os últimos 3 díxitos de 1978mcoinciden cos últimos 3 díxitos de 1978nnas súas representacións decimais. Encontra mentales que m+nteñan valor mínimo. [5] Problema 3.19 (IMO 1983 Problema 3).Sexan a, b, c enteiros positivos coprimos dous a dous. Demostra que 2·a·b·c−a·b−b·c−c·aé o maior enteiro que non pode ser expresado da forma x·b·c+y·c·a+z·a·bsendo a y z enteiros non negativos. [5] Problema 3.20 (IMO 1986 Problema 1).Sexa dcalquera enteiro positivo distinto de 2, 5 ou 13. Demostra que se pode encontrar a, b ∈ {2,5,13, d}tal que a·b−1non sexa un cadrado perfecto. [5] Problema 3.21 (IMO 2000 Problema 5).Existe algún enteiro positivo ntal que teña exactamente 2000 divisores primos e divida a 2n+ 1? [5] Problema 3.22 (IMO 1964 problema 1).(a) Encontra todos os enteiros npara os cales 2n−1é divisible entre 7. (b) Proba que non existe ningún enteiro positivo npara os cales 2n+ 1 son divisibles entre 7. [5] Solución Os residuos asociados a 2nson {21mod 7 = 2,22mod 7 = 4,23mod 7 = 1}, polo tanto cúmprese que 2n−1é un múltiplo de 7 sé e só se né un múltiplo de 3. Ademais como xa coñecemos os residuos de 2nvexamos que ao sumarlles 1 ningún da un múltiplo de 7. 3.3. Outros problemas Problema 3.23.Dado un número natural n, denotaremos s(n)como a suma dos díxitos de n. Achar todas as solucións de la ecuación n+s(n) + s(s(n)) = 2018 [4]