{"id":755,"date":"2026-02-16T10:20:17","date_gmt":"2026-02-16T09:20:17","guid":{"rendered":"https:\/\/clases.jesussoto.es\/?p=755"},"modified":"2026-03-17T06:40:39","modified_gmt":"2026-03-17T05:40:39","slug":"mad-maximo-comun-divisor","status":"publish","type":"post","link":"https:\/\/clases.jesussoto.es\/?p=755","title":{"rendered":"MAD: M\u00e1ximo com\u00fan divisor y Ecuaci\u00f3n diof\u00e1ntica de 2 variables"},"content":{"rendered":"<h2><b>M\u00e1ximo com\u00fan divisor<\/b><\/h2>\n<p>Consideremos dos n\u00fameros enteros Si \\(a\\) y \\(b\\) distintos de cero, decimos que \\(c\\) es un divisor com\u00fan de \\(a\\) y \\(b\\) si \\(c|a\\) y \\(c|b\\). Cuando existen, \u00fanicamente, como divisores comunes 1 y -1 de los n\u00fameros \\(a\\) y \\(b\\), estos se llaman <strong>coprimos <\/strong> o <strong>n\u00fameros primos entre s\u00ed<\/strong>.<\/p>\n<p>Un n\u00famero entero \\(d\\) se llama <b>m\u00e1ximo com\u00fan divisor<\/b> de los n\u00fameros \\(a\\) y \\(b\\), \\(d=\\textbf{mcd}(a,b)\\), cuando:<\/p>\n<ol>\n<li><i>d<\/i> es divisor com\u00fan de los n\u00fameros \\(a\\) y \\(b\\) y<\/li>\n<li>\\(c\\) es divisor de \\(a\\) y \\(b\\), entonces \\(c|d\\).<\/li>\n<\/ol>\n<h3><b>Algoritmo de Euclides<\/b><\/h3>\n<p>El algoritmo de Euclides es un m\u00e9todo antiguo y eficiente para calcular el m\u00e1ximo com\u00fan divisor (mcd). Se basa en el siguiente resultado:<\/p>\n<blockquote>\n<p><strong>Teorema<\/strong>:<br \/>\nSi \\(a\\) y \\(b\\) son n\u00fameros enteros, \\[\\textbf{mcd}(a,b)=\\textbf{mcd}(b,r),\\] donde \\(r\\) es el resto del algoritmo de la divisi\u00f3n para \\(a\\) y \\(b\\) (\\(a=qb+r\\)).<\/p>\n<\/blockquote>\n<p>Utilizando este resultado calculamos el <b>mcd(a,b)<\/b> de dos enteros (ambos <u>&gt;<\/u>0, suponemos a <u>&gt;<\/u> b) definiendo q<sub>i<\/sub> y r<sub>i<\/sub> recursivamente mediante las ecuaciones:<\/p>\n<blockquote>\n<p>a = bq<sub>1<\/sub> + r<sub>1<\/sub>  (0<u>&lt;<\/u>r<sub>1<\/sub>&lt;b)<\/p>\n<p>b = r<sub>1<\/sub>q<sub>2<\/sub> + r<sub>2<\/sub>  (0<u>&lt;<\/u>r<sub>2<\/sub>&lt;r<sub>1<\/sub>)<\/p>\n<p>r<sub>1<\/sub> = r<sub>2<\/sub>q<sub>3<\/sub> + r<sub>3<\/sub>  (0<u>&lt;<\/u>r<sub>3<\/sub>&lt;r<sub>2<\/sub>)<\/p>\n<p>\u2026.<\/p>\n<p>r<sub>k-3<\/sub> = r<sub>k-2<\/sub>q<sub>k-1<\/sub> + r<sub>k-1<\/sub>  (0<u>&lt;<\/u>r<sub>k-1<\/sub>&lt;r<sub>k-2<\/sub>)<\/p>\n<p>r<sub>k-2<\/sub> = r<sub>k-1<\/sub>q<sub>k<\/sub>  (r<sub>k<\/sub>=0)<\/p>\n<\/blockquote>\n<p>Del teorema anterior, se sigue que:<\/p>\n<p>\\[\\textbf{mcd}(a,b)=\\textbf{mcd}(b,r_1)=\\textbf{mcd}(r_1,r_2)=\\ldots=\\textbf{mcd}(r_{k-2},r_{k-1})=r_{k-1}\\]<\/p>\n<p>En general, es que el n\u00famero de pasos necesarios para calcular el <strong>mcd <\/strong> de dos n\u00fameros es menor que 5 veces el n\u00famero de d\u00edgitos del menor de ellos.<\/p>\n<blockquote>\n<p><strong>Ejemplo:<\/strong> Calcular \\(\\textbf{mcd}(866775, 138705)\\) <\/p>\n<\/blockquote>\n<p><script>\nfunction showHtmlDiv23b() {\n  var htmlShow23b = document.getElementById(\"html-show23b\");\n  if (htmlShow23b.style.display === \"none\") {\n    htmlShow23b.style.display = \"block\";\n  } else {\n    htmlShow23b.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv23b()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show23b\" style=\"display: none;\">\n\\[\\begin{align*}<br \/>\n866775&#038;=(6)138705+34545\\\\<br \/>\n138705&#038;=(4)34545+525\\\\<br \/>\n34545&#038;=(4)525+420\\\\<br \/>\n525&#038;=(1)420+105\\\\<br \/>\n420&#038;=(4)105+0<br \/>\n\\end{align*}\\]<br \/>\nConsecuentemente, el m\u00e1ximo com\u00fan divisor es 105.\n<\/div>\n<hr \/>\n<blockquote>\n<p><strong>Ejemplo:<\/strong> Calcular \\(\\textbf{mcd}(125846,56985214)\\) <\/p>\n<\/blockquote>\n<p><script>\nfunction showHtmlDiv23a() {\n  var htmlShow23a = document.getElementById(\"html-show23a\");\n  if (htmlShow23a.style.display === \"none\") {\n    htmlShow23a.style.display = \"block\";\n  } else {\n    htmlShow23a.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv23a()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show23a\" style=\"display: none;\">\n\\[\\begin{align*}<br \/>\n56985214&#038;=(452)125846+102822\\\\<br \/>\n125846&#038;=(1)102822+23024\\\\<br \/>\n102822&#038;=(4)23024+10726\\\\<br \/>\n23024&#038;=(2)10726+1572\\\\<br \/>\n10726&#038;=(6)1572+1294\\\\<br \/>\n1572&#038;=(1)1294+278\\\\<br \/>\n1294&#038;=(4)278+182\\\\<br \/>\n278&#038;=(1)182+96\\\\<br \/>\n182&#038;=(1)96+86\\\\<br \/>\n96&#038;=(1)86+10\\\\<br \/>\n86&#038;=(8)10+6\\\\<br \/>\n10&#038;=(1)6+4\\\\<br \/>\n6&#038;=(1)4+2\\\\<br \/>\n4&#038;=(2)2+0<br \/>\n\\end{align*}\\]<br \/>\nConsecuentemente, el m\u00e1ximo com\u00fan divisor es 2.\n<\/div>\n<hr \/>\n<h3>MCD con la calculadora<\/h3>\n<p><iframe loading=\"lazy\" title=\"\u00bfC\u00f3mo calcular el m\u00e1ximo com\u00fan divisor de 3 n\u00fameros con tu calculadora ClassWiz?   #matem\u00e1ticas\" width=\"540\" height=\"960\" src=\"https:\/\/www.youtube.com\/embed\/Pw9i5Y59ln4?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<hr \/>\n<h3><b>Teorema de B\u00e9zout<\/b><\/h3>\n<blockquote>\n<p><strong>Teorema<\/strong>: Si \\(d=mcd(a,b)\\), entonces<br \/>\n\\[\\exists x,y\\in\\mathbb{Z};\\, ax+by=d.\\]<\/p>\n<\/blockquote>\n<blockquote>\n<p><strong>Teorema de Euclides<\/strong>: Para todo \\(a,b,c\\in\\mathbb{Z}\\) si \\(a|(bc)\\) y \\(mcd(a,b)=1\\), entonces \\(a|c\\)<\/p>\n<\/blockquote>\n<p><script>\nfunction showHtmlDiv2g56() {\n  var htmlShow2g56 = document.getElementById(\"html-show2g56\");\n  if (htmlShow2g56.style.display === \"none\") {\n    htmlShow2g56.style.display = \"block\";\n  } else {\n    htmlShow2g56.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv2g56()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show2g56\" style=\"display: none;\">\nSi \\(a|(bc)\\), entonces \\(\\exists n\\in\\mathbb{Z}\\) tal que \\(bc=an\\). Adem\u00e1s, si \\(mcd(a,b)=1\\), el resultado anterior nos dice que \\(\\exists x,y\\in\\mathbb{Z};\\, ax+by=1\\). Si multiplicamos la \u00faltima igualdad por \\(c\\) tendremos:<br \/>\n\\[<br \/>\n\\begin{align*}<br \/>\nc&#038;=axc+byc \\\\<br \/>\n  &#038;=axc+(bc)y \\\\<br \/>\n  &#038;=axc+(an)y \\\\<br \/>\n  &#038;=a(xc+ny) \\\\<br \/>\n\\end{align*}<br \/>\n\\]<br \/>\nConsecuentemente, \\(a|c\\).\n<\/div>\n<hr \/>\n<blockquote>\n<p><strong>Teorema(Bezout)<\/strong>: Si \\(x_0,y_0\\in\\mathbb{Z}\\) son tales que \\(nx_0+my_0=\\mathbf{mcd}(n,m)\\), se cumple que\\[n\\left(x_0-\\frac{m}{\\mathbf{mcd}(n,m)}k\\right)+m\\left(y_0+\\frac{n}{\\mathbf{mcd}(n,m)}k\\right)=\\mathbf{mcd}(n,m)\\, \\forall k\\in\\mathbb{Z}\\]<\/p>\n<\/blockquote>\n<p>Por comodidad, a todas las posibles soluciones \\((x,y)\\in\\mathbb{Z}^2\\), tales que \\(nx+my=\\mathbf{mcd}(n,m)\\), les llamaremos soluciones de Bezout de \\(\\mathbf{mcd}(n,m)\\).<\/p>\n<p>El calculo de una de las soluciones anteriores ser\u00e1 un problema recurrente, aqu\u00ed propondremos dos procedimientos para obtenerla, ambas se basan el los n\u00fameros obtenidos en el desarrollo del algoritmo de Euclides:<\/p>\n<h3>Con un proceso recursivo <\/h3>\n<p style=\"text-align:center\"><iframe loading=\"lazy\" width=\"560\" height=\"315\" src=\"https:\/\/www.youtube.com\/embed\/2i5FberlJwg\" title=\"YouTube video player\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" allowfullscreen><\/iframe><\/p>\n<blockquote>\n<p><strong>Ejemplo: <\/strong> Sea v=[a,b], la  <strong>soluci\u00f3n de Bezout<\/strong> de \\(\\mathbf{mcd}(54180,47355)\\). \u00bfCu\u00e1nto es, en valor absoluto, el producto escalar [3,2].v\/||v||? <\/p>\n<\/blockquote>\n<p><script>\nfunction showHtmlDiv2g() {\n  var htmlShow2g = document.getElementById(\"html-show2g\");\n  if (htmlShow2g.style.display === \"none\") {\n    htmlShow2g.style.display = \"block\";\n  } else {\n    htmlShow2g.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv2g()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show2g\" style=\"display: none;\">\n<table border=\"0\" cellspacing=\"0\" cellpadding=\"0\" class=\"ta1\">\n<colgroup>\n<col width=\"99\"\/>\n<col width=\"99\"\/>\n<col width=\"99\"\/>\n<col width=\"99\"\/>\n<col width=\"99\"\/>\n<col width=\"99\"\/>\n<\/colgroup>\n<tr class=\"ro1\">\n<td class=\"ce1\">\n<p>cociente<\/p>\n<\/td>\n<td class=\"ce3\">\n<p>1<\/p>\n<\/td>\n<td class=\"ce3\">\n<p>6<\/p>\n<\/td>\n<td class=\"ce3\">\n<p>1<\/p>\n<\/td>\n<td class=\"ce3\">\n<p>15<\/p>\n<\/td>\n<td class=\"ce3\">\n<p>4<\/p>\n<\/td>\n<\/tr>\n<tr class=\"ro1\">\n<td class=\"ce2\">\n<p>54180<\/p>\n<\/td>\n<td class=\"ce4\">\n<p>47355<\/p>\n<\/td>\n<td class=\"ce4\">\n<p>6825<\/p>\n<\/td>\n<td class=\"ce4\">\n<p>6405<\/p>\n<\/td>\n<td class=\"ce4\">\n<p>420<\/p>\n<\/td>\n<td class=\"ce4\">\n<p>105<\/p>\n<\/td>\n<\/tr>\n<tr class=\"ro1\">\n<td class=\"ce1\">\n<p>6825<\/p>\n<\/td>\n<td class=\"ce3\">\n<p>6405<\/p>\n<\/td>\n<td class=\"ce3\">\n<p>420<\/p>\n<\/td>\n<td class=\"ce3\">\n<p>105<\/p>\n<\/td>\n<td class=\"ce3\">\n<p>0<\/p>\n<\/td>\n<td class=\"ce3\">\n<p>resto<\/p>\n<\/td>\n<\/tr>\n<\/table>\n<p>\\[<br \/>\n \\begin{align*}<br \/>\n r_1&#038;=a-q_1\\cdot b\\\\<br \/>\n   &#038;=a-b\\\\<br \/>\n r_2&#038;=b-q_2\\cdot r_1\\\\<br \/>\n    &#038;=b-6\\cdot (a-b)\\\\<br \/>\n    &#038;=7b-6a\\\\<br \/>\n r_3&#038;=r_1-1\\cdot r_2\\\\<br \/>\n    &#038;=(b-a)-(7b-6a)\\\\<br \/>\n    &#038;=-8b+7a\\\\<br \/>\n 105&#038;=r_2-15\\cdot r_3\\\\<br \/>\n    &#038;=(7b-6a)-15\\cdot-8b+7a\\\\<br \/>\n    &#038;=127b-111a<br \/>\n\\end{align*}<br \/>\n\\]<\/p>\n<p>El vector que buscamos es \\(v:[\u2212111,127]\\), ahora<br \/>\n\\[[3,2].v\/sqrt(v.v)=-\\left( \\frac{79}{5 \\sqrt{1138}}\\right)\\approx 0.47\\]\n<\/p><\/div>\n<hr \/>\n<blockquote>\n<p><strong>Ejemplo: <\/strong> Calcular los cocientes y restos necesarios para resolver  \\[43134x+343y=\\mathbf{mcd}(43134,343)\\]<\/p>\n<\/blockquote>\n<p><script>\nfunction showHtmlDiv2y() {\n  var htmlShow2y = document.getElementById(\"html-show2y\");\n  if (htmlShow2y.style.display === \"none\") {\n    htmlShow2y.style.display = \"block\";\n  } else {\n    htmlShow2y.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv2y()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show2y\" style=\"display: none;\">\nRealizando la tabla anterior, obtenemos los cocientes \\(q:[125,1,3,12]\\) y \\(\\mathbf{mcd}(43134,343)=7=r_3\\). Luego<br \/>\n\\[<br \/>\n \\begin{align*}<br \/>\n r_1&#038;=a-125\\cdot b\\\\<br \/>\n r_2&#038;=b-q_2\\cdot r_1\\\\<br \/>\n    &#038;=b-1\\cdot (a-125b)\\\\<br \/>\n    &#038;=126b-a\\\\<br \/>\n r_3&#038;=r_1-3\\cdot r_2\\\\<br \/>\n    &#038;=(a-125b)-(126b-a)\\\\<br \/>\n    &#038;=-503b+4a\\\\<br \/>\n\\end{align*}<br \/>\n\\]<br \/>\nPor tanto,<br \/>\n\\[ 7=4\\cdot 43134-503\\cdot 343\\]\n<\/div>\n<hr \/>\n<h3>Con matrices<\/h3>\n<p style=\"text-align:center\"><iframe loading=\"lazy\" width=\"560\" height=\"315\" src=\"https:\/\/www.youtube.com\/embed\/fAx0kBt8d5U\" title=\"YouTube video player\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" allowfullscreen><\/iframe><\/p>\n<hr \/>\n<blockquote>\n<p><strong>Ejemplo: <\/strong> Resolvamos utilizando matrices \\[43134x+343y=\\mathbf{mcd}(43134,343)\\]<\/p>\n<\/blockquote>\n<p><script>\nfunction showHtmlDiv2at7() {\n  var htmlShow2at7 = document.getElementById(\"html-show2at7\");\n  if (htmlShow2at7.style.display === \"none\") {\n    htmlShow2at7.style.display = \"block\";\n  } else {\n    htmlShow2at7.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv2at7()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show2at7\" style=\"display: none;\">\nConsideramos las matrices \\[\\begin{bmatrix}0 &#038; 1\\\\<br \/>\n1 &#038; -125\\end{bmatrix}{,}<br \/>\n\\begin{bmatrix}0 &#038; 1\\\\<br \/>\n1 &#038; -1\\end{bmatrix}{,}<br \/>\n\\begin{bmatrix}0 &#038; 1\\\\<br \/>\n1 &#038; -3\\end{bmatrix},<br \/>\n\\begin{bmatrix}0 &#038; 1\\\\<br \/>\n1 &#038; -12\\end{bmatrix}\\]<br \/>\ny hacemos la multiplicaci\u00f3n<br \/>\n\\[\\begin{align*}<br \/>\n\\begin{bmatrix}0 &#038; 1\\\\<br \/>\n1 &#038; -125\\end{bmatrix}{\\cdot}<br \/>\n\\begin{bmatrix}0 &#038; 1\\\\<br \/>\n1 &#038; -1\\end{bmatrix}{\\cdot}<br \/>\n\\begin{bmatrix}0 &#038; 1\\\\<br \/>\n1 &#038; -3\\end{bmatrix}\\cdot<br \/>\n\\begin{bmatrix}0 &#038; 1\\\\<br \/>\n1 &#038; -12\\end{bmatrix}&#038;=<br \/>\n\\begin{bmatrix}1 &#038; -1\\\\<br \/>\n-125 &#038; 126\\end{bmatrix}{\\cdot}<br \/>\n\\begin{bmatrix}0 &#038; 1\\\\<br \/>\n1 &#038; -3\\end{bmatrix}\\cdot<br \/>\n\\begin{bmatrix}0 &#038; 1\\\\<br \/>\n1 &#038; -12\\end{bmatrix}\\\\<br \/>\n&#038;=<br \/>\n\\begin{bmatrix}-1 &#038; 4\\\\<br \/>\n126 &#038; -503\\end{bmatrix}{\\cdot}<br \/>\n\\begin{bmatrix}0 &#038; 1\\\\<br \/>\n1 &#038; -12\\end{bmatrix}\\\\<br \/>\n&#038;=<br \/>\n\\begin{bmatrix}4 &#038; -49\\\\<br \/>\n-503 &#038; 6162\\end{bmatrix}<br \/>\n\\end{align*}\\]\n<\/div>\n<hr \/>\n<blockquote>\n<p><strong>Ejemplo: <\/strong> Sea v=[a,b], la  <strong>soluci\u00f3n de Bezout<\/strong> de \\(\\mathbf{mcd}(462,216)\\). \u00bfCu\u00e1nto es, en valor absoluto, el producto escalar [-1,5].v\/||v||? <\/p>\n<\/blockquote>\n<p><script>\nfunction showHtmlDiv2at() {\n  var htmlShow2at = document.getElementById(\"html-show2at\");\n  if (htmlShow2at.style.display === \"none\") {\n    htmlShow2at.style.display = \"block\";\n  } else {\n    htmlShow2at.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv2at()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show2at\" style=\"display: none;\">\nDeterminemos los cocientes<\/p>\n<table border=\"0\" cellspacing=\"0\" cellpadding=\"0\" class=\"ta1\" style=\"width:70%\" >\n<colgroup>\n<col width=\"99\"\/>\n<col width=\"99\"\/>\n<col width=\"99\"\/>\n<col width=\"99\"\/>\n<\/colgroup>\n<tr class=\"ro1\">\n<td style=\"text-align:left;width:1cm; \" class=\"Default\">\n<p>cociente<\/p>\n<\/td>\n<td style=\"text-align:right; width:1cm; \" class=\"Default\">\n<p>2<\/p>\n<\/td>\n<td style=\"text-align:right; width:1cm; \" class=\"Default\">\n<p>7<\/p>\n<\/td>\n<td style=\"text-align:right; width:1cm; \" class=\"Default\">\n<p>5<\/p>\n<\/td>\n<\/tr>\n<tr class=\"ro1\">\n<td style=\"text-align:right; width:1cm; \" class=\"Default\">\n<p>462<\/p>\n<\/td>\n<td style=\"text-align:right; width:1cm; \" class=\"Default\">\n<p>216<\/p>\n<\/td>\n<td style=\"text-align:right; width:1cm; \" class=\"Default\">\n<p>30<\/p>\n<\/td>\n<td style=\"text-align:right; width:1cm; \" class=\"Default\">\n<p style=\"color:#FF0000\";><strong>6<\/strong><\/p>\n<\/td>\n<\/tr>\n<tr class=\"ro1\">\n<td style=\"text-align:right; width:1cm; \" class=\"Default\">\n<p>30<\/p>\n<\/td>\n<td style=\"text-align:right; width:1cm; \" class=\"Default\">\n<p>6<\/p>\n<\/td>\n<td style=\"text-align:right; width:1cm; \" class=\"Default\">\n<p>0<\/p>\n<\/td>\n<td style=\"text-align:left;width:1cm; \" class=\"Default\">\n<p>resto<\/p>\n<\/td>\n<\/tr>\n<\/table>\n<p>Ahora consideramos las matrices \\[\\begin{bmatrix}0 &#038; 1\\\\<br \/>\n1 &#038; -2\\end{bmatrix}{,}\\begin{bmatrix}0 &#038; 1\\\\<br \/>\n1 &#038; -7\\end{bmatrix}{,}\\begin{bmatrix}0 &#038; 1\\\\<br \/>\n1 &#038; -5\\end{bmatrix},\\]<br \/>\ny hacemos la multiplicaci\u00f3n<br \/>\n\\[\\begin{bmatrix}0 &#038; 1\\\\<br \/>\n1 &#038; -2\\end{bmatrix}.\\begin{bmatrix}0 &#038; 1\\\\<br \/>\n1 &#038; -7\\end{bmatrix}.\\begin{bmatrix}0 &#038; 1\\\\<br \/>\n1 &#038; -5\\end{bmatrix}=\\begin{bmatrix}-7 &#038; 36\\\\<br \/>\n15 &#038; -77\\end{bmatrix}.\\]<br \/>\nEl vector que buscamos el la primera columna del producto de matrices \\(v:[-7,15]\\). Podemos verificar que \\[-7\\cdot 462+15\\cdot 216=6\\]<br \/>\nAhora solo nos resta calcular: \\[[-1,5].v\/\\|v\\|\\approx 4.95\\]\n<\/p><\/div>\n<hr \/>\n<h2><b>M\u00ednimo com\u00fan m\u00faltiplo<\/b><\/h2>\n<p>Aunque no lo utilizaremos tanto como el mcd tambi\u00e9n podemos definir el menor m\u00faltiplo com\u00fan de a un conjunto de enteros:<br \/>\nUn n\u00famero entero \\(m\\) se llama <b>m\u00ednimo com\u00fan m\u00faltiplo<\/b> de los n\u00fameros \\(a\\) y \\(b\\), que notaremos por \\(m=mcm(a,b)\\), cuando:<\/p>\n<ol>\n<li>\\(a|m\\) y \\(b|m\\); es decir,<i>m<\/i> es un m\u00faltiplo com\u00fan de los n\u00fameros \\(a\\) y \\(b\\) y<\/li>\n<li>\\(c\\in\\mathbb{Z}^+\\) es un m\u00faltiplo de \\(a\\) y \\(b\\), entonces \\(m\\leq c\\).<\/li>\n<\/ol>\n<blockquote>\n<p><strong>Teorema<\/strong>: Dados dos n\u00fameros enteros \\(a\\) y \\(b\\), entonces \\[mcm(a,b)=\\frac{|ab|}{\\mathbf{mcd}(a,b)}\\]<\/p>\n<\/blockquote>\n<hr \/>\n<h3>M\u00ednimo com\u00fan m\u00faltiplo con la calculadora<\/h3>\n<p><iframe loading=\"lazy\" title=\"Casio ClassWiz - \u00bfC\u00f3mo calcular el m\u00ednimo com\u00fan m\u00faltiplo de 2 n\u00fameros? #matem\u00e1ticas #calculadora\" width=\"540\" height=\"960\" src=\"https:\/\/www.youtube.com\/embed\/z7V3Hpz6wVI?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<hr \/>\n<h2>Funci\u00f3n \\(\\varphi\\) de Euler<\/h2>\n<blockquote><p>\n<strong>Definici\u00f3n:<\/strong> Llamaremos funci\u00f3n \\(\\varphi\\) de Euler a una funci\u00f3n, \\(\\varphi:\\mathbb{Z}^+\\to\\mathbb{Z}^+\\), dada por \\[\\varphi (n)=|\\{m\\in\\mathbb{Z}^+|m&lt;n, \\mathbf{mcd}(n,m)=1\\}|.\\]\n<\/p><\/blockquote>\n<blockquote>\n<p><strong>Ejemplo:<\/strong> Calcular \\(\\varphi(15)\\)<\/p>\n<\/blockquote>\n<p><script>\nfunction showHtmlDiv2b134() {\n  var htmlShow2b134 = document.getElementById(\"html-show2b134\");\n  if (htmlShow2b134.style.display === \"none\") {\n    htmlShow2b134.style.display = \"block\";\n  } else {\n    htmlShow2b134.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv2b134()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show2b134\" style=\"display: none;\">\nPara resolver el problema, solo necesitamos determinar \\(\\mathbf{mcd}(i,15)\\), para \\(i=1\\) hasta 14, y ver para cu\u00e1les de ellos el m\u00e1ximo com\u00fan divisor es 1. El resultado nos dar\u00e1 que hay 8 n\u00fameros que son coprimos con 15, en los 15 primeros n\u00fameros enteros positivos. Por tanto, \\(\\varphi(15)=8\\).\n<\/div>\n<hr \/>\n<h2><b>Ecuaci\u00f3n diof\u00e1ntica de 2 variables<\/b><\/h2>\n<p>Al tratar el <b>Teorema de B\u00e9zout<\/b> vemos que podemos resolver la ecuaci\u00f3n $ax+by=\\mathbf{mcd(a,b)}$ con soluciones $(x,y)\\in\\mathbb{Z}^2$. Vemamos como generalizamos este resultado.<\/p>\n<blockquote><p>\n<strong>Definici\u00f3n:<\/strong> LLamaremos ecuaci\u00f3n diof\u00e1ntica de dos variables a la ecuaci\u00f3n \\[ax+by=c,\\] siendo $a,b,c\\in\\mathbb{Z}$ con soluciones $(x,y)\\in\\mathbb{Z}^2$.\n<\/p><\/blockquote>\n<blockquote><p>\n<strong>Teorema:<\/strong> La ecuaci\u00f3n diof\u00e1ntica \\[ax+by=c,\\] tiene soluci\u00f3n si, y solo si, $\\mathbf{mcd}(a,b)|c$.\n<\/p><\/blockquote>\n<p>Si una ecuaci\u00f3n diof\u00e1ntica tiene soluci\u00f3n, nos apoyamos en el hecho de la existencia de una soluci\u00f3n particular, \\[ax_0+by_0=\\mathbf{mcd}(a,b),\\] dada por el Teorema de Bezout, y esto nos permitir\u00e1 encontrar las infinitas soluciones.<\/p>\n<blockquote>\n<p><strong>Teorema:<\/strong> La ecuaci\u00f3n \\(ax+by=c\\), donde \\(d=\\mathbf{mcd}(a,b)\\)  divide a \\(c\\), tendr\u00e1 por soluci\u00f3n general:<br \/>\n\\[\\begin{array}{l} X=x_0\\frac{c}{d}+\\frac{b}{d}k\\\\ Y=y_0\\frac{c}{d}-\\frac{a}{d}k \\end{array},\\]<\/p>\n<p>donde \\((x_0,y_0)\\) es una soluci\u00f3n de la ecuaci\u00f3n \\(ax+by=\\mathbf{mcd}(a,b)\\).<\/p>\n<\/blockquote>\n<blockquote>\n<p><strong>Ejercicio:<\/strong> Resolver la ecuaci\u00f3n diof\u00e1ntica \\(4x+22y=46\\).<\/p>\n<\/blockquote>\n<p><script>\nfunction showHtmlDiv1b() {\n  var htmlShow1b = document.getElementById(\"html-show1b\");\n  if (htmlShow1b.style.display === \"none\") {\n    htmlShow1b.style.display = \"block\";\n  } else {\n    htmlShow1b.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv1b()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show1b\" style=\"display: none;\">\nDeterminamos: \\(\\mathbf{mcd}(4,22)=2\\). Como 2|46, la ecuaci\u00f3n tiene soluci\u00f3n. Para resolverla necesitamos una soluci\u00f3n de \\(4x_0+22y_0=2\\), por ejemplo \\((6,-1)\\) (si la soluci\u00f3n no se aprecia de forma sencilla, podemos utilizar la soluci\u00f3n de B\u00e9zout). Ahora estamos en condiciones de aplicar el Teorema:<br \/>\n\\[\\begin{align*}<br \/>\n x&#038;=6\\cdot\\frac{46}{2}+\\frac{22}{2}k=138+11k \\\\<br \/>\n y&#038;=-1\\cdot\\frac{46}{2}-\\frac{4}{2}k=-23-2k<br \/>\n\\end{align*}\\]<\/p>\n<\/div>\n<hr \/>\n<blockquote>\n<p><strong>Ejercicio:<\/strong> Resolver la ecuaci\u00f3n diof\u00e1ntica \\(6x+15y=36\\).<\/p>\n<\/blockquote>\n<p><script>\nfunction showHtmlDiv1c() {\n  var htmlShow1c = document.getElementById(\"html-show1c\");\n  if (htmlShow1c.style.display === \"none\") {\n    htmlShow1c.style.display = \"block\";\n  } else {\n    htmlShow1c.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv1c()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show1c\" style=\"display: none;\">\nDeterminamos: \\(\\mathbf{mcd}(6,15)=3\\). Como 3|36, la ecuaci\u00f3n tiene soluci\u00f3n. Para resolverla necesitamos una soluci\u00f3n de \\(6x_0+15y_0=3\\), por ejemplo \\((-2,1)\\). Ahora estamos en condiciones de aplicar el Teorema:<br \/>\n\\[\\begin{align*}<br \/>\n x&#038;=-2\\cdot\\frac{36}{3}+\\frac{15}{3}k=-24+5k \\\\<br \/>\n y&#038;=1\\cdot\\frac{36}{3}-\\frac{6}{3}k=12-2k<br \/>\n\\end{align*}\\]<br \/>\nObservemos el siguiente detalle, si hacemos el cambio \\(k=n+5\\) ser\u00e1<br \/>\n\\[\\begin{align*}<br \/>\n x&#038;=-24+5k=-24+5(n+5)=1+5n \\\\<br \/>\n y&#038;=12-2k= 12-2(n+5)=2-2n<br \/>\n\\end{align*}\\]\n<\/div>\n<hr \/>\n<blockquote>\n<p><strong>Ejercicio:<\/strong> Sea \\(v\\) la menor de las soluciones positivas de 34x-56y=4, \u00bfcu\u00e1l es el valor de [3,-4].v?<\/p>\n<\/blockquote>\n<p><script>\nfunction showHtmlDiv1d() {\n  var htmlShow1d = document.getElementById(\"html-show1d\");\n  if (htmlShow1d.style.display === \"none\") {\n    htmlShow1d.style.display = \"block\";\n  } else {\n    htmlShow1d.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv1d()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show1d\" style=\"display: none;\">\nPrimero vemos que \\[34x-56y=4\\Leftrightarrow 34x+56(-y)=4\\Leftrightarrow 34x+56z=4 \\] donde \\(z=-y\\). Resolvamos, ahora, \\[34x+56z=4\\] Determinamos: \\(\\mathbf{mcd}(34,56)=2\\). Como 2|4, la ecuaci\u00f3n tiene soluci\u00f3n. Para resolverla necesitamos una soluci\u00f3n de \\(34x_0+56z_0=2\\), por ejemplo \\((5,-3)\\). Ahora estamos en condiciones de aplicar el Teorema:<br \/>\n\\[\\begin{align*}<br \/>\n x&#038;=5\\cdot\\frac{4}{2}+\\frac{56}{2}k=10+28k \\\\<br \/>\n z&#038;=-3\\cdot\\frac{4}{2}-\\frac{34}{2}k=-6-17k<br \/>\n\\end{align*}\\]<br \/>\nComo \\(z=-y\\) ser\u00e1 \\(y=-z\\), luego<br \/>\n\\[\\begin{align*}<br \/>\n x&#038;=10+28k \\\\<br \/>\n y&#038;=6+17k<br \/>\n\\end{align*}\\]<br \/>\nObviamente, la primera soluci\u00f3n positiva ser\u00e1 para \\(k=0\\), luego \\(v=[10,6]\\). Por tanto la respuesta es: \\[[3,-4].[10,6]=6\\]\n<\/div>\n<hr \/>\n<p>Veamos otra forma de afrontar cuando uno de los coeficientes \\(a\\) o \\(b\\), de la ecuaci\u00f3n \\(ax+by=c\\) es negativo:<\/p>\n<blockquote>\n<p><strong>Ejercicio:<\/strong> Sea <strong>v<\/strong>\\(:(x_m,y_m)\\) la soluci\u00f3n de 48x-27y=129, tal que \\(y_m=\\mathbf{max}\\{y_s&lt;0;\\ 48x_s-27y_s=129\\}\\). \u00bfCu\u00e1l es el valor de [1,-2].<strong>v<\/strong>?<\/p>\n<\/blockquote>\n<p><script>\nfunction showHtmlDiv1a() {\n  var htmlShow1a = document.getElementById(\"html-show1a\");\n  if (htmlShow1a.style.display === \"none\") {\n    htmlShow1a.style.display = \"block\";\n  } else {\n    htmlShow1a.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv1a()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show1a\" style=\"display: none;\">\n<p>Calculemos el m\u00e1ximo com\u00fan divisor:<\/p>\n<table align=\"center\" border=\"1\">\n<colgroup width=\"67\">\n\t<\/colgroup>\n<colgroup span=\"6\" width=\"27\">\n\t<\/colgroup>\n<tbody>\n<tr>\n<td align=\"right\" height=\"17\">cociente<\/td>\n<td align=\"left\">&nbsp;<\/td>\n<td align=\"right\" sdnum=\"3082;\" sdval=\"-1\">-1<\/td>\n<td align=\"right\" sdnum=\"3082;\" sdval=\"-2\">-2<\/td>\n<td align=\"right\" sdnum=\"3082;\" sdval=\"1\">1<\/td>\n<td align=\"right\" sdnum=\"3082;\" sdval=\"2\">2<\/td>\n<td align=\"right\" sdnum=\"3082;\" sdval=\"2\">2<\/td>\n<\/tr>\n<tr>\n<td align=\"left\" height=\"17\">&nbsp;<\/td>\n<td align=\"right\" sdnum=\"3082;\" sdval=\"48\">48<\/td>\n<td align=\"right\" sdnum=\"3082;\" sdval=\"-27\">-27<\/td>\n<td align=\"right\" sdnum=\"3082;\" sdval=\"21\">21<\/td>\n<td align=\"right\" sdnum=\"3082;\" sdval=\"15\">15<\/td>\n<td align=\"right\" sdnum=\"3082;\" sdval=\"6\">6<\/td>\n<td align=\"right\" sdnum=\"3082;\" sdval=\"3\">3<\/td>\n<\/tr>\n<tr>\n<td align=\"right\" height=\"17\">resto<\/td>\n<td align=\"right\" sdnum=\"3082;\" sdval=\"21\">21<\/td>\n<td align=\"right\" sdnum=\"3082;\" sdval=\"15\">15<\/td>\n<td align=\"right\" sdnum=\"3082;\" sdval=\"6\">6<\/td>\n<td align=\"right\" sdnum=\"3082;\" sdval=\"3\">3<\/td>\n<td align=\"right\" sdnum=\"3082;\" sdval=\"0\">0<\/td>\n<td align=\"left\">&nbsp;<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>Observemos que \\(\\text{mcd}(48,-27)=3\\), y \\((4)48+(7)(-27)=3\\), luego \\(x_0=4\\), \\(y_0=7\\)<br \/>\n\\[\\begin{array}{ccc}\\begin{array}{l}x=4\\cdot \\frac{129}{3}+\\frac{(-27)}{3} k\\\\ y=7\\cdot \\frac{129}{3}-\\frac{48}{3} k\\end{array}&#038; \\to &#038; \\begin{array}{l}x=172+(-9) k \\\\ y=301-16 k\\end{array} \\end{array}\\]<\/p>\n<p>Como buscamos la soluci\u00f3n cuya \\(y_s\\) negativa sea m\u00e1s pr\u00f3xima a cero, elegimos \\(k=\\left \\lfloor  \\frac{301}{16}\\right \\rfloor=18\\)<br \/>\n\\[\\begin{array}{c|c|c|c}<br \/>\nk &#038; 18 &#038; 19 &#038; 20  \\\\ \\hline<br \/>\nx &#038; 10 &#038; 1  &#038; -8  \\\\<br \/>\ny &#038; 13 &#038; -3 &#038; -19<br \/>\n\\end{array}\\]<\/p>\n<p>Luego, concluimos que [1,-3].[1,-2]=7.\n<\/p><\/div>\n<hr \/>\n<p>&nbsp;<\/p>\n<table id=\"yzpi\" border=\"0\" width=\"100%\" cellspacing=\"0\" cellpadding=\"3\" bgcolor=\"#999999\">\n<tbody>\n<tr>\n<td width=\"100%\">\n<p><strong>Ejercicio:<\/strong> Si 10=A, 11=B, 12=C, 13=D, 14=E, \u00bfcu\u00e1l car\u00e1cter no aparece en la representaci\u00f3n de \\((F_5)_{10}\\) en base 15?<\/p>\n<div id=\"menu-a\">\n<ul>\n<li>A<\/li>\n<li>B<\/li>\n<li>C<\/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>B.)<\/strong><\/p>\n<p>Si realizamos el algoritmo de la divisi\u00f3n:<br \/>\n\\[\\begin{align*}<br \/>\n4294967297&#038;=(286331153)15+2\\\\<br \/>\n286331153&#038;=(19088743)15+8\\\\<br \/>\n19088743&#038;=(1272582)15+D\\\\<br \/>\n1272582&#038;=(84838)15+C\\\\<br \/>\n84838&#038;=(5655)15+D\\\\<br \/>\n5655&#038;=(377)15+0\\\\<br \/>\n377&#038;=(25)15+2\\\\<br \/>\n25&#038;=(1)15+A\\\\<br \/>\n1&#038;=(0)15+1\\\\<br \/>\n\\end{align*}\\]\n<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>M\u00e1ximo com\u00fan divisor Consideremos dos n\u00fameros enteros Si \\(a\\) y \\(b\\) distintos de cero, decimos que \\(c\\) es un divisor com\u00fan de \\(a\\) y \\(b\\) si \\(c|a\\) y \\(c|b\\). Cuando existen, \u00fanicamente,&#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":[],"class_list":["post-755","post","type-post","status-publish","format-standard","hentry","category-matematica-discreta"],"_links":{"self":[{"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=\/wp\/v2\/posts\/755","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=755"}],"version-history":[{"count":21,"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=\/wp\/v2\/posts\/755\/revisions"}],"predecessor-version":[{"id":841,"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=\/wp\/v2\/posts\/755\/revisions\/841"}],"wp:attachment":[{"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=755"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=755"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=755"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}