.. -*- coding: utf-8 -*-



Ejercicios
::::::::::

1.
~~

El teorema de Euler afirma que para un número  *a*  y un número  *m* , se tiene:


.. MATH::
    a^{\varphi(m)}\equiv 1(mod \;m)


para la función :math:`\varphi` de Euler, siempre que  *a*  y  *m*  sean primos entre sí.


 - Escribe un programa que compruebe el teorema para los números m menores que 1000 y todos los números a<m.

 - ¿Es cierto que si se verifica la igualdad, entonces necesariamente *a*  y  *m*  son primos entre sí? Busca un contraejemplo, o verífica la propiedad para todos los números  *m*  menores que 1000.

 - ¿Es :math:`\varphi(m)` siempre el menor número posible que verifica esta identidad para todos los números  *a*  que son primos relativos con  *m* ? Busca un contraejemplo, o verífica la propiedad para todos los números  *m*  menores que 1000.

 - Dados dos números  *a*  y  *m* , encuentra el menor número positivo  *k*  tal que  :math:`a^k\equiv 1 (mod \;m)`

 - Dado un número  *m* , encuentra el menor número positivo  *k*  tal que  :math:`a^k\equiv 1 (mod \;m)`  *para todo a que sea primo relativo con m* . Llamemos :math:`\lambda(m)` al número k así obtenido.

2.
~~

Como vimos en el ejercicio anterior, :math:`\lambda(m)` no siempre coincide con :math:`\varphi(m)`. Para cada una de las preguntas siguientes,  busca un contraejemplo, o verifica la propiedad para todos los números menores que 1000.




 - ¿Coinciden siempre para los números :math:`m=p^j` cuando  *p*  es primo?


 - ¿Coinciden siempre para los números :math:`m=p^j` cuando  *p*  es primo  *impar* ?


 - ¿Coinciden siempre para los números :math:`m=p^j\:q^k` cuando  *p*  y  *q*  son primos impares?



3. Ejercicio opcional
~~~~~~~~~~~~~~~~~~~~~




 - Intenta relacionar :math:`\lambda(p^j\:q^k)` con los valores de :math:`\lambda(p^j)` y :math:`\lambda(q^k)`.


 - Conjetura una fórmula que expresa :math:`\lambda(p_1^{j_1}\dots p_L^{j_L})` en función de :math:`\lambda(p_1^{j_1})`, :math:`\lambda(p_2^{j_2})`,... hasta :math:`\lambda(p_L^{j_L})`.


4. Raíces racionales de polinomios con coeficientes enteros
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


 Comprueba el criterio que aprendimos en secundaria sobre las raíces racionales de un polinomio con coeficientes enteros:


*Cualquier raíz racional de un polinomio con coeficientes enteros   tiene un numerador que divide al término independiente y un denominador   que divide al coeficiente del término de mayor grado.*




 - Escribe código que busque las raíces de un polinomio con coeficientes enteros según este criterio


 - Escribe código que compruebe que el resultado coincide con el resultado de llamar al método roots, para un conjunto de polinomios que te parezca lo bastante significativo.


5.
~~

Investiga la siguiente pregunta:


Dado un polinomio  *p*  con coeficientes enteros, ¿para cuántos valores de  *k*  el polinomio  *p\+k*  es reducible? ¿para cuántos valores tiene al menos una raíz (entera)?


 - Escribe una función que acepte como argumentos un polinomio  *p*  con coeficientes enteros y dos enteros  *k1*  y  *k2* , y devuelva en una lista todos los enteros  *j*  entre   *k1*  y  *k2*  tal que  *p\+j*  tiene alguna raíz entera.


 - Escribe una función que acepte como argumentos un polinomio  *p*  con coeficientes enteros y dos enteros  *k1*  y  *k2* , y devuelva en una lista todos los enteros  *j*  entre   *k1*  y  *k2*  tal que  *p\+j*  es reducible sobre :math:`\mathbb{Q}`.


 - ¿Te parece razonable la siguiente conjetura?: "La cantidad de enteros  *j*  en el intervalo [\-K, K] tal que  *p\+j*  tiene alguna raíz entera crece como :math:`O(K^{1/n})`, donde  *n*  es el grado del polinomio  *p* ". Medita un momento al respecto.


 - Argumenta con datos empíricos si la conjetura análoga para  polinomios reducibles es razonable, o no, estimando el ratio entre los  polinomios que verifican una u otra condición.