jueves, 12 de agosto de 2010

Problema del día 11

(Este es el problema que Fer no pudo poner en una nueva entrada)

El problema del día 11 es el siguiente:
Probar que la secuencia 1, 11, 111,... contiene una subsecuencia de primos relativos por parejas.

8 comentarios:

Georges dijo...

Ya lo habia puesto!!... pero bueno.. lo ponemos 2 veces para que todos lo vean jaja

Unknown dijo...

Pues creo que este problema ya lo había hecho alguna vez.

Denotamos $a_{k}$ al número con k 1's. Como $a_{kt}=a_{k}+10a_{k}+...+10^{t-1}a_{k}$ entonces $a_{k}$ divide a a_{kt}.
Supongamos que ya construimos el conjunto $A=\{a_{k_{1}}, a_{k_{2}},..., a_{k_{n}}\}$ con todos sus elementos primos relativos por parejas. Tomamos $c=\[k_{1}, k_{2},..., k_{n}\]$ y a $A$ le agregamos $10a_{c}+1$. Hacemos esto indefinidamente y la cardinalidad de $A$ aumenta tanto como queramos.

(Creo que esta prueba no está bien si lo que queremos es una subsucesión infinita, o si?)

Unknown dijo...

Donde dice LAtex failed iba $c=[k_{1}, k_2,..., k_{n}]$

Unknown dijo...

jajaja, cuando se me ocurrió ponerlo todavía no estaba tu entrada

Manuel Dosal dijo...

Solucion.
Sea $N_{n}=111...11$ donde el 1 aparece n veces.
Veamos que si $p$ es un primo que divide a algun $N_{n}$.Entonces sea $N_{k}$ el menor numero en la secuencia el cual es multiplo de $p$. Entonces veamos que $N_{k+1}=10N_{k}+1$ $\Rightarrow N_{k+1}\equiv 1\pmod{p}$ y por induccion $N_{k+r}\equiv N_{r}\pmod{p}$ $\Rightarrow$ El proximo multiplo de p sera cuando $r=k$ ya que $N_{k}$ es el primer multiplo de $p$.$\Rightarrow$ Todos los numeros en la secuencia que son multiplos de $p$ por induccion son de la forma $N_{km}$ m entero positivo. Ahora si nos tomamos $N_{q}$ y $N_{r}$ con $q$ y $r$ primos y $q<r$ $\Rightarrow$ veremos que si un primo $p$ divide a $N_{q}$ y a $N_{r}$ tendremos que si $N_{q}$ tendra que ser el primer num. en la secuencia que sea multiplo de p, Ya que si no entonces existe $N_{x}$ tal que p lo divide, y por lo que demostramos ahorita $x$ divide a $q$ pero q es un primo entonces $x=1$ pero p no puede dividir a $N_{1}$. Entonces efectivamente $N_{q}$ es el primer numero en la secuencia. Ahora por lo que demostramos anteriormente $q$ debe dividir a $r$ pero es contradiccion ya que ambos son primos diferentes.$\Rightarrow (N_{q},N_{r})=1$ y $\Rightarrow$ podemos tomarnos todos los $N_{n}$ tal que n sea primo y seran primos relativos 2 a 2. FIN.

Flavio dijo...

Sean los numeros de la secuencia a_1, a_2,...
Primero veamos que a_d|a_n si y solo si
d|n.
si d|n entonces n=dk para un entero k entonces
a_d | a_d + a_d*10^d + a_d*10^2d + ... + a_d*10^((k-1)*d) = a_n
Luego si a_d|a_n y n=dk+r con 0<=ra_r entonces a_r debe ser 0
y r debe ser 0.
Ahora probare que a_(b_1), a_(b_2), ...
es una subsecuencia de primos relativos por parejas si y solo si
b_1, b_2, ... es una secuencia de primos relativos por parejas.
supongamos que la subsecuencia de a's si cumple, y las b's no
entonces hay dos b_i y b_j tales que d=(b_i,b_j)>1 entonces
a_d>1 y a_d|a_(b_i) y a_d|a_(b_j) entonces no son primos relativos
lo cual es contradiccion. Entonces si las a's cumplen las b's
cumplen.
Ahora si las b's cumplen, tomemos cualesquiera b_i,b_j entonces
por bezout existen enteros x,y ( aqui tomaremos ambos positivos por comodidad)
tales que x*b_i - y*b_j=1
entonces si d= (a_(b_i),a_(b_j))
entonces a_(b_i)|a_(x*b_i) y a_(b_j)|a_(y*b_j)
entonces d divide a ambos numeros, sea s=x*b_i entonces
s-1=y*b_j
luego d|a_s y d|a_(s-1) entonces d|10*a_(s-1)= a_s -1
entonces d|a_s y d|a_s -1
entonces d=1. Entonces las a's son primos relativos por parejas.
Entonces para resolver el problema solo hay que encontrar unas
b's que cumplan, y basta tomar la secuencia de primos, ya que
son primos relativos por parejas.

Georges dijo...

Vamos a hacerlo por inducción, para esto vamos a ver que si tenemos k números que son primos relativos por parejas siempre podemos agregar otro que sea primo relativo a todos los demas.
Llamemos a nuestra subsecuencia a_1, a_2,..., a_k.
a_1 va a ser igual a 111111=111x7x13x11.
Ahora para construir a_k+1 primero vamos a fijarnos en todos los primos que dividan a algun a_i con i<k+1. Sean p_1, p_2,..., p_r esos primos, entonces vamos a definir a a_(k+1) como a_(k+1)=((10^x)-1)/9. Donde x=(p_1-1)(p_2-1)..((p_r)-1)+1.
Primero vamos a ver que 3 no divide a a_(k+1) eso pasa por que como 7 divide a a_1 entonces en los (p_i)-1 aparece 6=2x3 por lo tanto a_(k+1)=((10^(3k+1)-1)/9 y este numero va a ser de la forma 111..1111 con 3k+1 unos, por lo tanto va a ser congruente con 1 mod 3 y por lo tanto 3 no lo divide.
Ahora vamos a ver que cualquiero otro p_i distinto de 3 no puede dividir a a_(k+1), esto pasa por que por el pequeño teorema de fermat vamos a tener que a_(k+1) es congruente con 9 mod p_i y esto es congruente con 0 si y solo si p_i= 3 pero eso no puede ser por que estamos suponiendo que p_i es distinto de 3.
Por lo tanto queda completa la inducción y entonces haciendo esto podemos llegar a una infinidad de repunits (11..11) primos relativos por parejas. FIN

DANIELIMO dijo...

a.1 = 1111...(a digitos uno).
es facil ver que (a.1) divide a(ak.1)(10^x) para k,x natural, aplicando esto es podemos ver que({ak+b}.1 , k.1)=(b.1,k.1) y repitiendo el proceso (como el algoritmo de euclides) podemos ver que (a.1,b.1)=(a,b).1 por lo que si tomamos la sucesion p.1 para infinitos primos p, cumple.

Publicar un comentario