metodo chino del resto y ptf

Primero observemos que $65=5*13$. Ahora recordemos que si$p, q$ son primos entonces decir $pq|m$ es equivalente a decir $p|m$ y $q|m.$ Tenemos entonces que $f(n)$ divisible entre $65$ equivale a decir $f(n)$ divisible entre $5$ y $f(n)$ divisible entre $13$. Este hecho hace posible descomponer el problema en dos subproblemas.

Así pues, $f(n) \equiv 0(mod \ 65)$ si y sólo si $f(n) \equiv 0(mod \ 5)$ y $f(n) \equiv 0(mod\ 13).$ Resolvamos cada uno de ellos:

De $f(n) \equiv 0(mod\ 5)$ se sigue, de acuerdo al pequeño teorema de Fermat, que $13n+9an \equiv 0(mod\ 5).$ Es decir, $n(13+9a) \equiv 0(mod\ 5)$ y, de aquí, que $13+9a \equiv 0(mod\ 5)$ –pues debe cumplirse la congruencia para todo entero n1). Finalmente, esta ecuación de congruencias se simplifica a $a \equiv 3(mod\ 5).$

De $f(n)\equiv 0(mod\ 13)$ se sigue, de nuevo por el pequeño teorema de Fermat, que $5n+9an \equiv 0(mod\ 13).$ Es decir, $n(5+9a) \equiv 0 (mod\ 13)$ y, de aquí, que $5+9a\equiv 0(mod\ 13).$ Finalmente, la ecuación se simplifica a $a\equiv 11(mod\ 13).$

El resultado es que tenemos que resolver el sistema de congruencias

$a \equiv 3(mod\ 5)$

$a \equiv 11(mod\ 13)$

Para el primer número se encuentra de inmediato el $13=2(5)+3.$ Para el segundo, nos apoyamos en el hecho de que $40=39+1.$ Es decir, $40 \equiv 1 (mod\ 13).$ Por lo tanto, $40(11) = 440 \equiv 11(mod\ 13).$ Es decir, el segundo número es $440$. Por tanto, una solución del sistema es $a=440+13 = 453$. Pero también es solución a$=453+65k=63+6(65)+65k$. Entonces, la solución mínima es $a=63.$

Vamos a resolver el sistema de congruencias

$a \equiv 3(mod\ 5)$

$a \equiv 11(mod\ 13)$

con el método diofantino, como una forma de compararlo con el método chino:

$a=5r+3=13s+11$

$5r=13s+8$

$r=2s+1+(3s+3)/5$

$x=(3s+3)/5$

$5x=3s+3$

$3s=5x-3$

$s=x-1+2x/3$

$y=2x/3$

$3y=2x$

$x=3y/2=y+y/2$

$z=y/2$

$y=2z$

$x=3z$

$s=3z-1+2z=5z-1$

$a=13s+11=13(5z-1)+11=65z-13+11=65z-2$

Solución mínima positiva: $a= 63$

Aquí se puede ver que el método chino del resto puede llegar a ser más eficiente que el método diofantino. Éste, sin embargo, tiene la ventaja de olvidarse de las congruencias. Es por ello recomendado para los novicios que todavía no confían plenamente en el álgebra de congruencias.

Otro detalle importante a comentar es que el pequeño teorema de Fermat es obligatorio para poder resolver este problema. Sin esa herramienta, simplemente no se puede continuar hasta llegar al sistema de congruencias que lo resuelve. Por esa razón este problema tiene dos niveles de complejidad, lo cual lo convierte en un problema verdaderamente difícil.