{"id":849,"date":"2026-02-25T11:15:49","date_gmt":"2026-02-25T10:15:49","guid":{"rendered":"https:\/\/clases.jesussoto.es\/?p=849"},"modified":"2026-02-26T10:31:25","modified_gmt":"2026-02-26T09:31:25","slug":"mad-congruencias-con-maxima","status":"publish","type":"post","link":"https:\/\/clases.jesussoto.es\/?p=849","title":{"rendered":"MAD: Congruencias con maxima"},"content":{"rendered":"<h2>Restos potenciales<\/h2>\n<p>Veamos el siguiente ejercicio:<\/p>\n<blockquote>\n<p><strong>Ejemplo:<\/strong> Dado \\(n=71\\cdots 71\\), donde la pareja 71 se repite 10 veces, \u00bfcu\u00e1l es su resto al dividirlo por 17? <\/p>\n<\/blockquote>\n<p><script>\nfunction showHtmlDiv2() {\n  var htmlShow2 = document.getElementById(\"html-show2\");\n  if (htmlShow2.style.display === \"none\") {\n    htmlShow2.style.display = \"block\";\n  } else {\n    htmlShow2.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv2()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show2\" style=\"display: none;\">\nEl n\u00famero en cuesti\u00f3n es \\(71717171717171717171\\) y el problema nos plantea: encontrar la soluci\u00f3n de la ecuaci\u00f3n \\[71717171717171717171\\equiv X\\pmod{17}.\\] Para resolverlo tendremos que calcular su resto al dividirlo por 17. Utilicemos las propiedades de divisibilidad:\\[71717171717171717171=71717\\cdot 10^{15}+17171\\cdot 10^{10}+71717\\cdot 10^5+17171\\] Sabemos que \\(71717=\\dot{17}+11\\), \\(17171=\\dot{17}+1\\), luego \\[71717171717171717171\\equiv r\\pmod{17}\\] donde \\(r\\) es el mismo resto que \\[11\\cdot 10^{15}+1\\cdot 10^{10}+11\\cdot 10^5+1\\equiv r\\pmod{17}\\] Realicemos lo mismo para \\(10^{i}\\), con \\(i=5,10,15\\) y tendremos \\[11\\cdot 12+1\\cdot 2+11\\cdot 6+1\\equiv r\\pmod{17},\\] obteniendo que \\(r=14\\).\n<\/div>\n<hr \/>\n<p>Para resolverlo hemos tenido que calcular \\( 10^i\\pmod{17}\\) para \\(i=5,10,15\\). Si lo analizamos desde el punto de vista de resolver \\( 10^i\\pmod{17},\\, \\forall i\\in\\mathbb{Z}^+\\) estaremos planteando un problema de restos potenciales. Los restos potenciales son los residuos positivos que resultan de dividir las potencias sucesivas de un n\u00famero entero (base) por otro n\u00famero positivo (m\u00f3dulo). Estos restos se repiten c\u00edclicamente (periodo) o se vuelven cero, formando secuencias peri\u00f3dicas puras o mixtas menores que el m\u00f3dulo, \u00fatiles para resolver problemas complejos de divisibilidad. <\/p>\n<blockquote><p>\n<strong>Definici\u00f3n:<\/strong> Sean \\(a,n\\in\\mathbb{Z}^+\\), llamamos restos potenciales de \\(a\\) m\u00f3dulo \\(n\\) a los restos \\[a^i\\equiv r_i\\pmod{n},\\, \\forall i\\in\\mathbb{Z}^+\\]\n<\/p><\/blockquote>\n<p>Como veremos, estos restos son c\u00edclicos y, por tanto, el n\u00famero de restos distintos es finito.<\/p>\n<blockquote>\n<p><strong>Ejercicio:<\/strong> Determinar el resto de la divisi\u00f3n de \\(751^{157}\\) entre 22.<\/p>\n<\/blockquote>\n<p><script>\nfunction showHtmlDiv4a() {\n  var htmlShow4a = document.getElementById(\"html-show4a\");\n  if (htmlShow4a.style.display === \"none\") {\n    htmlShow4a.style.display = \"block\";\n  } else {\n    htmlShow4a.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv4a()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show4a\" style=\"display: none;\">\nObservemos que el problema es equivalentes a resolver la ecuaci\u00f3n \\(751^{157}\\equiv X {\\pmod {22}} \\). Como \\(751\\equiv 3 {\\pmod {22}} \\), resultar\u00e1 \\[751^{157}\\equiv 3^{157} {\\pmod {22}}\\] Por tanto, tendremos que calcular los restos potenciales de 3 m\u00f3dulo 22:<br \/>\n\\[\\begin{align*}  3^{5n}&#038;\\equiv 1 {\\pmod {22}} \\\\  3^{5n+1}&#038;\\equiv 3 {\\pmod {22}} \\\\ 3^{5n+2}&#038;\\equiv 9 {\\pmod {22}} \\\\ 3^{5n+3}&#038;\\equiv 5 {\\pmod {22}} \\\\ 3^{5n+4}&#038;\\equiv 15 {\\pmod {22}}  \\end{align*}\\]<br \/>\nSi tenemos en cuenta que \\(157=5n+2\\Leftrightarrow 157\\equiv 2\\pmod{5}\\), ser\u00e1<br \/>\n\\[3^{157}=3^{5n+2}\\equiv 3^{2}\\equiv 9 {\\pmod {22}}\\]\n<\/div>\n<hr \/>\n<p>Estos restos cumplen las siguientes propiedades: \\[\\begin{align*} a^0 &#038;\\equiv 1{\\pmod{n}} \\\\ a &#038;\\equiv a{\\pmod{n}} \\\\ a^k&#038;\\equiv r_k{\\pmod{n}}\\Rightarrow a^{k+1}\\equiv a\\cdot r_k{\\pmod{n}} \\end{align*}\\]<\/p>\n<p>Adem\u00e1s a partir de un resto que se repiten, se repiten todos en forma c\u00edclica.<\/p>\n<blockquote>\n<p><strong>Ejercicio:<\/strong> Verifica si es cierta o no la afirmaci\u00f3n: \u00abPara todo \\(n\\) natural \\(6^{n}-1\\) es divisible entre 5\u00bb.<\/p>\n<\/blockquote>\n<p><script>\nfunction showHtmlDiv4a5() {\n  var htmlShow4a5 = document.getElementById(\"html-show4a5\");\n  if (htmlShow4a5.style.display === \"none\") {\n    htmlShow4a5.style.display = \"block\";\n  } else {\n    htmlShow4a5.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv4a5()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show4a5\" style=\"display: none;\">\nCalculemos los restos potenciales de 6 m\u00f3dulo 5:<br \/>\n\\[\\begin{align*}  6^{0}&#038;\\equiv 1 {\\pmod {5}} \\\\   6^{1}&#038;\\equiv 1 {\\pmod {5}}  \\end{align*},\\]<br \/>\nluego para todo \\(n\\in\\mathbb{Z}^+\\) \\[6^n\\equiv 1\\pmod{5}\\Rightarrow 5|(6^n-1)\\]\n<\/div>\n<hr \/>\n<blockquote>\n<p><strong>Ejercicio:<\/strong> Crear una funci\u00f3n,\\(\\mathbf{restos}(a,n)\\), que devuelva los restos potenciales de \\(a\\) m\u00f3dulo \\(n\\).<\/p>\n<\/blockquote>\n<p><script>\nfunction showHtmlDiv4a5x() {\n  var htmlShow4a5x = document.getElementById(\"html-show4a5x\");\n  if (htmlShow4a5x.style.display === \"none\") {\n    htmlShow4a5x.style.display = \"block\";\n  } else {\n    htmlShow4a5x.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv4a5x()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show4a5x\" style=\"display: none;\">\n<table>\n<tr style=\"border: 0px;\">\n<td style=\"width: 70px;vertical-align: top;padding: 1mm;\"><span class=\"prompt\">(%i2)<\/span><\/td>\n<td style=\"vertical-align: top;padding: 1mm;\"><span class=\"input\"><span class=\"code_function\">restos<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">n<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">m<\/span><span class=\"code_operator\">)<\/span><span class=\"code_operator\">:<\/span><span class=\"code_operator\">=<\/span><span class=\"code_function\">block<\/span><span class=\"code_operator\">(<\/span><span class=\"code_operator\">[<\/span><span class=\"code_variable\">r<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">proximo<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">repetido<\/span><span class=\"code_operator\">]<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0 <span class=\"code_variable\">r<\/span><span class=\"code_operator\">:<\/span><span class=\"code_operator\">[<\/span><span class=\"code_number\">1<\/span><span class=\"code_operator\">]<\/span><span class=\"code_endofline\">,<\/span> \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0 <span class=\"code_variable\">proximo<\/span><span class=\"code_operator\">:<\/span><span class=\"code_function\">mod<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">n<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">m<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">,<\/span> \u00a0\u00a0 <span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0 <span class=\"code_variable\">repetido<\/span><span class=\"code_operator\">:<\/span><span class=\"code_function\">false<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0 <span class=\"code_function\">while<\/span><span class=\"code_function\">not<\/span><span class=\"code_variable\">repetido<\/span><span class=\"code_function\">do<\/span><span class=\"code_operator\">(<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <span class=\"code_comment\">\/* Primero a\u00f1adimos el n\u00famero, sea cual sea *\/<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <span class=\"code_variable\">r<\/span><span class=\"code_operator\">:<\/span><span class=\"code_function\">append<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">r<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_operator\">[<\/span><span class=\"code_variable\">proximo<\/span><span class=\"code_operator\">]<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <span class=\"code_comment\">\/* Calculamos el que vendr\u00eda despu\u00e9s *\/<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <span class=\"code_variable\">proximo<\/span><span class=\"code_operator\">:<\/span><span class=\"code_function\">mod<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">proximo<\/span><span class=\"code_operator\">\u00b7<\/span><span class=\"code_variable\">n<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">m<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <span class=\"code_comment\">\/* Comprobamos si ese \u00abproximo\u00bb ya existe en nuestra lista *\/<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <span class=\"code_function\">if<\/span><span class=\"code_function\">member<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">proximo<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">r<\/span><span class=\"code_operator\">)<\/span><span class=\"code_function\">then<\/span><span class=\"code_operator\">(<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <span class=\"code_comment\">\/* Si ya existe, lo a\u00f1adimos UNA \u00faltima vez para ver el cierre *\/<\/span><span class=\"code_endofline\"><br \/><\/span>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <span class=\"code_variable\">r<\/span><span class=\"code_operator\">:<\/span><span class=\"code_function\">append<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">r<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_operator\">[<\/span><span class=\"code_variable\">proximo<\/span><span class=\"code_operator\">]<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <span class=\"code_variable\">repetido<\/span><span class=\"code_operator\">:<\/span><span class=\"code_function\">true<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <span class=\"code_operator\">)<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0 <span class=\"code_operator\">)<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0 <span class=\"code_variable\">r<\/span><span class=\"code_endofline\"><br \/><\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">$<\/span><span class=\"code_endofline\"><br \/><\/span><span class=\"code_function\">restos<\/span><span class=\"code_operator\">(<\/span><span class=\"code_number\">10<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">16<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">;<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p>\\[\\left[ 1{,}10{,}4{,}8{,}0{,}0\\right] \\]<\/p>\n<p>Observar que la funci\u00f3n devuelve el \u00faltimo valor que se repite. Si el \u00faltimo es igual al pen\u00faltimo no dice que a partir del pen\u00faltimo, todos son iguales. Si no coincide, entonces es c\u00edclico.\n<\/p><\/div>\n<hr \/>\n<blockquote><p><strong>Ejercicio:<\/strong> Calcular el resto potencial de \\(4^{68}\\pmod{57}\\)<\/p><\/blockquote>\n<p><script>\nfunction showHtmlDiv4b() {\n  var htmlShow4b = document.getElementById(\"html-show4b\");\n  if (htmlShow4b.style.display === \"none\") {\n    htmlShow4b.style.display = \"block\";\n  } else {\n    htmlShow4b.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv4b()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show4b\" style=\"display: none;\">\n<div class=\"comment\">Primero calcularemos los restos potenciales de 4 m\u00f3dulo 57, utilizando la funci\u00f3n anterio.<\/div>\n<p><!-- Code cell --><\/p>\n<table>\n<tr style=\"border: 0px;\">\n<td style=\"width: 70px;vertical-align: top;padding: 1mm;\"><span class=\"prompt\">(%i4)<\/span><\/td>\n<td style=\"vertical-align: top;padding: 1mm;\"><span class=\"input\"><span class=\"code_variable\">r<\/span><span class=\"code_operator\">:<\/span><span class=\"code_function\">restos<\/span><span class=\"code_operator\">(<\/span><span class=\"code_number\">4<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">57<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">;<\/span><span class=\"code_endofline\"><br \/><\/span><span class=\"code_variable\">ciclo<\/span><span class=\"code_operator\">:<\/span><span class=\"code_function\">length<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">r<\/span><span class=\"code_operator\">)<\/span><span class=\"code_operator\">\u2212<\/span><span class=\"code_number\">1<\/span><span class=\"code_endofline\">;<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p>\\[{ }\\left[ 1{,}4{,}16{,}7{,}28{,}55{,}49{,}25{,}43{,}1\\right] \\]<\/p>\n<p>\\[{ }9\\]<\/p>\n<p><!-- Code cell --><\/p>\n<table>\n<tr style=\"border: 0px;\">\n<td style=\"width: 70px;vertical-align: top;padding: 1mm;\"><span class=\"prompt\">(%i6)<\/span><\/td>\n<td style=\"vertical-align: top;padding: 1mm;\"><span class=\"input\"><span class=\"code_function\">mod<\/span><span class=\"code_operator\">(<\/span><span class=\"code_number\">68<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">ciclo<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">;<\/span><span class=\"code_comment\">\/* este es el exponente de 4 modulo 57 *\/<\/span><span class=\"code_endofline\"><br \/><\/span><span class=\"code_variable\">r<\/span><span class=\"code_operator\">[<\/span><span class=\"code_variable\">%<\/span><span class=\"code_operator\">+<\/span><span class=\"code_number\">1<\/span><span class=\"code_operator\">]<\/span><span class=\"code_endofline\">;<\/span><span class=\"code_comment\">\/* la posici\u00f3n que ocupa en los restos potenciales de 4 modulo 57*\/<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p>\\[{ }5\\]<\/p>\n<p>\\[{ }55\\]<\/p>\n<\/div>\n<hr \/>\n<p>Uno de los problemas es determinar cu\u00e1ndo se produce el ciclo. Para resolverlo no ayudaremos de la funci\u00f3n fi de Euler:<\/p>\n<blockquote>\n<p><strong>Teorema de Euler:<\/strong> Si \\(a,n\\in\\mathbb{Z}\\) con \\(\\mathbf{mcd}(n,a)=1\\), entonces \\(a^{\\varphi (n)}\\equiv 1{\\pmod {p}}\\)<\/p>\n<\/blockquote>\n<h2>Ecuaci\u00f3n de congruencias<\/h2>\n<p>Nuestro prop\u00f3sito principal es resolver la ecuaci\u00f3n de congruencias \\(aX\\equiv b {\\pmod {n}}\\). Si \\(mcd(n,a)=1\\), vimos que podemos utilizar la soluci\u00f3n de Bezout para resolverlo:<\/p>\n<blockquote>\n<p><strong>Ejemplo:<\/strong> Resolver la ecuaci\u00f3n \\[7X\\equiv 3 {\\pmod {103}}\\] <\/p>\n<\/blockquote>\n<p><script>\nfunction showHtmlDiv2d3w() {\n  var htmlShow2d3w = document.getElementById(\"html-show2d3w\");\n  if (htmlShow2d3w.style.display === \"none\") {\n    htmlShow2d3w.style.display = \"block\";\n  } else {\n    htmlShow2d3w.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv2d3w()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show2d3w\" style=\"display: none;\">\n<!-- Code cell --><\/p>\n<table>\n<tr style=\"border: 0px;\">\n<td style=\"width: 70px;vertical-align: top;padding: 1mm;\"><span class=\"prompt\">(%i5)<\/span><\/td>\n<td style=\"vertical-align: top;padding: 1mm;\"><span class=\"input\"><span class=\"code_variable\">ex<\/span><span class=\"code_operator\">:<\/span><span class=\"code_function\">eucl_ext<\/span>(<span class=\"code_number\">7<\/span>,<span class=\"code_number\">103<\/span>)<span class=\"code_endofline\">;<\/span><br \/>if <span class=\"code_variable\">ex<\/span>[<span class=\"code_number\">1<\/span>]&lt;<span class=\"code_number\">0<\/span> then <span class=\"code_variable\">inv<\/span><span class=\"code_operator\">:<\/span><span class=\"code_function\">mod<\/span>(<span class=\"code_variable\">ex<\/span>[<span class=\"code_number\">1<\/span>],<span class=\"code_number\">103<\/span>) else <span class=\"code_variable\">inv<\/span><span class=\"code_operator\">:<\/span><span class=\"code_variable\">ex<\/span>[<span class=\"code_number\">1<\/span>]<span class=\"code_endofline\">$<\/span><br \/><span class=\"code_variable\">sol<\/span><span class=\"code_operator\">:<\/span><span class=\"code_function\">mod<\/span>(<span class=\"code_variable\">inv<\/span><span class=\"code_operator\">*<\/span><span class=\"code_number\">3<\/span>,<span class=\"code_number\">103<\/span>)<span class=\"code_endofline\">$<\/span><br \/><span class=\"code_function\">print<\/span>(<span class=\"code_string\">\u00abSoluci\u00f3n X=\u00bb<\/span>,<span class=\"code_variable\">sol<\/span>,<span class=\"code_string\">\u00ab(103)\u00bb<\/span>)<span class=\"code_endofline\">$<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p><math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"block\"><mtable><mlabeledtr columnalign=\"left\"><mtd><mtext>(ex)<\/mtext><\/mtd><mtd><mo>[<\/mo><mi>\u2212<\/mi><mn>44<\/mn><mo>,<\/mo><mn>3<\/mn><mo>,<\/mo><mn>1<\/mn><mo>]<\/mo><\/mtd><\/mlabeledtr><mlabeledtr columnalign=\"left\"><mtd><mtext\/><\/mtd><mtd><mo>Soluci\u00f3n X=<\/mo><mo\/><mn>74<\/mn><mo\/><mo>(103)<\/mo><mo\/><\/mtd><\/mlabeledtr><\/mtable><\/math><!-- Text cell --><\/p>\n<div class=\"comment\">\n<p>Verifiqu\u00e9moslo:<\/p>\n<\/div>\n<p><!-- Code cell --><\/p>\n<table>\n<tr style=\"border: 0px;\">\n<td style=\"width: 70px;vertical-align: top;padding: 1mm;\"><span class=\"prompt\">(%i6)<\/span><\/td>\n<td style=\"vertical-align: top;padding: 1mm;\"><span class=\"input\"><span class=\"code_function\">mod<\/span>(<span class=\"code_number\">7<\/span><span class=\"code_operator\">*<\/span><span class=\"code_variable\">sol<\/span>,<span class=\"code_number\">103<\/span>)<span class=\"code_endofline\">;<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p><math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"block\"><mtable><mlabeledtr columnalign=\"left\"><mtd><mtext>(%o6) <\/mtext><\/mtd><mtd><mn>3<\/mn><\/mtd><\/mlabeledtr><\/mtable><\/math>\n<\/div>\n<hr \/>\n<p>Sin embargo, si \\(mcd(n,a)=1\\) tenemos una herramienta poderosa: el <strong>teorema de Euler<\/strong>. Utiliz\u00e1ndolo, tendremos<\/p>\n<p>\\[aX\\equiv b {\\pmod {n}}\\to a^{\\varphi (n)-1}aX\\equiv a^{\\varphi (n)-1}b {\\pmod {n}}\\to X\\equiv a^{\\varphi (n)-1}b {\\pmod {n}},\\]<\/p>\n<p>con lo que obtendremos la soluci\u00f3n antes.<\/p>\n<blockquote>\n<p><strong>Ejemplo:<\/strong> Resolver \\(5X\\equiv 12 {\\pmod {21}}\\)<\/p>\n<\/blockquote>\n<p><script>\nfunction showHtmlDiv2b() {\n  var htmlShow2b = document.getElementById(\"html-show2b\");\n  if (htmlShow2b.style.display === \"none\") {\n    htmlShow2b.style.display = \"block\";\n  } else {\n    htmlShow2b.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv2b()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show2b\" style=\"display: none;\">\nNecesitamos encontrar el inverso de 5 en \\(\\mathbb{Z}_{21}\\), ya para ello utilizamos el teorema de Euler: \\[5\\cdot 5^{(\\varphi(21)-1)}\\equiv 1{\\pmod {21}}\\] Ahora \\(\\varphi(21)=(3-1)(7-1)=12\\), de modo que \\[5^{11}\\equiv 17{\\pmod {21}}.\\]<br \/>\nSolo nos falta aplicarlo \\[5X\\equiv 12 {\\pmod {21}}\\to X\\equiv 17\\cdot 12\\equiv 15{\\pmod {21}}\\]\n<\/div>\n<hr \/>\n<blockquote>\n<p><strong>Ejemplo:<\/strong> Resolver \\(6X\\equiv 22 {\\pmod {77}}\\)<\/p>\n<\/blockquote>\n<p><script>\nfunction showHtmlDiv2c() {\n  var htmlShow2c = document.getElementById(\"html-show2c\");\n  if (htmlShow2c.style.display === \"none\") {\n    htmlShow2c.style.display = \"block\";\n  } else {\n    htmlShow2c.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv2c()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show2c\" style=\"display: none;\">\nNecesitamos encontrar el inverso de 6 en \\(\\mathbb{Z}_{77}\\), que existe pues \\(\\mathbf{mcd}(6,77)=1\\). Por el teorema de Euler: \\[6\\cdot 6^{(\\varphi(77)-1)}\\equiv 1{\\pmod {77}}\\] Ahora \\(\\varphi(77)=(7-1)(11-1)=60\\), de modo que tenemos que determinar \\[6^{59}\\equiv X_0 {\\pmod {77}}.\\]<\/p>\n<p>El teorema de Euler nos garantizaba que \\(6^{60}\\equiv 1 {\\pmod {77}}\\), pero no nos garantiza que 60 sea el primer entero, \\(n\\), tal que \\(6^{n}\\equiv 1 {\\pmod {77}}\\); es decir, puede existir un entero m\u00e1s peque\u00f1o que lo cumpla. Ahora si \\(n\\) es tal que \\(6^{n}\\equiv 1 {\\pmod {77}}\\), entonces \\(n|60\\). Probemos con los divisores de 60: [1, 5, 3, 15, 2, 10, 6, 30, 4, 20, 12, 60]<\/p>\n<p>\\[\\begin{align*}  6^2&#038;\\equiv 36 (77)\\\\   6^3&#038;\\equiv 62 (77)\\\\   6^4&#038;\\equiv 64 (77)\\\\   6^5&#038;\\equiv 76 (77)\\\\   6^6&#038;\\equiv 71 (77)\\\\   6^{10}&#038;\\equiv 1 (77) \\end{align*}\\]<\/p>\n<p>Es decir, ser\u00e1 suficiente con: 59=5*10+9, \\[6^{59}\\equiv 6^{9}\\equiv 13 {\\pmod {77}}.\\]<\/p>\n<p>Solo nos falta aplicarlo: \\[6X\\equiv 22 {\\pmod {77}}\\to X\\equiv 13\\cdot 22\\equiv 55{\\pmod {77}}\\]\n<\/p><\/div>\n<hr \/>\n<p>Si el m\u00f3dulo en cuesti\u00f3n es primo, la ecuaci\u00f3n es m\u00e1s simple:<\/p>\n<blockquote>\n<p><strong>Teorema de Fermat:<\/strong> Si \\(p\\) es primo y \\(p\\not\\,\\!|\\,a\\) entonces, \\(a^{ (p-1)}\\equiv 1{\\pmod {p}}\\) <\/p>\n<\/blockquote>\n<p>Aunque anterior, este resultado se puede demostrar como consecuencia del Teorema de Euler y ser\u00e1 muy importante a la hora de encontrar los restos potenciales y ver cu\u00e1ndo se reproduce el ciclo.<\/p>\n<blockquote>\n<p><strong>Ejemplo:<\/strong> Resolver \\(7X\\equiv 22 {\\pmod {31}}\\)<\/p>\n<\/blockquote>\n<p><script>\nfunction showHtmlDiv2ae3() {\n  var htmlShow2ae3 = document.getElementById(\"html-show2ae3\");\n  if (htmlShow2ae3.style.display === \"none\") {\n    htmlShow2ae3.style.display = \"block\";\n  } else {\n    htmlShow2ae3.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv2ae3()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show2ae3\" style=\"display: none;\">\nNecesitamos encontrar el inverso de 7 en \\(\\mathbb{Z}_{31}\\), ya para ello podemos utilizar el teorema de Fermat: \\[7\\cdot 7^{29}\\equiv 1{\\pmod {31}}\\] Ahora simplificamos como creamos conveniente; por ejemplo, 29=5*5+4, luego \\[7^{29}\\equiv (7^5)^57^4\\equiv 5^5\\cdot 14\\equiv 25\\cdot 14\\equiv 9{\\pmod {31}}\\]<\/p>\n<p>Solo nos falta aplicarlo \\[7X\\equiv 22 {\\pmod {31}}\\to X\\equiv 9\\cdot 22\\equiv 12{\\pmod {31}}\\]\n<\/p><\/div>\n<hr \/>\n<p>Recordemos que si \\(n\\in\\mathbb{Z}\\) es \\({\\displaystyle n=p_{1}^{k_{1}}\\cdots p_{r}^{k_{r}}}\\), entonces \\[\\varphi (n)=n\\prod_{i=1}^r\\left(1-\\frac{1}{p_i}\\right)\\]<\/p>\n<blockquote>\n<p><strong>Ejemplo:<\/strong> Utilizar la f\u00f3rmula anterior para construir un algoritmo que calcule \\(\\varphi(87)\\)<\/p>\n<\/blockquote>\n<p><script>\nfunction showHtmlDiv2d8() {\n  var htmlShow2d8 = document.getElementById(\"html-show2d8\");\n  if (htmlShow2d8.style.display === \"none\") {\n    htmlShow2d8.style.display = \"block\";\n  } else {\n    htmlShow2d8.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv2d8()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show2d8\" style=\"display: none;\">\n<!-- Code cell --><!-- Code cell --><\/p>\n<table>\n<tr style=\"border: 0px;\">\n<td style=\"width: 70px;vertical-align: top;padding: 1mm;\"><span class=\"prompt\">(%i1)\t<\/span><\/td>\n<td style=\"vertical-align: top;padding: 1mm;\"><span class=\"input\"><span class=\"code_function\">fiEuler<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">n<\/span><span class=\"code_operator\">)<\/span><span class=\"code_operator\">:<\/span><span class=\"code_operator\">=<\/span><span class=\"code_function\">block<\/span><span class=\"code_operator\">(<\/span><span class=\"code_operator\">[<\/span><span class=\"code_variable\">result<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">d<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">p<\/span><span class=\"code_operator\">]<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0 <span class=\"code_variable\">result<\/span><span class=\"code_operator\">:<\/span><span class=\"code_variable\">n<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0 <span class=\"code_variable\">p<\/span><span class=\"code_operator\">:<\/span><span class=\"code_variable\">n<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0 <span class=\"code_variable\">d<\/span><span class=\"code_operator\">:<\/span><span class=\"code_number\">2<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0 <span class=\"code_function\">while <\/span><span class=\"code_variable\">d<\/span><span class=\"code_endofline\"> &lt; <\/span><span class=\"code_function\">sqrt<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">p<\/span><span class=\"code_operator\">)<\/span><span class=\"code_function\"> do <\/span><span class=\"code_operator\">(<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <span class=\"code_function\">if<\/span><span class=\"code_function\"> mod<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">p<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">d<\/span><span class=\"code_operator\">) <\/span><span class=\"code_operator\">=<\/span><span class=\"code_number\">0<\/span><span class=\"code_function\"> then <\/span><span class=\"code_operator\">(<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <span class=\"code_variable\">result<\/span><span class=\"code_operator\">:<\/span><span class=\"code_variable\">result<\/span><span class=\"code_operator\">\u00b7<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">d<\/span><span class=\"code_operator\">\u2212<\/span><span class=\"code_number\">1<\/span><span class=\"code_operator\">)<\/span><span class=\"code_operator\">\/<\/span><span class=\"code_variable\">d<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <span class=\"code_function\">while <\/span><span class=\"code_function\">mod<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">p<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">d<\/span><span class=\"code_operator\">)<\/span><span class=\"code_operator\">=<\/span><span class=\"code_number\">0<\/span><span class=\"code_function\"> do <\/span><span class=\"code_operator\">(<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <span class=\"code_variable\">p<\/span><span class=\"code_operator\">:<\/span><span class=\"code_variable\">p<\/span><span class=\"code_operator\">\/<\/span><span class=\"code_variable\">d<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <span class=\"code_operator\">)<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <span class=\"code_operator\">)<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <span class=\"code_variable\">d<\/span><span class=\"code_operator\">:<\/span><span class=\"code_variable\">d<\/span><span class=\"code_operator\">+<\/span><span class=\"code_number\">1<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0 <span class=\"code_operator\">)<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0 <span class=\"code_function\">if <\/span><span class=\"code_variable\">p<\/span><span class=\"code_endofline\">&gt;<\/span><span class=\"code_number\">1<\/span><span class=\"code_function\"> then <\/span><span class=\"code_variable\">result<\/span><span class=\"code_operator\">:<\/span><span class=\"code_variable\">result<\/span><span class=\"code_operator\">\u00b7<\/span><span class=\"code_operator\">(<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">p<\/span><span class=\"code_operator\">\u2212<\/span><span class=\"code_number\">1<\/span><span class=\"code_operator\">)<\/span><span class=\"code_operator\">\/<\/span><span class=\"code_variable\">p<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0 <span class=\"code_function\">return<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">result<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\"><br \/><\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">$<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p><!-- Code cell --><\/p>\n<table>\n<tr style=\"border: 0px;\">\n<td style=\"width: 70px;vertical-align: top;padding: 1mm;\"><span class=\"prompt\">(%i2)\t<\/span><\/td>\n<td style=\"vertical-align: top;padding: 1mm;\"><span class=\"input\"><span class=\"code_function\">fiEuler<\/span><span class=\"code_operator\">(<\/span><span class=\"code_number\">87<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">;<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p>\\[56\\]<\/p>\n<\/div>\n<hr \/>\n<blockquote>\n<p><strong>Ejercicio:<\/strong> Resolver la ecuaci\u00f3n de congruencias \\(3X\\equiv 16 \\pmod{22}\\).<\/p>\n<\/blockquote>\n<p><script>\nfunction showHtmlDiv5w() {\n  var htmlShow5w = document.getElementById(\"html-show5w\");\n  if (htmlShow5w.style.display === \"none\") {\n    htmlShow5w.style.display = \"block\";\n  } else {\n    htmlShow5w.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv5w()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show5w\" style=\"display: none;\">\n<!-- Code cell --><\/p>\n<table>\n<tr style=\"border: 0px;\">\n<td style=\"width: 70px;vertical-align: top;padding: 1mm;\"><span class=\"prompt\">(%i1)<\/span><\/td>\n<td style=\"vertical-align: top;padding: 1mm;\"><span class=\"input\"><span class=\"code_function\">mcd<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">a<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">b<\/span><span class=\"code_operator\">)<\/span><span class=\"code_operator\">:<\/span><span class=\"code_operator\">=<\/span><span class=\"code_function\">block<\/span><span class=\"code_operator\">(<\/span><span class=\"code_operator\">[<\/span><span class=\"code_variable\">r<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">i<\/span><span class=\"code_operator\">]<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0 <span class=\"code_variable\">r<\/span><span class=\"code_operator\">:<\/span><span class=\"code_operator\">[<\/span><span class=\"code_function\">mod<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">a<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">b<\/span><span class=\"code_operator\">)<\/span><span class=\"code_operator\">]<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0 <span class=\"code_variable\">r<\/span><span class=\"code_operator\">:<\/span><span class=\"code_function\">append<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">r<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_function\">mod<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">b<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">r<\/span><span class=\"code_operator\">)<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0 <span class=\"code_variable\">id<\/span><span class=\"code_operator\">:<\/span><span class=\"code_number\">2<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0 <span class=\"code_function\">for <\/span><span class=\"code_variable\">i<\/span><span class=\"code_operator\">:<\/span><span class=\"code_number\">2<\/span><span class=\"code_function\"> while <\/span><span class=\"code_variable\">r<\/span><span class=\"code_operator\">[<\/span><span class=\"code_variable\">i<\/span><span class=\"code_operator\">]<\/span><span class=\"code_endofline\">&gt;<\/span><span class=\"code_number\">0<\/span><span class=\"code_function\"> do <\/span><span class=\"code_operator\">(<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <span class=\"code_variable\">r<\/span><span class=\"code_operator\">:<\/span><span class=\"code_function\">append<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">r<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_operator\">[<\/span><span class=\"code_function\">mod<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">r<\/span><span class=\"code_operator\">[<\/span><span class=\"code_variable\">i<\/span><span class=\"code_endofline\">\u2212<\/span><span class=\"code_number\">1<\/span><span class=\"code_operator\">]<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">r<\/span><span class=\"code_operator\">[<\/span><span class=\"code_variable\">i<\/span><span class=\"code_operator\">]<\/span><span class=\"code_operator\">)<\/span><span class=\"code_operator\">]<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0 <span class=\"code_operator\">)<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0 <span class=\"code_variable\">r<\/span><span class=\"code_operator\">[<\/span><span class=\"code_function\">length<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">r<\/span><span class=\"code_operator\">)<\/span><span class=\"code_operator\">\u2212<\/span><span class=\"code_number\">1<\/span><span class=\"code_operator\">]<\/span><span class=\"code_endofline\"><br \/><\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">$<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p><!-- Code cell --> <\/p>\n<table>\n<tr style=\"border: 0px;\">\n<td style=\"width: 70px;vertical-align: top;padding: 1mm;\"><span class=\"prompt\">(%i3)<\/span><\/td>\n<td style=\"vertical-align: top;padding: 1mm;\"><span class=\"input\"><span class=\"code_function\">fiEuler<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">n<\/span><span class=\"code_operator\">)<\/span><span class=\"code_operator\">:<\/span><span class=\"code_operator\">=<\/span><span class=\"code_function\">block<\/span><span class=\"code_operator\">(<\/span><span class=\"code_operator\">[<\/span><span class=\"code_variable\">f<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">i<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">m<\/span><span class=\"code_operator\">]<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0 <span class=\"code_variable\">f<\/span><span class=\"code_operator\">:<\/span><span class=\"code_number\">1<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0 <span class=\"code_function\">for <\/span><span class=\"code_variable\">i<\/span><span class=\"code_operator\">:<\/span><span class=\"code_number\">2<\/span><span class=\"code_function\"> thru <\/span><span class=\"code_variable\">n<\/span><span class=\"code_operator\">\u2212<\/span><span class=\"code_number\">1<\/span><span class=\"code_function\"> do <\/span><span class=\"code_operator\">(<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <span class=\"code_function\">if<\/span><span class=\"code_operator\">(<\/span><span class=\"code_function\">mcd<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">i<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">n<\/span><span class=\"code_operator\">)<\/span><span class=\"code_operator\">=<\/span><span class=\"code_number\">1<\/span><span class=\"code_operator\">)<\/span><span class=\"code_function\"> then <\/span><span class=\"code_variable\">f<\/span><span class=\"code_operator\">:<\/span><span class=\"code_variable\">f<\/span><span class=\"code_operator\">+<\/span><span class=\"code_number\">1<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0 <span class=\"code_operator\">)<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span>\u00a0 <span class=\"code_variable\">f<\/span><span class=\"code_endofline\"><br \/><\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">$<\/span><span class=\"code_endofline\"><br \/><\/span><span class=\"code_variable\">fi<\/span><span class=\"code_operator\">:<\/span><span class=\"code_function\">fiEuler<\/span><span class=\"code_operator\">(<\/span><span class=\"code_number\">22<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">;<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p>\\[\\operatorname{ }10\\]<\/p>\n<p><!-- Text cell --><\/p>\n<div class=\"comment\">Sabemos que \\(3^{10-1}\\pmod{22}\\) es el inverso de 3, luego<\/div>\n<p><!-- Code cell --><\/p>\n<table>\n<tr style=\"border: 0px;\">\n<td style=\"width: 70px;vertical-align: top;padding: 1mm;\"><span class=\"prompt\">(%i5)<\/span><\/td>\n<td style=\"vertical-align: top;padding: 1mm;\"><span class=\"input\"><span class=\"code_variable\">r<\/span><span class=\"code_operator\">:<\/span><span class=\"code_function\">mod<\/span><span class=\"code_operator\">(<\/span><span class=\"code_number\">3<\/span><span class=\"code_operator\">^<\/span><span class=\"code_number\">2<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">22<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">$<\/span><span class=\"code_endofline\"><br \/><\/span><span class=\"code_function\">makelist<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">r<\/span><span class=\"code_operator\">:<\/span><span class=\"code_function\">mod<\/span><span class=\"code_operator\">(<\/span><span class=\"code_number\">3<\/span><span class=\"code_operator\">\u00b7<\/span><span class=\"code_variable\">r<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">22<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">i<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">3<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">9<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">;<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p>\\[\\operatorname{ }\\left[ 5\\operatorname{,}15\\operatorname{,}1\\operatorname{,}3\\operatorname{,}9\\operatorname{,}5\\operatorname{,}15\\right] \\]<\/p>\n<p><!-- Text cell --><\/p>\n<div class=\"comment\">El inverso que buscamos es 15. El resultado ser\u00e1<\/div>\n<p><!-- Code cell --><\/p>\n<table>\n<tr style=\"border: 0px;\">\n<td style=\"width: 70px;vertical-align: top;padding: 1mm;\"><span class=\"prompt\">(%i6)<\/span><\/td>\n<td style=\"vertical-align: top;padding: 1mm;\"><span class=\"input\"><span class=\"code_function\">mod<\/span><span class=\"code_operator\">(<\/span><span class=\"code_number\">15<\/span><span class=\"code_operator\">\u00b7<\/span><span class=\"code_number\">16<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">22<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">;<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p>\\[\\operatorname{ }20\\]<\/p>\n<p><!-- Text cell --><\/p>\n<div class=\"comment\">Verifiqu\u00e9moslo<\/div>\n<p><!-- Code cell --><\/p>\n<table>\n<tr style=\"border: 0px;\">\n<td style=\"width: 70px;vertical-align: top;padding: 1mm;\">\n<span class=\"prompt\">(%i7)<\/span><\/td>\n<td style=\"vertical-align: top;padding: 1mm;\"><span class=\"input\"><span class=\"code_function\">mod<\/span><span class=\"code_operator\">(<\/span><span class=\"code_number\">3<\/span><span class=\"code_operator\">\u00b7<\/span><span class=\"code_number\">20<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">22<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">;<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p>\\[\\operatorname{ }16\\]<\/p>\n<\/div>\n<hr \/>\n<p>\u00bfQu\u00e9 ocurre si \\(\\mathbf{mcd}(a,n)=d\\) y \\(d|b\\)? En tal caso la soluci\u00f3n que buscamos depender\u00e1 de la soluci\u00f3n de<\/p>\n<p>\\[\\frac{a}{d}X_0 \\equiv \\frac{b}{d} \\left(\\mathbf{mod}\\ \\frac{n}{d}\\right)\\]<\/p>\n<p>En tal caso, las soluciones ser\u00e1 varias y vendr\u00e1s dadas por:<\/p>\n<p>\\[X\\equiv \\left[X_0+\\frac{n}{d}k\\right]\\pmod{n}, \\]<\/p>\n<p>donde \\(k\\in \\{0,1,2,\\ldots,d-1\\}\\).<\/p>\n<blockquote>\n<p><strong>Ejercicio:<\/strong> Resolver la ecuaci\u00f3n de congruencias \\(4X\\equiv 22 \\pmod{46}\\).<\/p>\n<\/blockquote>\n<p><script>\nfunction showHtmlDiv5b() {\n  var htmlShow5b = document.getElementById(\"html-show5b\");\n  if (htmlShow5b.style.display === \"none\") {\n    htmlShow5b.style.display = \"block\";\n  } else {\n    htmlShow5b.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv5b()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show5b\" style=\"display: none;\">\nPara resolver nuestro problemas seguimos los siguientes pasos:<\/p>\n<ul>\n<li>Determinamos: \\(\\mathbf{mcd}(a,n)=d\\)<\/li>\n<li>Si \\(d|22\\)<\/li>\n<ul>\n<li>Resolvemos: \\(\\frac{4}{d}X_0\\equiv \\frac{22}{d} \\left(\\mathbf{mod}{\\frac{46}{d}}\\right)\\)<\/li>\n<\/ul>\n<li>en caso contrario<\/li>\n<ul>\n<li>No hay soluci\u00f3n<\/li>\n<\/ul>\n<\/ul>\n<\/div>\n<hr \/>\n<blockquote>\n<p><strong>Ejercicio:<\/strong> Sea \\(0&lt;X&lt;161\\), la mayor de las soluciones de \\(28X\\equiv 35 {\\pmod {161}}\\). \u00bfCu\u00e1nto suman sus d\u00edgitos?<\/p>\n<\/blockquote>\n<p><script>\nfunction showHtmlDiv6b() {\n  var htmlShow6b = document.getElementById(\"html-show6b\");\n  if (htmlShow6b.style.display === \"none\") {\n    htmlShow6b.style.display = \"block\";\n  } else {\n    htmlShow6b.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv6b()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show6b\" style=\"display: none;\">\nSiguiendo el procedimiento, primero vemos que \\(\\mathbf{mcd}(28,161)=7\\), y como 7|35, la ecuaci\u00f3n tiene soluci\u00f3n y esta depende de \\[4X_0\\equiv 5 {\\pmod {23}}.\\] Resolvamos esta ecuaci\u00f3n. Como 23 es primo, resulta \\(\\varphi(23)=(23-1)=22\\), luego necesitamos \\[4^{21}\\equiv Y {\\pmod {23}}.\\]<\/p>\n<p>Calculemos los restos potenciales:<br \/>\n\\[\\begin{align*}<br \/>\n 4^0 &#038;\\equiv 1\\pmod{23} \\\\<br \/>\n 4^1 &#038;\\equiv 4\\pmod{23} \\\\<br \/>\n 4^2 &#038;\\equiv 16\\pmod{23} \\\\<br \/>\n 4^3 &#038;\\equiv 18\\pmod{23} \\\\<br \/>\n 4^5 &#038;\\equiv 12\\pmod{23} \\\\<br \/>\n 4^{10} &#038;\\equiv 6\\pmod{23} \\\\<br \/>\n 4^{20} &#038;\\equiv 13\\pmod{23} \\\\<br \/>\n 4^{21} &#038;\\equiv 6\\pmod{23}<br \/>\n\\end{align*}\\]<br \/>\nAhora solo falta aplicarlo:\\[4X_0\\equiv 5 {\\pmod {23}}\\Rightarrow X_0\\equiv 6\\cdot 5 {\\pmod {23}}\\Rightarrow X_0\\equiv 7 {\\pmod {23}}.\\]<br \/>\nLa soluci\u00f3n general ser\u00e1: \\[X\\equiv \\left[7+23k\\right]\\pmod{161},\\ k\\in\\{0,\\ldots,6\\}.\\]<br \/>\nLa soluciones menores de 161 ser\u00e1n:\\[7,30,53,76,99,122,145.\\] La mayor de las soluciones es 145, y la respuesta al ejercicio 1+4+5=10.\n<\/p><\/div>\n<hr \/>\n<h2>Criterio de divisibilidad<\/h2>\n<p>La utilizaci\u00f3n de los restos potenciales nos sirve para establecer un criterio de divisibilidad que permite saber las propiedades de un n\u00famero para que sea divisible por otro:<\/p>\n<blockquote>\n<p>Sea dados \\(m,n\\in\\mathbb{Z}^+\\) para todo entero \\[a=a_kn^k+a_{k-1}n^{k-1}+&#8230;+a_1n+a_0\\] si \\(n^i\\equiv r_i{\\pmod {m}}\\) entonces \\[a\\equiv a_kr_k+&#8230;+a_0r_0{\\pmod {m}}\\]<\/p>\n<\/blockquote>\n<p>Esto nos permite justificar, por ejemplo, que un n\u00famero es divisible por 3 si la suma de sus d\u00edgitos es divisible por 3.<\/p>\n<blockquote>\n<p><strong>Ejemplo:<\/strong> Crear una criterio de divisibilidad para el 4.<\/p>\n<\/blockquote>\n<p><script>\nfunction showHtmlDiv2a5() {\n  var htmlShow2a5 = document.getElementById(\"html-show2a5\");\n  if (htmlShow2a5.style.display === \"none\") {\n    htmlShow2a5.style.display = \"block\";\n  } else {\n    htmlShow2a5.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv2a5()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show2a5\" style=\"display: none;\">\nPrimero calculamos los restos potenciales de 10 m\u00f3dulo 4:<br \/>\n\\[\\begin{align*}  10^{0}&#038;\\equiv 1 {\\pmod {4}} \\\\  10^{1}&#038;\\equiv 2 {\\pmod {4}}\\\\   10^{2}&#038;\\equiv 0 {\\pmod {4}}\\end{align*}\\] Luego si \\(N=\\sum_{i=0}^kd_i10^i\\) resultar\u00e1 \\[N\\equiv (2d_1+d_0) {\\pmod {4}}.\\] Es decir, <em>un n\u00famero es divisible por 4 si lo es la suma de su \u00faltima cifra m\u00e1s el doble de la pen\u00faltima<\/em>.\n<\/div>\n<hr \/>\n<blockquote>\n<p><strong>Ejemplo:<\/strong> \u00bfCu\u00e1l es el resto de la divisi\u00f3n de 10655871899 entre 6?<\/p>\n<\/blockquote>\n<p><script>\nfunction showHtmlDiv2a5w() {\n  var htmlShow2a5w = document.getElementById(\"html-show2a5w\");\n  if (htmlShow2a5w.style.display === \"none\") {\n    htmlShow2a5w.style.display = \"block\";\n  } else {\n    htmlShow2a5w.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv2a5w()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show2a5w\" style=\"display: none;\">\n<!-- Text cell --><\/p>\n<div class=\"comment\">Primero calculamos los restos potenciales<\/div>\n<p><!-- Code cell --><\/p>\n<table>\n<tr style=\"border: 0px;\">\n<td style=\"width: 70px;vertical-align: top;padding: 1mm;\"><span class=\"prompt\">(%i1)<\/span><\/td>\n<td style=\"vertical-align: top;padding: 1mm;\"><span class=\"input\"><span class=\"code_function\">makelist<\/span><span class=\"code_operator\">(<\/span><span class=\"code_function\">mod<\/span><span class=\"code_operator\">(<\/span><span class=\"code_number\">10<\/span><span class=\"code_operator\">^<\/span><span class=\"code_variable\">i<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">6<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">i<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">0<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">5<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">;<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p>\\[\\left[ 1,4,4,4,4,4\\right] \\]<\/p>\n<p><!-- Text cell --><\/p>\n<div class=\"comment\">Como vemos, a partir del segundo d\u00edgito se repiten. Luego \\[4\\left ( \\sum_{i=1}^k d_i \\right )+d_0\\equiv n(\\textbf{mod}\\,6)\\Leftrightarrow 4\\left ( \\sum_{i=0}^k d_i \\right )-3d_0\\equiv n(\\textbf{mod}\\,6)\\]<\/div>\n<p><!-- Code cell --><\/p>\n<table>\n<tr style=\"border: 0px;\">\n<td style=\"width: 70px;vertical-align: top;padding: 1mm;\"><span class=\"prompt\">(%i3)<\/span><\/td>\n<td style=\"vertical-align: top;padding: 1mm;\"><span class=\"input\"><span class=\"code_variable\">d<\/span><span class=\"code_operator\">:<\/span><span class=\"code_operator\">[<\/span><span class=\"code_number\">1<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">0<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">6<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">5<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">5<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">8<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">7<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">1<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">8<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">9<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">9<\/span><span class=\"code_operator\">]<\/span><span class=\"code_endofline\">$<\/span><span class=\"code_endofline\"><br \/><\/span><span class=\"code_number\">4<\/span><span class=\"code_operator\">\u00b7<\/span><span class=\"code_function\">sum<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">d<\/span><span class=\"code_operator\">[<\/span><span class=\"code_variable\">i<\/span><span class=\"code_operator\">]<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">i<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">1<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_function\">length<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">d<\/span><span class=\"code_operator\">)<\/span><span class=\"code_operator\">)<\/span><span class=\"code_operator\">\u2212<\/span><span class=\"code_number\">3<\/span><span class=\"code_operator\">\u00b7<\/span><span class=\"code_variable\">d<\/span><span class=\"code_operator\">[<\/span><span class=\"code_function\">length<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">d<\/span><span class=\"code_operator\">)<\/span><span class=\"code_operator\">]<\/span><span class=\"code_endofline\">;<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p>\\[209\\]<\/p>\n<p><!-- Text cell --><\/p>\n<div class=\"comment\">Reduzcamos este n\u00famero<\/div>\n<p><!-- Code cell --><\/p>\n<table>\n<tr style=\"border: 0px;\">\n<td style=\"width: 70px;vertical-align: top;padding: 1mm;\"><span class=\"prompt\">(%i4)<\/span><\/td>\n<td style=\"vertical-align: top;padding: 1mm;\"><span class=\"input\"><span class=\"code_function\">mod<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">%<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">6<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">;<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p>\\[5\\]<\/p>\n<\/div>\n<hr \/>\n<blockquote>\n<p><strong>Ejemplo:<\/strong> Crear una criterio de divisibilidad para el 7 y determinar \\[12345678910987654321\\equiv X {\\pmod {7}}\\]<\/p>\n<\/blockquote>\n<p><script>\nfunction showHtmlDiv2a3() {\n  var htmlShow2a3 = document.getElementById(\"html-show2a3\");\n  if (htmlShow2a3.style.display === \"none\") {\n    htmlShow2a3.style.display = \"block\";\n  } else {\n    htmlShow2a3.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv2a3()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show2a3\" style=\"display: none;\">\nPara este ejercicio crearemos dos funciones previamente: <strong>restos<\/strong>(\\(n,m\\)), nos proporciona los restos potenciales de \\(n\\) m\u00f3dulo \\(m\\). <strong>digitos<\/strong>(\\(n\\)), nos devuelve un vector con los d\u00edgitos del n\u00famero \\(n\\).<\/p>\n<p>Ahora, veamos los restos de 10 m\u00f3dulo 7:<br \/>\n<!-- Code cell --><\/p>\n<table>\n<tr style=\"border: 0px;\">\n<td style=\"width: 70px;vertical-align: top;padding: 1mm;\"><span class=\"prompt\">(%i3)<\/span><\/td>\n<td style=\"vertical-align: top;padding: 1mm;\"> <span class=\"input\"><span class=\"code_variable\">r10<\/span><span class=\"code_operator\">:<\/span><span class=\"code_function\">restos<\/span>(<span class=\"code_number\">10<\/span>,<span class=\"code_number\">7<\/span>)<span class=\"code_endofline\">;<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p><math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"block\"><mtable><mlabeledtr columnalign=\"left\"><mtd><mtext>(r10)<\/mtext><\/mtd><mtd><mo>[<\/mo><mo>[<\/mo><mn>1<\/mn><mo>,<\/mo><mn>3<\/mn><mo>,<\/mo><mn>2<\/mn><mo>,<\/mo><mn>6<\/mn><mo>,<\/mo><mn>4<\/mn><mo>,<\/mo><mn>5<\/mn><mo>]<\/mo><mo>,<\/mo><mo>[<\/mo><mn>1<\/mn><mo>,<\/mo><mn>1<\/mn><mo>]<\/mo><mo>,<\/mo><mo>[<\/mo><mn>6<\/mn><mo>]<\/mo><mo>]<\/mo><\/mtd><\/mlabeledtr><\/mtable><\/math><\/p>\n<p><!-- Text cell --><\/p>\n<div class=\"comment\">\n<p>Luego, tenemos un ciclo de longitud 6 desde 0. Apliquemos el teorema:<\/p>\n<\/div>\n<p><!-- Code cell --><\/p>\n<table>\n<tr style=\"border: 0px;\">\n<td style=\"width: 70px;vertical-align: top;padding: 1mm;\"><span class=\"prompt\">(%i7)<\/span><\/td>\n<td style=\"vertical-align: top;padding: 1mm;\"> <span class=\"input\"><span class=\"code_variable\">d<\/span><span class=\"code_operator\">:<\/span><span class=\"code_function\">digitos<\/span>(<span class=\"code_number\">12345678910987654321<\/span>)<span class=\"code_endofline\">$<\/span><br \/><span class=\"code_variable\">r<\/span><span class=\"code_operator\">:<\/span><span class=\"code_number\">0<\/span><span class=\"code_endofline\">$<\/span><br \/>for <span class=\"code_variable\">i<\/span><span class=\"code_operator\">:<\/span><span class=\"code_number\">1<\/span> thru <span class=\"code_function\">length<\/span>(<span class=\"code_variable\">d<\/span>) do(<br \/> \u00a0\u00a0 <span class=\"code_variable\">a<\/span><span class=\"code_operator\">:<\/span><span class=\"code_variable\">d<\/span>[<span class=\"code_variable\">i<\/span>],<br \/> \u00a0\u00a0 <span class=\"code_variable\">b<\/span><span class=\"code_operator\">:<\/span><span class=\"code_variable\">r10<\/span>[<span class=\"code_number\">1<\/span>][<span class=\"code_function\">mod<\/span>(<span class=\"code_variable\">i<\/span><span class=\"code_operator\">&#8211;<\/span><span class=\"code_number\">1<\/span>,<span class=\"code_function\">length<\/span>(<span class=\"code_variable\">r10<\/span>[<span class=\"code_number\">1<\/span>]))<span class=\"code_operator\">+<\/span><span class=\"code_number\">1<\/span>],<br \/> \u00a0\u00a0 <span class=\"code_variable\">r<\/span><span class=\"code_operator\">:<\/span><span class=\"code_variable\">r<\/span><span class=\"code_operator\">+<\/span><span class=\"code_variable\">a<\/span><span class=\"code_operator\">*<\/span><span class=\"code_variable\">b<\/span><br \/>)<span class=\"code_endofline\">$<\/span><br \/><span class=\"code_function\">print<\/span>(<span class=\"code_string\">\u00abResultado:\u00bb<\/span>, <span class=\"code_function\">mod<\/span>(<span class=\"code_variable\">r<\/span>,<span class=\"code_number\">7<\/span>))<span class=\"code_endofline\">$<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p><math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"block\"><mtable><mlabeledtr columnalign=\"left\"><mtd><mtext\/><\/mtd><mtd><mo>Resultado:<\/mo><mo\/><mn>5<\/mn><mo\/><\/mtd><\/mlabeledtr><\/mtable><\/math>\n<\/div>\n<hr \/>\n<blockquote>\n<p><strong>Ejemplo:<\/strong> Cu\u00e1ntos n\u00fameros, \\(0\\leq N&lt;100\\), verifican \\[123456789N987654321\\equiv 5 {\\pmod {7}}\\]<\/p>\n<\/blockquote>\n<p><script>\nfunction showHtmlDiv2a1() {\n  var htmlShow2a1 = document.getElementById(\"html-show2a1\");\n  if (htmlShow2a1.style.display === \"none\") {\n    htmlShow2a1.style.display = \"block\";\n  } else {\n    htmlShow2a1.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv2a1()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show2a1\" style=\"display: none;\">\n<strong>Soluci\u00f3n<\/strong>: 15\n<\/div>\n<hr \/>\n<table id=\"yzpi\" border=\"0\" width=\"100%\" cellspacing=\"0\" cellpadding=\"3\" bgcolor=\"#999999\">\n<tbody>\n<tr>\n<td width=\"100%\"><strong>Ejercicio:<\/strong> Sea \\(v\\) la <strong>soluci\u00f3n de Bezout<\/strong> de \\(\\mathbf{mcd}(5432,872)\\). \u00bfCu\u00e1l es el valor de \\([3,-5].v\/\\|v\\|\\) ?<\/p>\n<div id=\"menu-a\">\n<ul>\n<li>8.45<\/li>\n<li>7.12<\/li>\n<li>5.41<\/li>\n<\/ul>\n<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p><script>\nfunction showHtmlDiv() {\n  var htmlShow = document.getElementById(\"html-show\");\n  if (htmlShow.style.display === \"none\") {\n    htmlShow.style.display = \"block\";\n  } else {\n    htmlShow.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show\" style=\"display: none;\">\n<p id=\"htmlContent\" class=\"text-html\"><strong>C.)<\/strong><\/p>\n<p>Calculemos los restos y los cocientes que utilizaremos posteriormente.<\/p>\n<p><!-- Code cell --><\/p>\n<table>\n<tr style=\"border: 0px;\">\n<td style=\"width: 70px;vertical-align: top;padding: 1mm;\"><span class=\"prompt\">(%i9) <\/span><\/td>\n<td style=\"vertical-align: top;padding: 1mm;\"><span class=\"input\"><span class=\"code_variable\">n<\/span><span class=\"code_operator\">:<\/span><span class=\"code_number\">5432<\/span><span class=\"code_endofline\">$<\/span><span class=\"code_endofline\"><br \/><\/span><span class=\"code_variable\">m<\/span><span class=\"code_operator\">:<\/span><span class=\"code_number\">872<\/span><span class=\"code_endofline\">$<\/span><span class=\"code_endofline\"><br \/><\/span><span class=\"code_variable\">q<\/span><span class=\"code_operator\">:<\/span><span class=\"code_operator\">[<\/span><span class=\"code_function\">floor<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">n<\/span><span class=\"code_operator\">\/<\/span><span class=\"code_variable\">m<\/span><span class=\"code_operator\">)<\/span><span class=\"code_operator\">]<\/span><span class=\"code_endofline\">$<\/span><span class=\"code_endofline\"><br \/><\/span><span class=\"code_variable\">r<\/span><span class=\"code_operator\">:<\/span><span class=\"code_operator\">[<\/span><span class=\"code_function\">mod<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">n<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">m<\/span><span class=\"code_operator\">)<\/span><span class=\"code_operator\">]<\/span><span class=\"code_endofline\">$<\/span><span class=\"code_endofline\"><br \/><\/span><span class=\"code_variable\">q<\/span><span class=\"code_operator\">:<\/span><span class=\"code_function\">append<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">q<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_operator\">[<\/span><span class=\"code_function\">floor<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">m<\/span><span class=\"code_operator\">\/<\/span><span class=\"code_variable\">r<\/span><span class=\"code_operator\">[<\/span><span class=\"code_number\">1<\/span><span class=\"code_operator\">]<\/span><span class=\"code_operator\">)<\/span><span class=\"code_operator\">]<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">$<\/span><span class=\"code_endofline\"><br \/><\/span><span class=\"code_variable\">r<\/span><span class=\"code_operator\">:<\/span><span class=\"code_function\">append<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">r<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_operator\">[<\/span><span class=\"code_function\">mod<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">m<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">r<\/span><span class=\"code_operator\">[<\/span><span class=\"code_number\">1<\/span><span class=\"code_operator\">]<\/span><span class=\"code_operator\">)<\/span><span class=\"code_operator\">]<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">$<\/span><span class=\"code_endofline\"><br \/><\/span><span class=\"code_function\">for <\/span><span class=\"code_variable\">i<\/span><span class=\"code_operator\">:<\/span><span class=\"code_number\">2 <\/span><span class=\"code_function\">while <\/span><span class=\"code_variable\">r<\/span><span class=\"code_operator\">[<\/span><span class=\"code_variable\">i<\/span><span class=\"code_operator\">]<\/span><span class=\"code_endofline\">&gt;<\/span><span class=\"code_number\">0 <\/span><span class=\"code_function\">do<\/span><span class=\"code_operator\">(<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0 <span class=\"code_variable\">q<\/span><span class=\"code_operator\">:<\/span><span class=\"code_function\">append<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">q<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_operator\">[<\/span><span class=\"code_function\">floor<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">r<\/span><span class=\"code_operator\">[<\/span><span class=\"code_variable\">i<\/span><span class=\"code_operator\">\u2212<\/span><span class=\"code_number\">1<\/span><span class=\"code_operator\">]<\/span><span class=\"code_operator\">\/<\/span><span class=\"code_variable\">r<\/span><span class=\"code_operator\">[<\/span><span class=\"code_variable\">i<\/span><span class=\"code_operator\">]<\/span><span class=\"code_operator\">)<\/span><span class=\"code_operator\">]<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0 <span class=\"code_variable\">r<\/span><span class=\"code_operator\">:<\/span><span class=\"code_function\">append<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">r<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_operator\">[<\/span><span class=\"code_function\">mod<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">r<\/span><span class=\"code_operator\">[<\/span><span class=\"code_variable\">i<\/span><span class=\"code_operator\">\u2212<\/span><span class=\"code_number\">1<\/span><span class=\"code_operator\">]<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">r<\/span><span class=\"code_operator\">[<\/span><span class=\"code_variable\">i<\/span><span class=\"code_operator\">]<\/span><span class=\"code_operator\">)<\/span><span class=\"code_operator\">]<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\"><br \/><\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">$<\/span><span class=\"code_endofline\"><br \/><\/span><span class=\"code_variable\">q<\/span><span class=\"code_endofline\">;<\/span><span class=\"code_endofline\"><br \/><\/span><span class=\"code_variable\">r<\/span><span class=\"code_endofline\">;<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p>\\[\\left[ 6, 4, 2, 1, 3, 2\\right] \\]<\/p>\n<p>\\[\\left[ 200, 72, 56, 16, 8, 0\\right] \\]<\/p>\n<p>Declaremos la funci\u00f3n que nos permita aplicar el algoritmo extendido de Euclides para encontrar la soluci\u00f3n que buscamos.<\/p>\n<p><!-- Code cell --><\/p>\n<table>\n<tr style=\"border: 0px;\">\n<td style=\"width: 70px;vertical-align: top;padding: 1mm;\"><span class=\"prompt\">(%i10)<\/span><\/td>\n<td style=\"vertical-align: top;padding: 1mm;\"><span class=\"input\"><span class=\"code_function\">qm<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">a<\/span><span class=\"code_operator\">)<\/span><span class=\"code_operator\">:<\/span><span class=\"code_operator\">=<\/span><span class=\"code_function\">matrix<\/span><span class=\"code_operator\">(<\/span><span class=\"code_operator\">[<\/span><span class=\"code_number\">0<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">1<\/span><span class=\"code_operator\">]<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_operator\">[<\/span><span class=\"code_number\">1<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_operator\">\u2212<\/span><span class=\"code_variable\">a<\/span><span class=\"code_operator\">]<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">$<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p>Apliquemos el algoritmo extendido de Euclides multiplicando las matrices generadas con los cocientes.<\/p>\n<p><!-- Code cell --><\/p>\n<table>\n<tr style=\"border: 0px;\">\n<td style=\"width: 70px;vertical-align: top;padding: 1mm;\"><span class=\"prompt\">(%i12)<\/span><\/td>\n<td style=\"vertical-align: top;padding: 1mm;\"><span class=\"input\"><span class=\"code_variable\">M<\/span><span class=\"code_operator\">:<\/span><span class=\"code_function\">ident<\/span><span class=\"code_operator\">(<\/span><span class=\"code_number\">2<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">$<\/span><span class=\"code_endofline\"><br \/><\/span><span class=\"code_variable\">ml<\/span><span class=\"code_operator\">:<\/span><span class=\"code_function\">makelist<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">M<\/span><span class=\"code_operator\">:<\/span><span class=\"code_variable\">M<\/span><span class=\"code_endofline\">.<\/span><span class=\"code_function\">qm<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">q<\/span><span class=\"code_operator\">[<\/span><span class=\"code_variable\">i<\/span><span class=\"code_operator\">]<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">i<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">1<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_function\">length<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">q<\/span><span class=\"code_operator\">)<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">;<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p>\\[\\left[ \\begin{bmatrix}0 &amp; 1\\\\1 &amp; -6\\end{bmatrix}, \\begin{bmatrix}1 &amp; -4\\\\-6 &amp; 25\\end{bmatrix}, \\begin{bmatrix}-4 &amp; 9\\\\25 &amp; -56\\end{bmatrix}, \\begin{bmatrix}9 &amp; -13\\\\-56 &amp; 81\\end{bmatrix}, \\begin{bmatrix}-13 &amp; 48\\\\81 &amp; -299\\end{bmatrix}, \\begin{bmatrix}48 &amp; -109\\\\-299 &amp; 679\\end{bmatrix}\\right] \\]<\/p>\n<p>Tenemos la soluci\u00f3n, la primera columna de la \u00faltima matriz. Resolvamos el ejercicio.<\/p>\n<p><!-- Code cell --><\/p>\n<table>\n<tr style=\"border: 0px;\">\n<td style=\"width: 70px;vertical-align: top;padding: 1mm;\"><span class=\"prompt\">(%i14)<\/span><\/td>\n<td style=\"vertical-align: top;padding: 1mm;\"><span class=\"input\"><span class=\"code_variable\">v<\/span><span class=\"code_operator\">:<\/span><span class=\"code_function\">transpose<\/span><span class=\"code_operator\">(<\/span><span class=\"code_function\">col<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">ml<\/span><span class=\"code_operator\">[<\/span><span class=\"code_function\">length<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">q<\/span><span class=\"code_operator\">)<\/span><span class=\"code_operator\">]<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">1<\/span><span class=\"code_operator\">)<\/span><span class=\"code_operator\">)<\/span><span class=\"code_operator\">[<\/span><span class=\"code_number\">1<\/span><span class=\"code_operator\">]<\/span><span class=\"code_endofline\">$<\/span><span class=\"code_endofline\"><br \/><\/span><span class=\"code_operator\">[<\/span><span class=\"code_number\">3<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_operator\">\u2212<\/span><span class=\"code_number\">5<\/span><span class=\"code_operator\">]<\/span><span class=\"code_endofline\">.<\/span><span class=\"code_variable\">v<\/span><span class=\"code_operator\">\/<\/span><span class=\"code_function\">sqrt<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">v<\/span><span class=\"code_endofline\">.<\/span><span class=\"code_variable\">v<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">numer<\/span><span class=\"code_endofline\">;<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p>\\[5.412307287160986\\]<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Restos potenciales Veamos el siguiente ejercicio: Ejemplo: Dado \\(n=71\\cdots 71\\), donde la pareja 71 se repite 10 veces, \u00bfcu\u00e1l es su resto al dividirlo por 17? Soluci\u00f3n: El n\u00famero en cuesti\u00f3n es&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8],"tags":[9],"class_list":["post-849","post","type-post","status-publish","format-standard","hentry","category-matematica-discreta","tag-practicas-mad"],"_links":{"self":[{"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=\/wp\/v2\/posts\/849","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=849"}],"version-history":[{"count":15,"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=\/wp\/v2\/posts\/849\/revisions"}],"predecessor-version":[{"id":878,"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=\/wp\/v2\/posts\/849\/revisions\/878"}],"wp:attachment":[{"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=849"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=849"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=849"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}