Autor Tema: Máximo común divisor

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

08 Abril, 2015, 04:46 pm
Leído 3520 veces

Héctor Manuel

  • Lathi
  • Mensajes: 3,631
  • Karma: +0/-0
  • Sexo: Masculino
Los problemas son:
1) Sea \( n\in\mathbb{N} \). Entonces \( (n!+1,(n+1)!+1)=1 \).

Demostración

Usaremos el siguiente lema: "Si \( p \) es primo y \( a,b\in\mathbb{N} \) son tales que \( p|ab \), entonces \( p|a \) o bien \( p|b \)".

De esta forma, supongamos que \( (n!+1,(n+1)!+1)\neq 1 \), de modo que este mcd debe ser mayor que 1. Luego, por el Teorema Fundamental, existe un primo \( p \) tal que \( p|(n!+1,(n+1)!+1) \).

Así, como \( p|n!+1 \) y \( p|(n+1)!+1 \), entonces \( p|(n+1)!+1-(n!+1)=n!n \). Se concluye del lema anterior que, al ser \( p \) primo, entonces \( p|n! \) o \( p|n \). Veamos que necesariamente se cumple \( p|n! \). En efecto, si \( p|n! \) ya, y si \( p|n \), inferimos que \( p\le n \), resultando en \( p|n! \) por definición de factorial.

Luego, debido a que \( p|n! \) y \( p|n!+1 \), se ha de cumplir que \( p|n!+1-n!=1 \), por lo cual \( p=1 \). Pero \( p \) es primo. Esta contradicción muestra que \( (n!+1,(n+1)!+1)=1 \) \( \quad \).







2) Si \( a,b,c \) y \( d \) son naturales tales que \( ad-bc|a \) y \( ad-bc|c \), entonces para cualquier \( n\in\mathbb{N} \) se tiene que \( (an+b,cn+d)=1 \).

Demostración

Sea \( x=(an+b,cn+d) \).

Como \( x|an+b \), entonces \( x|c(an+b)=acn+bc \). Como \( x|cn+d \), entonces \( x|a(cn+d)=acn+ad \). Luego, \( x|acn+ad-(acn+bc)=ad-bc \).

Por transitividad, debido a que \( ad-bc|a \) y \( ad-bc|c \) se sigue que \( x|a \) y \( x|c \), y por cumplirse que \( x|an+b \) y \( x|cn+d \), nos damos cuenta de que \( x|b \) y \( x|d \).

Dado lo anterior, podemos escribir \( a=xa_1 \), \( b=xb_1 \), \( c=xc_1 \) y \( d=xd_1 \) para ciertos \( a_1,b_1,c_1,d_1 \).

Luego, \( ad-bc=x^2(a_1d_1-b_1c_1)|a=xa_1 \), de donde \( x|a_1 \), y análogamente, \( x|c_1 \), de modo que \( a_1=xa_2 \) y \( c_1=xc_2 \), por lo cual \( a=x^2a_2 \) y \( c=x^2c_2 \).

Pero esto último implica \( ad-bc=x^3(a_2d_1-b_1c_2)|a=x^2a_2 \), de donde \( x|a_2 \) y análogamente, \( x|c_2 \), de modo que \( a_2=xa_3 \) y \( c_2=xc_3 \), por lo cual \( a=x^3a_3 \) y \( c=x^3c_3 \).

Nuevamente, esto último implica \( ad-bc=x^4(a_3d_1-b_1c_3)|a=x^3a_3 \), de donde \( x|a_3 \) y análogamente, \( x|c_3 \), de modo que \( a_3=xa_4 \) y \( c_3=xc_4 \), por lo cual \( a=x^4a_4 \) y \( c=x^4c_4 \).

Como puede verse, podemos continuar con este proceso infinitamente, de modo que \( x,x^2,x^3,x^4,... \) son divisores de \( a \) (y de \( c \)). Así, si \( x\neq 1 \) entonces estas potencias de \( x \) son todas distintas, así que \( a \) tendría infinitos divisores, por lo cual necesariamente ha de ser \( x=1 \), lo que concluye la prueba.\( \quad \)

Saludos, Héctor.

08 Abril, 2015, 09:33 pm
Respuesta #1

Juan Pablo Sancho

  • Moderador Global
  • Mensajes: 4,852
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
\(  {\red Editado } \) perdón Hector había puesto una burrada


Spoiler
Para el primero:

\( \displaystyle d = (n!+1,(n+1)!+1)  \) entonces \(  d  \) divide a cualquier combinación lineal de los dos.

\(  d|[((n+1)!+1)-(n!+1)] = n!  \) entonces \(  d|(n!,n!+1)  \) obtenemos \(  d=1  \)
[cerrar]

Ni sacar factor común.

\(  {\red Editado } \)

Un segundo intento para el primero:

\(  d = (n!+1,(n+1)!+1)  \) entonces \(  d|[p(n!+1) + s \cdot ((n+1)!+1)]  \) para todo \(  p,s \in \mathbb{Z}  \)

\( \displaystyle p(n!+1) + s \cdot ((n+1)!+1) = (p+s) \cdot (n!+1) + n! \cdot s \cdot n  \)

Como \(  d|[(p+s) \cdot (n!+1) + n! \cdot s \cdot n] \ \ \ \  \)  y   \( \ \ \ d|(n!+1)  \) para todo \(  p,s \in \mathbb{Z}  \) tenemos que:

\(  d| n! \cdot s \cdot n  \) tomo \(  s = (n-1)!  \) y queda que \(  d| n! \cdot n!  \)

Uso el hecho de que:

\( (a,b)=(a,c) = 1  \) entonces \(  (a,bc)=1  \) y nos queda \(  d|(n!+1,n! \cdot n!) = 1  \).

Tampoco acorté mucho el trabajo.

08 Abril, 2015, 11:11 pm
Respuesta #2

Héctor Manuel

  • Lathi
  • Mensajes: 3,631
  • Karma: +0/-0
  • Sexo: Masculino
Hola Juan Pablo. Te comento:
\(  {\red Editado } \) perdón Hector había puesto una burrada

Tampoco acorté mucho el trabajo.

Puse el hilo en discusiones semi-públicas pensando no sólo que lo viera la persona que me pidió ayuda (la cual es ajena al Foro), sino precisamente para que quienquiera que se anime pueda participar con las ideas que pueda... lo importante es ver si podemos mejorar las demostraciones, así que no te preocupes.

Gracias.

Saludos, Héctor.