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
de enteros es un punto primitivo si el máximo común divisor de
e
es 1.
Dado un conjunto finito
de puntos primitivos, demostrar que existen un entero positivo
y enteros
tales que, para cada
, se cumple que:
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.
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
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
La identidad de Bézout prueba lo primero
Sí, Bezout se puede usar sin demostración. Y lo segundo es imposible, pero seguro que Alejandro ya se ha dado cuenta de eso.
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
y otro, digamos 
. Para que se cumpla la ecuacion pedida para el 
se tiene que cumplir que
. Entonces se tendria que
con lo que
tiene que dividir a 
. Eso ya prueba que 
no puede ser 1 o 2 en general. Que existe un tal 
se puede deducir de la teoria de congruencias, por ejemplo, usando que 
e 
son coprimos; por lo tanto 
es invertible modulo 
. Una vez escogido este 
, sea
Como
e 
son coprimos, 
e 
tambien lo son, por lo que existen 
y 
tales que
Tomemos entonces
, 
y el resto de 
igual a 0.
Ahora el caso general (con dos elementos). Supongamos que los elementos de S son
y 
. Sean 
y 
tales que
que existen por Bezout. Entonces el canvio de variable
va a 
manda 
a 
. Ademas es invertible, dado que la matriz correspondiente tiene determinante 1. Esto nos permite reducirnos al caso anterior.
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.
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.
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 …