Autor Tema: Prueba: si \(\;m,n\;\) coprimos entonces \(\;\exists\;s_0,t_0|1=ms_0+nt_0\)

0 Usuarios y 1 Visitante están viendo este tema.

01 Enero, 2017, 12:28 pm
Leído 2436 veces

Buscón

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,708
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino

Si    \( m \)    y    \( n \)    son enteros primos entre sí existen dos enteros    \( s_0 \)    y    \( t_0 \)    tales que


\( \bf 1=ms_0+nt_0 \).


Demuéstrelo.


01 Enero, 2017, 02:26 pm
Respuesta #1

robinlambada

  • Moderador Global
  • Mensajes: 3,804
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino

Si    \( m \)    y    \( n \)    son enteros primos entre sí existen dos enteros    \( s_0 \)    y    \( t_0 \)    tales que


\( \bf 1=ms_0+nt_0 \).

Demuéstrelo.

Hola, Feliz año.

Se trata de la
Identidad o lema de Bezout.

Se puede demostrar usando ideales, que no domino.
Tambien se demuestra usando el conjunto de combinaciones lineales de m y n , mayores que cero. Llama d al mínimo del conjunto y divide m entre ď con resto r. Por ser r combinación lineal de m y d pertenecientes al conjunto r tambien lo es, pero por ser menor que d(mínimo) , debe ser r=0. Por ello d divide a m. Por el mismo razonamiento tambien divide a n. Solo falta ver que d es el MCD(n,m). Lo puedes hacer por reducción al absurdo.

Disculpa lo poco explicito y detallado. Pero escribo desde el movil.
Debe de haber enlaces a la demostración en internet.
Saludos.
Envejecer es como escalar una gran montaña: mientras se sube las fuerzas disminuyen, pero la mirada es más libre, la vista más amplia y serena.

La verdadera juventud una vez alcanzada, nunca se pierde.

01 Enero, 2017, 05:44 pm
Respuesta #2

feriva

  • $$\Large \color{#a53f54}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 9,636
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino

Si    \( m \)    y    \( n \)    son enteros primos entre sí existen dos enteros    \( s_0 \)    y    \( t_0 \)    tales que


\( \bf 1=ms_0+nt_0 \).


Demuéstrelo.


La idea para demostrarlo creo que podría ser ésta si no me equivoco en nada:

Spoiler

Considera el conjunto de los números de la forma \( ms+nt \), donde siendo “s” y “t” enteros y “ponen el signo”, podemos considerar sin pérdida de generalidad “n” y ”m” naturales.

Este conjunto existe de antemano porque no estamos poniendo condiciones en cuanto a que sea 1 ni nada.

Llamemos al mínimo de ese conjunto “k” siendo éste \( k=s_{0}m+t_{0}n
  \); si demostramos que dicho mínimo es divisor de “m” y “n”, entonces “k” será 1 necesariamente, por ser ambos coprimos según lo dice el problema, y queda demostrado.

Para hacer lo dicho hay pues que demostrar que “k” divide a “m” y a “n”.

Por el algoritmo de la división tenemos:

\( m=qk+r
  \) donde el resto es siempre menor que “K”, trivialmente. (había puesto "q", y precisamente el argumento es éste, que "r" es menor que el mínimo "k"; todo por ir cambiando letras para adaptarlo)

Sustituimos ese “k” por la expresión \( s_{0}n+t_{0}n
  \)

\( m=q(s_{0}m+t_{0}n)+r
  \)

despejamos “r”

\( r=m-q(s_{0}m+t_{0}n)
  \)

aplicamos la distributiva

\( r=m-qs_{0}m+qt_{0}n
  \)

sacamos factor común m

\( r=m(1-qs_{0})+qt_{0}n
  \)

Entonces “r” es un número que resulta que pertenece al conjunto de los números que habíamos dicho, tiene la forma

\( ms+nt \); y además es menor que el mínimo.

El resto siempre es positivo y entonces ese polinomio da un valor positivo.




el argumento  ya está, basta con ver que "r<k" con lo que no puede ser más que el cero al ser "k" el mínimo.



el resto es cero y, por tanto, la división es exacta; es decir, se ha demostrado que “k” divide a “m”.

Basta demostrar exactamente de la misma manera que “k” divide también a “n”, con lo que se demuestra que es divisor de ambos y, al ser comprimos, sólo puede pasar que “k=1”

[cerrar]

01 Enero, 2017, 08:42 pm
Respuesta #3

feriva

  • $$\Large \color{#a53f54}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 9,636
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Lo que te puse en el spoiler no es mío, lo aprendí hace años de este vídeo (alguna cosa no la recordaba bien del todo


Pero esta idea sí es mía, se me ha ocurrido ahora:

EDITADO

Spoiler



Sin perder generalidad \( m,n\in\mathbb{N};s,t  \, \in \mathbb{Z}
  \)

\( 1=ms+nt
  \)

\( 1-ms=nt
  \)

también sin perder generalidad, si \( t<0 \) entonces \( s>0 \); y con \( t=-k \) podemos hacer:

\( 1-ms=n(-k)
  \)

multiplicamos por -1

\( -1(1-ms)=-1(-nk)
  \)

\( ms-1=nk
  \)

\( ms=b\Rightarrow nk=b-1
  \)

Es decir, que se puede traducir informalmente por esto: “dados dos enteros “n” y “m” existen otros dos tales que al multiplicarlos por ellos obtenemos dos números consecutivos múltiplos de “n” y “m” respectivamente”; en cristiano, que existen múltiplos “n” y “m” que van seguidos.

Encontraremos los múltiplos de “n” multiplicando desde 1 por los demás naturales.

La diferencia entre dos mútliplos consecutivos de “n” será “n” o “-n”: \( 2n-n=n \), \( 3n-2n=n \)... etc. igualmente para “m”

Del mismo modo, el múltiplo siguiente (o anterior análogamente) de \( n+1 \) será \( 2n+2=2(n+1) \) y así sucesivamente; lo mismo para “m+1”.

Si tomamos “m” y su siguiente, a partir de ahí encontraremos pares de números consecutivos tales que

CORREGIDO

\( (m),(m+1);\quad(2m),(2m+1);\quad(3m),(3m+1)...=
  \)

\( (m),(m+1);\quad(2m),({\color{blue}1}m+[m+1]);\quad(3m),({\color{blue}2} \cdot m+[m+1])...(am),(({\color{blue}a-1})m+[m+1])
  \)

Ese último término es

\( am-m+m+1=am+1
  \)

Y el coeficiente “azul” va recorriendo todos los números naturales, y, por tanto, los distintos \( am+1
  \) darán distintos restos al ser divididos entre “n” y uno de esos restos ha de ser forzosamente cero.

(este tipo de argumento supongo que no te valdrá, te pedirán una demostración como la otra)

[cerrar]

Saludos.

02 Enero, 2017, 02:26 pm
Respuesta #4

Buscón

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,708
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
La verdad es que es fácil ver que    \( \min(ms+nt)=1 \),    \( ms+nt>o \)    \( m,n,s,t\in{\mathbb{Z}} \)

\begin{align*}&a\cdot{a^1}+0\cdot{b}&=&\;1\\

&a\cdot{a^{-1}}+b\cdot{b^{-1}}&=&\;2\\

&a\cdot{a^{-1}}+2b\cdot{b^{-1}}&=&\;3\\

& &...\\
&a\cdot{a^{-1}}+nb\cdot{b^{-1}}&=&\;n+1\\
& &...\end{align*}

Se trata del conjunto     \( \mathbb{N} \)    y    \( \min(\mathbb{N})=1\in{\mathbb{N}} \),    así que, tienen que existir esos    \( s_0,t_0 \).


Un saludo.


02 Enero, 2017, 03:26 pm
Respuesta #5

feriva

  • $$\Large \color{#a53f54}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 9,636
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
La verdad es que es fácil ver que    \( \min(ms+nt)=1 \),    \( ms+nt>o \)    \( m,n,s,t\in{\mathbb{Z}} \)

\begin{align*}&a\cdot{a^1}+0\cdot{b}&=&\;1\\

&a\cdot{a^{-1}}+b\cdot{b^{-1}}&=&\;2\\

&a\cdot{a^{-1}}+2b\cdot{b^{-1}}&=&\;3\\

& &...\\
&a\cdot{a^{-1}}+nb\cdot{b^{-1}}&=&\;n+1\\
& &...\end{align*}

Se trata del conjunto     \( \mathbb{N} \)    y    \( \min(\mathbb{N})=1\in{\mathbb{N}} \),    así que, tienen que existir esos    \( s_0,t_0 \).





Eso no lo entiendo muy bien, pero espero a que lo mire un moderador.

Spoiler


En caso de que no sean coprimos es imposible que vayan seguidos, estarán siempre a la distancia de su mcd o un múltiplo de su mcd; por ejemplo, 6 y 14, mcd=2 y 14-6=8, que es múltiplo del mcd; y es bastante trivial de ver.


[cerrar]

Un saludo.

02 Enero, 2017, 04:50 pm
Respuesta #6

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 49,008
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

La verdad es que es fácil ver que    \( \min(ms+nt)=1 \),    \( ms+nt>o \)    \( m,n,s,t\in{\mathbb{Z}} \)

\begin{align*}&a\cdot{a^1}+0\cdot{b}&=&\;1\\

&a\cdot{a^{-1}}+b\cdot{b^{-1}}&=&\;2\\

&a\cdot{a^{-1}}+2b\cdot{b^{-1}}&=&\;3\\

& &...\\
&a\cdot{a^{-1}}+nb\cdot{b^{-1}}&=&\;n+1\\
& &...\end{align*}

Se trata del conjunto     \( \mathbb{N} \)    y    \( \min(\mathbb{N})=1\in{\mathbb{N}} \),    así que, tienen que existir esos    \( s_0,t_0 \).

Pero eso no vale: en general \( a^{-1} \) y \( b^{-1} \) NO serán números enteros.

Saludos.

03 Enero, 2017, 11:49 am
Respuesta #7

feriva

  • $$\Large \color{#a53f54}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 9,636
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Hola, Buscon. Te propongo este planteamiento, por si te gusta (yo lo tengo terminado, pero lo dejo sin terminar por si te apetece pensar en la resolución)

Spoiler


Sea “k” un múltiplo cualquiera de \( ms+tn
  \) pero no de \( (ms+tn)^{2}
  \); entonces existe un entero “g” tal que

\( \dfrac{km}{ms+tn}=g
  \)

(el porqué de por qué se toma que no sea cuadrado se verá luego; y es algo que existe y siempre podemos elegir).

\( km=gms+gtn\Rightarrow m|gtn
  \); o sea, “m” tiene que dividir a “gtn”; y si “t” y “n” son coprimos con m, “m” divide a “g”; y hacemos \( gtn=mqtn
  \) donde “q” es algún entero.

Entonces, sustituyendo y dividendo por “m”

*\( k=gs+qtn
  \)

Sustituyendo ahora por “k” arriba se tiene

\( \dfrac{mgs+mqtn}{ms+tn}=g
  \)

\( mgs+mqtn=mgs+tng
  \)

\( mq=g
  \)

luego

\( \dfrac{km}{ms+tn}=mq\Rightarrow\dfrac{k}{ms+tn}=q\Rightarrow ms+tn=\dfrac{k}{q}
  \)

\( ms+tn=\dfrac{k}{q}=1
  \) es la condición a demostrar; suponemos entonces, por reducción al absurdo, que \( k/q\neq1
  \); pero al menos ha de ser un entero, así que “q” divide a “k”: \(  k=qh
  \) con \( h\neq1;\, q=\dfrac{k}{h}
  \)

Tenemos que \( h=ms+nt
  \); y por lo dicho al principio “k” es múltiplo de “h” pero no de su cuadrado.

Si ahora volvemos a la expresión del asterisco y sustituimos “q” por “k/h”, llegamos a

\( k=gs+\dfrac{k}{h}tn
  \)

\( k-\dfrac{k}{h}tn=gs
  \)

\( kh-ktn=hgs
  \)

\( h(k-gs)=ktn
  \)

como “k” no divide a “h”, porque ocurre al contrario, es menor que “k”, entonces divide a \( (k-gs)
  \), lo que implica que “k” divida a “gs” y que “gs”, por tanto, sea mútliplo de “h” también (puesto que “k” lo es)...

[cerrar]

Añado el final

Spoiler

Si se sigue, volviendo a la expresión \( k=gs+\dfrac{k}{h}tn
  \) es casi inmediato demostrar que, entonces, según las condicones puestas, “tn” tiene que ser también múltiplo de “h”:

\( k \) lo es, \( gs \) lo es y \( k/h \) no lo es (por la elección del cuadrado que decía, ése es el quid de la demostración). Y, dado eso, “tn” tiene que ser divisible entre “h”.

Pero resulta que \( h=ms+tn
  \); luego “ms” también tiene que ser múltiplo de “h”, con lo que ambos sumandos tienen que tener de factor común a “h”.

Si dividimos entre “h” da igual a 1, no se puede dividir más, lo que implica que “h” es el “mcd” de “ms” y “nt”.

Si supones que “h” es factor común de “s” y “t” (puesto que de ellos no te dicen que tengan que ser coprimos) al dividir la ecuación por “h” tendrás

\( 1=m\dfrac{s}{h}+n\dfrac{t}{h}
  \)

y, si fuera posible tal división, aun así seguirían existiendo unos coeficientes tales que multiplicados por “m” y “n” la suma nos daría uno.

En definitiva, existen esos coeficientes para la igualdad dada siempre que “m” y “n” sean coprimos, pero no si no lo son; pues tendríamos \( \dfrac{1}{h}<1
  \) y no sería una suma de enteros.

*pero es una demostración muy aparatosa donde se empela hasta la saciedad el lema de Euclides, típica de aficionado a la Teoría de números, que es, como mucho, a lo que llego.

[cerrar]

Saludos.

03 Enero, 2017, 01:30 pm
Respuesta #8

Buscón

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,708
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Ciertamente, un desastre, ni son coprimos, ni son enteros los ejemplos que puse.

Se trata de usar que, tanto para    \( m \)    como para    \( n \)    existen    \( q,q',r,r'\in{\mathbb{Z}} \)    tales que


\( m=dq+r \),   \( 0\leq{r}<d \),    \( |m|>d \),   \( d\in{\mathbb{N}} \),


\( n=dq'+r' \),    \( 0\leq{r'}<d \),    \( |n|>d \),    \( d\in{\mathbb{N}} \).


Esto se puede probar utilizando la existencia del supremo y el teorema del buen orden de    N,   (propiedad arquimediana).

Se tiene que para los números reales     \( \displaystyle\frac{m}{d},\displaystyle\frac{n}{d} \)    existen    \( q,q'\in{\mathbb{Z}} \)    tales que


\( q\leq{\displaystyle\frac{m}{d}}<q+1 \),


\( q'\leq{\displaystyle\frac{n}{d}}<q'+1 \).


está probado por aquí:



pero sólo podría ser  \( m=dq,n=dq',r=r'=0 \)    si    \( d=1 \)    ya que, por hipótesis,    \( m \)    y    \( n \)    son

coprimos y    \( d \)    no puede ser    \( -1 \)    ya que    \( d\in{\mathbb{N}} \).


Ahora, por otro lado, resulta que,

Cita de: Quico Benítez.Tema 2. CONJUNTOS NUMÉRICOS.
...cosideremos el conjunto

\( S=\{ms+nt>0:\;\;\;s,t\in{\mathbb{Z}}\} \)

Es claro que    \( S\subset{\mathbb{N}} \),    así que tendrá un primer elemento, llamémosle    \( d \).    Como    \( d\in{S} \)    existirán    \( s_0 \)    y    \( t_0 \)    tales que    \( d=ms_0+nt_0 \).

continúa Quico Benítez con el siguiente desarrollo:

tenemos que


\( r=m-dq \),


sustituyendo,


\( r=m-(ms_0+nt_0)q \),


\( r=m-ms_0q-nt_0q \),


\( r=m(1-s_0q)-nt_0q \),


\( r=m(1-s_0q)+n(-t_0q) \),


con    \( 1-s_0q\in{\mathbb{Z}} \)    y    \( -t_0q\in{\mathbb{Z}} \),    lo que significa que


\( r=m-dq=m(\underbrace{1-s_0q}_{s})+n(\underbrace{-t_0q}_{t})>0 \),


\( m-dq>0 \),    luego,    \( m-dq\in{S} \),


pero también por hipótesis    \( 0\leq{m-dq}<d \)    que contradice la hipótesis     \( d=\min(S) \)    así que sólo puede ser que


\( m-dq=0 \),    y por consiguiente    \( m-dq\not\in{S} \),


con lo que


\( m=dq \),    esto es,    \( d \)    divide a    \( m \).


Procediendo de forma análoga obtenemos que    \( d \)    también divide a    \( n \)    y si son coprimos, de nuevo,sólo puede ser    \( d=1 \).

Precioso! Impresionante!

Pero no lo entiendo. ¿En base a que se fuerza que    \( d=\min(S) \)    y también    \( d \)    divisor de    \( m \)    y    \( n \)?


Un saludo.

03 Enero, 2017, 05:04 pm
Respuesta #9

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 49,008
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

No me quedan del todo claras las preguntas. Intentaré responder tal como las entiendo:

Pero no lo entiendo. ¿En base a que se fuerza que    \( d=\min(S) \) 

No sé que quieres decir con que se "fuerza" que \( d=\min(S) \). Tomamos \( d=\min(S) \) que sabemos que existe, porque \( S \) es un sobconjunto de los naturales no vacío.

Citar
  y también    \( d \)    divisor de    \( m \)   


Entonces se prueba que ese \( d \) es divisor de \( m \) con este argumento (en la parte que marqué en rojo es decisivo que \( d \) sea el mínimo):

Citar
tenemos que


\( r=m-dq \),


sustituyendo,


\( r=m-(ms_0+nt_0)q \),


\( r=m-ms_0q-nt_0q \),


\( r=m(1-s_0q)-nt_0q \),


\( r=m(1-s_0q)+n(-t_0q) \),


con    \( 1-s_0q\in{\mathbb{Z}} \)    y    \( -t_0q\in{\mathbb{Z}} \),    lo que significa que


\( r=m-dq=m(\underbrace{1-s_0q}_{s})+n(\underbrace{-t_0q}_{t})>0 \),


\( m-dq>0 \),    luego,    \( m-dq\in{S} \),


pero también por hipótesis    \( 0\leq{m-dq}<d \)    que contradice la hipótesis     \( d=\min(S) \)    así que sólo puede ser que


\( m-dq=0 \),    y por consiguiente    \( m-dq\not\in{S} \),


con lo que


\( m=dq \),    esto es,    \( d \)    divide a    \( m \).

Análogamente prueba que \( d \) divide a \( n \).

Entonces \( d \) divide a \( n \) y \( m \) y como son primos entres si, entonces necesariamente \( d=1 \).

Saludos.