Puntos primitivos (y un EXTRA)

El problema de esta semana es el último problema de la pasada Olimpiada Internacional de Matemáticas, celebrada en Río de Janeiro el pasado mes de julio. Ahí va:

Un par ordenado (x,y) de enteros es un punto primitivo si el máximo común divisor de x e y es 1.

Dado un conjunto finito S de puntos primitivos, demostrar que existen un entero positivo n y enteros a_0,a_1, \ldots, a_n tales que, para cada (x,y) \in S, se cumple que:

a_ox^n+a_1x^{n-1}y+a_2x^{n-2}y^2+ \ldots +a_{n-1}xy^{n-1}+a_ny^n=1

A por él.

Extra:

El otro día compartí en la página de Facebook de Gaussianos un post en el que hablan sobre los entresijos de la Olimpiada Internacional de Matemáticas. Os recomiendo que le echéis un vistazo, es interesante: Más detalles de la Olimpiada Internacional de Matemáticas.

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

7 Comentarios

  1. Trataría de probar primero que para cualquier (x, y) primitivos existen a y b tales que ax+by=1. Luego que si a1x1+b1y1=1 y s2x2+b2y2=1 se pueden derivar a y b tales que ax1+by1=ax2+by2=1.
    Con eso ya estaría, ya que (ax+by)^n=1

    Publica una respuesta
    • Sí, Bezout se puede usar sin demostración. Y lo segundo es imposible, pero seguro que Alejandro ya se ha dado cuenta de eso.

      Publica una respuesta
  2. El problema es muy interesante! El caso en que el número de elementos de S es 1 es Bezout. Voy a hacer el caso en que S tiene dos elementos (que ya es curioso).

    Primero supongamos que los elementos de S son el (1,0) y otro, digamos (x,y). Para que se cumpla la ecuacion pedida para el (1,0) se tiene que cumplir que
    a_0=1. Entonces se tendria que

     y(a_1x^{n-1}+\cdots + a_ny^{n-1})=1-x^n

    con lo que y tiene que dividir a 1-x^n. Eso ya prueba que n no puede ser 1 o 2 en general. Que existe un tal n se puede deducir de la teoria de congruencias, por ejemplo, usando que x e y son coprimos; por lo tanto x es invertible modulo y. Una vez escogido este n, sea

    d:=(1-x^n)/y

    Como x e y son coprimos, x^{n-1} e y^{n-1} tambien lo son, por lo que existen b_1 y b_2 tales que

    b_1x^{n-1}+b_2y^{n-1}=1

    Tomemos entonces a_1=db_1, a_n=db_2 y el resto de a_i igual a 0.

    Ahora el caso general (con dos elementos). Supongamos que los elementos de S son (z,t) y (x,y). Sean e y f tales que

    e z+f t=1

    que existen por Bezout. Entonces el canvio de variable (r,s) va a (er+ft,-tr+zs) manda (z,t) a (1,0). Ademas es invertible, dado que la matriz correspondiente tiene determinante 1. Esto nos permite reducirnos al caso anterior.

    Publica una respuesta
  3. Existe un conjunto finito, más aún, infinito de tales punto primitivos …. basta que x = y+1, con y natural … Todos esos puntos cumplen que 1x – 1y = 1 …. Elevando esta igualdad a la n-sima potencia se obtiene el resultado pedido.

    Publica una respuesta
    • Perdona, parece que no has cambiado la hora del reloj … Te lo he mandado a las 23:25 del 31 de Octubre y marca el día 1 de Noviembre.

      Publica una respuesta
  4. Es más … existen infinitos conjuntos Sm = { (my+1; y) } con ‘y’ natural mayor que 1, para evitar los puntos (x, 1), y ‘m’ un natural mayor que cero.

    Es fácil probar que la pareja (x=my+1; y) son coprimos, basta aplicar el algoritmo de Euclides.

    Por su definición cumplen que x -my = 1 y elevando dicha igualdad a la n-sima potencia se obtiene el resultado pedido.

    Por la definición de Sm … el ejemplo que escribí antes correspondería con el valor para m = 1.

    cqd …

    Publica una respuesta

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *