OMA Foros

Hola a todos,

comparto con ustedes los problemas de los exámenes selectivos de Perú de este año:

http://www.fileden.com/files/2008/5/31/ ... no2012.pdf

Definimos al [math]n-ésimo polinomio ciclotómico para cualquier entero positivo [math]n como el polinomio mónico [math]\Phi_n que tiene como raíces a las raíces primitivas [math]n-ésimas de la unidad
Notemos que como hay [math]\varphi (n) raíces primitivas [math]n-ésimas de la unidad el grado de [math]\Phi_n es [math]\varphi (n).

Propiedad 1: [math]X^n - 1 = \displaystyle\prod_{d\mid n} \Phi_d (X)

Demostración:

Las raíces del polinomio del lado izquierdo son las raíces [math]n-ésimas de la unidad. Ahora, si [math]\omega es una raíz primitiva [math]d-ésima de la unidad es una raíz de [math]\Phi_d. Pero [math]d\mid n, entonces existe [math]t\in \mathbb{N} tal que [math]n=dt y así [math]\omega^n = \omega^{dt} = (\omega^d)^t = 1, y es raíz del polinomio del lado izquierdo. Como tienen las mismas raíces y son mónicos, por factorización única de polinomios estamos. [math]\blacksquare

Propiedad 2: [math]\Phi_n (X) = \displaystyle\prod_{d\mid n} (X^{\frac{n}{d}} -1)^{\mu (d)}

Demostración:

Se sigue de aplicar logaritmo a ambos lados sobre la fórmula de la propiedad 1, luego la Fórmula de Inversión de Möbius y deshacer el logaritmo. [math]\blacksquare

Observación: [math]\Phi_n( X ) es un polinomio con coeficientes enteros. Es decir, [math]\Phi_n(X) \in \mathbb{Z}[X].

Lema 1: Sea [math]p un primo. Si [math]X^n - 1 tiene raíz doble módulo [math]p, es decir, existe un entero [math]a y un polinomio [math]f(X)\in\mathbb{Z}[ X ] tal que [math]X^n - 1 = (X-a)^2 f(X) \pmod{p} Luego, [math]p\mid n.

Demostración (No elemental):

Derivamos a ambos lados. [math]nX^{n-1} \equiv (X-a)(2f(X) + (X-a)f'(X)) \pmod{p}. Si lo evaluamos en [math]X=a, se sigue que [math]na^{n-1} \equiv 0 \pmod{p}. Como es claro que [math]a\not\equiv 0 \pmod{p} se sigue que [math]p\mid n. [math]\blacksquare

Lema 2:

Sea [math]n un entero positivo, [math]t<n un divisor de [math]n y [math]\alpha un entero. Supongamos que [math]p primo es un divisor de [math]\Phi_n (\alpha) y de [math]\Phi_t (\alpha). Luego, [math]p\mid n.

Demostración:

Por la propiedad 1, [math]\alpha^n - 1 = \displaystyle\prod_{d\mid n} \Phi_d (\alpha). Luego, [math]\Phi_n (\alpha) \Phi_d (\alpha) \mid \alpha^n -1, de donde [math]p^2 \mid \alpha^n - 1 y así el polinomio [math]X^n - 1 tiene raíz doble en [math]\alpha módulo [math]p. En virtud del lema 1 estamos. [math]\blacksquare

Teorema 1:

Sea [math]n un entero positivo, [math]p un primo y [math]\alpha un entero. Supongamos que [math]p\mid \Phi_n (\alpha) entonces [math]p\equiv 1 \pmod{n} ó [math]p\mid n.

Demostración:

Notemos que [math]p \nmid \alpha pues [math]p\mid \Phi_n(\alpha) \mid \alpha^n - 1. De [math]p\mid \alpha^n - 1 se sigue que [math]\alpha^n \equiv 1 \pmod{p}. Luego, si [math]\text{ord}_p(\alpha) = r, tenemos que [math]r\mid n.

Si [math]r=n tenemos que [math]n\mid p-1 por Pequeño Teorema de Fermat. Es decir, [math]p \equiv 1 \pmod{n}.

Si [math]r<n luego, [math]0 \equiv \alpha^{r}-1 = \displaystyle\prod_{d\mid r} \Phi_{d}(\alpha) \pmod{p}. Luego, como [math]p es primo, se sigue que existe algún [math]t\mid r tal que [math]p \mid \Phi_t(\alpha). Pero [math]t\mid r \mid n y [math]t < n, entonces, en virtud del lema 2, [math]p\mid n.

Y estamos. [math]\blacksquare

Corolario interesante: Sea [math]p un primo y [math]\alpha un entero. Todo divisor primo [math]q de [math]1 + \alpha + \ldots + \alpha^{p-1} es de la forma [math]q\equiv 1 \pmod{p} ó [math]q=p.

Demostración:

Notemos que [math]1 + \alpha + \ldots + \alpha^{p-1} = \dfrac{\alpha^{p}-1}{\alpha-1} = \dfrac{\alpha^{p}-1}{\Phi_1(\alpha)} = \Phi_p(\alpha).
Luego, si [math]q\mid \Phi_p(\alpha), tenemos por el Teorema 1 lo que queríamos. [math]\blacksquare


Antes de seguir con más propiedades, podemos resolver un problema, para ilustrar la magia:

Ejercicio 1: (IMO Shortlist 2006 N5) Demostrar que [math]\dfrac{x^{7} - 1}{x - 1} = y^{5} - 1 no tiene soluciones con [math]x,y enteros.

Solución:

Vamos a reescribir lo que tenemos como [math]\Phi_7(x) = (y-1)(1 + y + y^2 + y^3 + y^4).

Notemos por el Teorema 1 (o más bien su corolario) que si [math]d\mid \Phi_7 (x) entonces [math]d\equiv 0,1\pmod{7}. Luego, como [math]y-1 es un divisor, se sigue que [math]y-1 \equiv 0, 1\pmod{7} dando dos casos posibles [math]y\equiv 1,2\pmod{7}. Pero notemos que [math]1+y+y^2 + y^3 + y^4 es un divisor tambien. Pero como [math]y\equiv 1,2\pmod{7} se sigue que [math]1+y+y^2 +y^3 + y^4 \equiv 5,3 \not\equiv 0,1 \pmod{7}. Absurdo. La ecuación no tiene soluciones enteras. [math]\blacksquare

Problema:

Determinar todos los enteros positivos [math]n para los cuales existe algún entero [math]m tal que [math]{2^{n}-1} divide a [math]{m^{2}+9}.

http://omaforos.com.ar/viewtopic.php?f=11&t=858&p=2846

Fuente:
http://www.yimin-ge.com/doc/cyclotomic_polynomials.pdf

Una función aritmética [math]f(n) es aquella que está definida de los enteros positivos en los reales o complejos.

Decimos que la función aritmética [math]f \neq 0 es multiplicativa si para enteros positivos coprimos [math]m y [math]n cualesquiera se cumple que [math]f(mn) = f(m)f(n).

Es inmediato que si [math]f(n) y [math]g(n) son dos funciones multiplicativas entonces la función [math]f(n)g(n) es multiplicativa.

Notemos que si [math]f es multiplicativa, entonces [math]f(1)=1. En efecto, si [math]a es un entero positivo tal que [math]f(a)\neq 0 entonces [math]f(a) = f(a\cdot 1) = f(a)f(1), y simplificando [math]f(a) se obtiene que [math]f(1)=1. También observemos que si [math]n = p_1^{\alpha_1} \cdots p_k^{\alpha_k} entonces [math]f(n) = f(p_1^{\alpha_1})\cdots f(p_k^{\alpha_k}).

Una función aritmética muy importante es la función de Möbius, [math]\mu :\mathbb{Z^{+}}\to \{-1,0,1\} definida como:
[math]\mu (n) = \begin{cases} 1 &\mbox{si } n=1 \\ 0 &\mbox{si } p^2 \mid n \mbox{ para algún primo } p>1 \\ (-1)^k &\mbox{si } n=p_1\cdots p_k, \mbox{ donde } p_1, \ldots , p_k \mbox{ son primos distintos} \end{cases}.

Se ve fácilmente que [math]\mu es multiplicativa (es simplemente aplicar la definición).

Para una función aritmética [math]f, vamos a definir la función de suma [math]F de [math]f de manera que [math]F(n) = \displaystyle\sum_{d\mid n} f(d).

Fórmula de Inversión de Möbius: Sea [math]f una función aritmética y [math]F su función de suma. Entonces

Demostración:



Teorema: Sea [math]g una función aritmética. Entonces [math]g es multiplicativa si y sólo si su función suma [math]G es multiplicativa.

Demostración:

Demostremos el si primero. Escribimos

Ahora demostremos la vuelta. Para ello, vamos a usar la Fórmula de Inversión de Möbius:



Dejo dos problemas que salen con esto:

Ejercicio 1: (Problema 3 Selectivo de IMO Argentina 1992)

Sea [math]a_n [math](n\geq 1) la sucesión definida por:



Por ejemplo, si [math]n=6:



Demostrar que [math]n\mid a_n para todo [math]n.

Ejercicio 2: (IMO Shortlist 2004 N2 inciso a)

Sea [math]f:\mathbb{N}\to\mathbb{N} tal que



Demostrar que [math]f(mn)=f(m)f(n) para todos [math]m,n coprimos.

¿Existen [math]2011 enteros positivos [math]a_1 < a_2 < \ldots < a_{2011} tal que [math]\text{mcd}(a_i,a_j) = a_j - a_i para cualquier [math]i, j tal que [math]1 \le i < j \le 2011?

En el triángulo acutángulo [math]\triangle ABC, [math]M y [math]N son los puntos medios de [math]AB y [math]BC respectivamente y [math]H es el pie de la altura desde [math]B. Los circuncirculos de los triangulos [math]\triangle AHN y [math]\triangle CHM se intersecan en el punto [math]P \neq H. Probar que la recta [math]PH biseca al segmento [math]MN.