domingo, 1 de abril de 2012
Problema del Viernes 30
Demuestre sin usar el Teorema de Dirichlet que si $(a,b)=1$, entonces existen una infinidad de enteros $k$ tales que $(ak+b,n)=1$ para todo $n$ natural.
Suscribirse a:
Comentarios de la entrada (Atom)
12 comentarios:
Demostraremos que para n primo se cumple, entonces tendremos que k debe ser congruente a algún módulo mod n, entonces por el teorema chino del residuo también tendremos el resultado para n un entero no divisible por ningún cuadrado (o sea, $n=p_1*p_2*...*p_m$ con $p_i \neq p_j$), pero entonces como si $n'=p_1^{a_1}*...*p_m^{a_m}$, $(c,n)=1 \Leftrightarrow (c,n')=1$, y entonces tendremos el resultado $\forall n \in \mathbb{N}$. Ahora, supongamos $n=p \in \mathbb{P}$. Tenemos que si c no es congruente a $\frac{-a}{b} (mod p)$, entonces si $k \equiv c (mod p)$, $p$ no dividirá a $ak+b \Rightarrow (n,ak+b)=1$. Entonces, si $k \equiv c (mod p)$, k cumple y como hay infinitos k, acabo.
Quod erat demonstrandum. $\clubsuit$
Perdón, en donde dice: "pero entonces como si n, (c,n)=1...$ debería decir "pero entonces como si $n_1=p_1^{a_1}*...*p_m^{a_m}$, $(c,n)=1\Leftrightarrow (c,n_1)=1$, entonces tendremos ...$.
Perdón, en donde dice: "pero entonces como si n, (c,n)=1...$ debería decir "pero entonces como si $n_1=p_1^{a_1}*...*p_m^{a_m}$, $(c,n)=1\Leftrightarrow (c,n_1)=1$, entonces tendremos ...".
Perdón, en donde dice: "pero entonces como si n, (c,n)=1..." debería decir "pero entonces como si $n_1=p_1^{a_1}*...*p_m^{a_m}$, $(c,n)=1\Leftrightarrow (c,n_1)=1$, entonces tendremos ...".
Mi solución es escencialmente la misma que la de Juan, y esque sí, si se ocurre la idea de "ajustar" el $k$ primo por primo (la cual es algo standard) ya el problema se vuelve muy fácil.
Queremos ver que la ecuación $a+kb=r$ tiene solución para $(r,n)=1$, lo cual es equivalente por teorema chino del residuo a que $a+kb=r$ tenga solución con $(r,p^a)=1$ para todo $p^a|n$, lo cual es equivalente a que exista un $k$ tal que $a+bk$ no es múltiplo de $p$, ahora, si $p|a+kb$ y $p|a+(k+1)b$ entonces $p|b$ y como $(a,b)=1$ entonces $(p,a)=1$ entonces $p$ no divide a $a+kb$ lo cual es una contradicción, entonces no divide a $a+kb$ o $a+(k+1)b$, con lo cual concluimos el problema.
Demostraremos los siguientes puntos:
-Si $(a,b)=1$ y un primo $p$ divide a $at+b$ para algún $t$, entonces $p|ak+b\Leftrightarrow k=px+t$ para algún entero $x$.
El lado ``si'' es fácil, pues $p|a(px+t)+b\Leftrightarrow p|at+b$.
Para el lado ``sólo si'', supongamos que $p|at+b$ y $p|ak+b$, entonces $p|a(t-k)$. Si $p|a$, $p|at+b\Rightarrow p|b\Rightarrow p|(a,b)$, que es imposible pues $(a,b)=1$. Entonces, $p\nmid a\Rightarrow p|t-k$, de donde $t\equiv k$ (mod $p$), luego $k=px+t$ para algún entero $x$, como queríamos.
-Si ${x_{n}}$ y ${y_{n}}$ son sucesiones aritméticas con $x_{k}=ak+b$ y $y_{k}=ck+d$, con $a,b,c,d,k$ enteros y $(a,c)=1$, entonces ${x_{n}}$ y ${y_{n}}$ tienen infinitos términos en común.
Basta ver que módulo $c$, $a+b,2a+b,...,(c-1)a+b,ca+b$ es un sistema completo de residuos pues $(a,c)=1$, luego existe $k\in \mathbb{Z}_{c}$ con $ka+b\equiv d$ (mod $c$), luego $ak+b=cl+d$ para algún entero $l$ y $a(k+cm)+b=c(l+am)+d$ para todo entero $m$, y como podemos elegir $m$ de infinitas maneras, ${x_{n}}$ y ${y_{n}}$ tienen infinitos términos en común.
-Si $(a,b)=1$, existe una infinidad de enteros $k$ tales que $(ak+b,n)=1$ para todo $n$ natural.
Sea $n=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}...p_{s}^{\alpha_{s}}$ su factorización en primos. Tenemos que $(ak+b,n)>1$ si y sólo si $p_{i}|ak+b$ para algún $i\in {1,2,...,s}$. Entonces, $p_{i}|(ak+b,n)\Leftrightarrow p_{i}|ak+b$, y por la primera proposición esto ocurre si y sólo si $k=p_{i}x+t_{i}$, de donde $ak+b\equiv at_{i}+b$ (mod $p_{i}$).
Ahora, por el teorema chino del residuo existe $X$ (mod $p_{1}p_{2}...p_{k}$) tal que $X\equiv at_{i}+b$ (mod $p_{i}$) para todo $i=1,2,...,s$. Sea $X_{n}$ la sucesión aritmética con $X_{n}=np_{1}p_{2}...p_{k}+X$. Es evidente que hay infinitos $X_{n}$, y por la segunda proposición, $X_{n}$ y $a_{n}$ (donde $a_{k}=ak+b$) comparten infinitos elementos. Entonces, existen infinitos $r$ tal que $X_{r}=ak+b$ para algún $k$. Ahora, vemos que $X_{r}+a=a(k+1)+b$ cumple que $(X_{r}+a,n)=1$. En efecto, $X_{r}+a\equiv at_{i}+b+a$ (mod $p{i}$), que no es $at_{i}+b$ porque $p_{i}\nmid a$. Entonces, $p_{i}\nmid X_{r}+a$ para $i=1,2,..,k$, luego $(X_{r}+a,n)=1$. Como hay infinitos $X_{r}$, hay infinitos $X_{r}+a$, como queríamos.
Sea $n=\prod_{i=1}^{m}{p_{i}}\cdot \prod_{j=1}^{l}{q_{j}}$. De tal manera que si
$P=\left\{p_{1}, p_{2},\ldots, p_{m}\right\}$
$Q=\left\{q_{1}, q_{2},\ldots , q_{l}\right\}$
entonces los conjuntos $P$ y $Q$ son ajenos y además para todo $p_{i}$ se tiene que $p_{i}$ divide tanto a $a$ como a $n$ y para todo $q_{j}$ se tiene que $q_{j}$ no divide a $a$ pero si a $n$.
Ahora, veamos que $p_{i}$ no puede dividir a $ak+b$, pues $p_{i}$ divide a $ak$ y no divide a $b$, por lo que $p_{i}$ no divide a $ak+b$.
Veamos que es posible que $ak+b\equiv 0\pmod{q_{j}}$ pues $a$ y $q_{j}$ son primos relativos, y existe un inverso multiplicativo de $a$ en módulo $q_{j}$. Entonces a este inverso lo multiplicamos por $-b$, y el resultado es, digamos, $c_{j}$ entonces tendremos que
$ac_{j} \equiv -b\pmod{q_{j}}$
$ac_{j}+b\equiv ak+b\equiv 0\pmod{q_{j}}$
Entonces, tomamos el sistema de congruencias
$k\equiv c_{j}\pmod{q_{j}}$
y denominaremos a $C$ como su solución, que sabemos que existe y es única por el Teorema Chino del Residuo, pues todos los $q_{j}$ son primos distintos. Entonces tenemos que para todo $q_{j}$, se tiene que
$q_{j}|aC+b$
y entonces, tendremos que ningún $q_{j}$ dividirá a $a\left(C+1\right)+b$ pues si lo hiciera, tenemos que $q_{j}$ divide a $a$ lo cual es una contradicción. Entonces tenemos que
$\left(a\left(C+1\right)+b, n\right)=1.
Veamos que $a\left(C+1\right)+b\equiv a\left(C+1+nx\right)+b\pmod{n}$ con $x$ entero, por lo que
$\left(a\left(C+1+nx\right)+b, n\right)=1$
y acabamos.
Sea $n=\prod_{i=1}^{m}{p_{i}}\cdot \prod_{j=1}^{l}{q_{j}}$. De tal manera que si
$P=\left\{p_{1}, p_{2},\ldots, p_{m}\right\}$
$Q=\left\{q_{1}, q_{2},\ldots , q_{l}\right\}$
entonces los conjuntos $P$ y $Q$ son ajenos y además para todo $p_{i}$ se tiene que $p_{i}$ divide tanto a $a$ como a $n$ y para todo $q_{j}$ se tiene que $q_{j}$ no divide a $a$ pero si a $n$.
Ahora, veamos que $p_{i}$ no puede dividir a $ak+b$, pues $p_{i}$ divide a $ak$ y no divide a $b$, por lo que $p_{i}$ no divide a $ak+b$.
Veamos que es posible que $ak+b\equiv 0\pmod{q_{j}}$ pues $a$ y $q_{j}$ son primos relativos, y existe un inverso multiplicativo de $a$ en módulo $q_{j}$. Entonces a este inverso lo multiplicamos por $-b$, y el resultado es, digamos, $c_{j}$ entonces tendremos que
$ac_{j} \equiv -b\pmod{q_{j}}$
$ac_{j}+b\equiv ak+b\equiv 0\pmod{q_{j}}$
Entonces, tomamos el sistema de congruencias
$k\equiv c_{j}\pmod{q_{j}}$
y denominaremos a $C$ como su solución, que sabemos que existe y es única por el Teorema Chino del Residuo, pues todos los $q_{j}$ son primos distintos. Entonces tenemos que para todo $q_{j}$, se tiene que
$q_{j}|aC+b$
y entonces, tendremos que ningún $q_{j}$ dividirá a $a\left(C+1\right)+b$ pues si lo hiciera, tenemos que $q_{j}$ divide a $a$ lo cual es una contradicción. Entonces tenemos que
$\left(a\left(C+1\right)+b, n\right)=1$.
Veamos que $a\left(C+1\right)+b\equiv a\left(C+1+nx\right)+b\pmod{n}$ con $x$ entero, por lo que
$\left(a\left(C+1+nx\right)+b, n\right)=1$
y acabamos.
Sea $p$ un primo que divide a $n$ y sea $m$ la maxima potencia de $p$ que lo haga. Si $(a,p)=1$ entonces es conocido que existe solución para $k$ de $ak \equiv -b+1\pmod{p}$ y entonces $ak+b$ sería primo relativo con $p^n$, si $(a,p)=p$ entonces $(b,p)=1$ pues $(a,b)=1$, entonces $ak+b$ es primo relativo con $p^n$ para toda $k$.Entonces por haciendo lo mismo para cada uno de los primos que dividen a $n$ por el teorema chino del residuo tenemos una $k$ tal que $ak+b$ es primo relativo para cada divisor de $n$.
Bueno al final existe $k$ módulo $n$, por eso hay infinitas $k$ que lo cumplen (todos los congruentes con $k$ mod $n$) y todas las $p^n$ son $p^m$
Según yo, la idea ya la pusieron muchas veces arriba, pero aquí va. Sea $n=\prod_{i=1}^{k}p_{i}^{\alpha_{i}}$ entonces buscaremos que para todo $i$, $p_{i}$ no divida a $a+kb$. supongamos que sí divide a $a+kb$, si también divide a $a+(k+1)b$ entonces divide a $b$ y entonces deberá dividir a $a$ pero en ese caso, $(a,b)\geq p_{i}\textgreater 1$ lo cual no es cierto, así que al menos uno no es cierto, digamos que es $x_{i}$.
Ahora, como $(a+x_{i}b,p_{i})=1$ entonces $a+x_{i}b,p_{i}^{\alpha_{i}})=1$ así que usando el Teorema Chino del residuo con $a+x_{i}b\equiv r_{i}\pmod{p_{i}^{\alpha_{i}}}$ veremos que existe al menos una solución $m$ para $n$. Es decir que $(a+mb,n)=1$ pero entonces $(a+(cn+m)b,n)=1$ para todo $c$ entero, lo que demuestra que hay una infinidad.
Publicar un comentario