(Este es el problema que Fer no pudo poner en una nueva entrada)
Probar que la secuencia 1, 11, 111,... contiene una subsecuencia de primos relativos por parejas.
jueves, 12 de agosto de 2010
Problema del día 11
Probar que la secuencia 1, 11, 111,... contiene una subsecuencia de primos relativos por parejas.
Suscribirse a:
Comentarios de la entrada (Atom)
8 comentarios:
Ya lo habia puesto!!... pero bueno.. lo ponemos 2 veces para que todos lo vean jaja
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?)
Donde dice LAtex failed iba $c=[k_{1}, k_2,..., k_{n}]$
jajaja, cuando se me ocurrió ponerlo todavía no estaba tu entrada
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.
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.
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
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