Autor Tema: Sobre congruencias

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

18 Diciembre, 2018, 05:55 pm
Leído 765 veces

Adrianaprendiendo

  • $$\pi$$
  • Mensajes: 21
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Teorema

Dados m numeros enteros sucesivos

a, a+1, a+2,...a+m-1

Y dado otro numero entero A, uno y solo uno de estos sera congruente a A segun el modulo m

Si \( \displaystyle\frac{a-A}{m} \) es un entero, entonces a\equiv{A}, Si \( \displaystyle\frac{a-A}{m} \) es una fraccion, sea proximo mayor entero positivo( y si es negativo, el proximo menor, sin considerar signo).

A+K.m, que estara entre a y a+m, sera el numero buscado. Es evidente que todos los cocientes \( \displaystyle\frac{a-A}{m} \), \( \displaystyle\frac{a+1-A}{m} \), y \( \displaystyle\frac{a+2-A}{m} \), etc seran ubicados entre k-1 y k+1, por lo que solo uno de ellos puede ser entero.

Yo trate de encontrar un numero entero con a=2( pensando que a tendria que ser menor que m necesariamente porque asi lo dice al principio, dados m numeros...), A=8 y m=5

\( \displaystyle\frac{2-8}{5} \)= -6/5, el proximo menor menor negativo es -2

A+K.m= 8+(-10)=-2 que no esta entre a y a+m. ¿Que esta mal en la forma en que trate de encontrar el numero congruente a A segun el modulo m?

19 Diciembre, 2018, 01:15 pm
Respuesta #1

Luis Fuentes

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

Dados m numeros enteros sucesivos

a, a+1, a+2,...a+m-1

Y dado otro numero entero A, uno y solo uno de estos sera congruente a A segun el modulo m

Si \( \displaystyle\frac{a-A}{m} \) es un entero, entonces a\equiv{A}, Si \( \displaystyle\frac{a-A}{m} \) es una fraccion, sea proximo mayor entero positivo( y si es negativo, el proximo menor, sin considerar signo).

A+K.m, que estara entre a y a+m, sera el numero buscado. Es evidente que todos los cocientes \( \displaystyle\frac{a-A}{m} \), \( \displaystyle\frac{a+1-A}{m} \), y \( \displaystyle\frac{a+2-A}{m} \), etc seran ubicados entre k-1 y k+1, por lo que solo uno de ellos puede ser entero.

Yo trate de encontrar un numero entero con a=2( pensando que a tendria que ser menor que m necesariamente porque asi lo dice al principio, dados m numeros...), A=8 y m=5

\( \displaystyle\frac{2-8}{5} \)= -6/5, el proximo menor menor negativo es -2

A+K.m= 8+(-10)=-2 que no esta entre a y a+m. ¿Que esta mal en la forma en que trate de encontrar el numero congruente a A segun el modulo m?

siguiendo tu razonamiento, la cuestión es que si \( \dfrac{a-A}{m} \) es fracción lo que tienes que hacer es considerar el menor entero (da igual el signo) mayor que \( \dfrac{a-A}{m} \).

En tu ejemplo \( \displaystyle\frac{2-8}{5}=-6/5 \) y el menor entero mayor que ese valor es \( -1 \).

\( \dfrac{a-A+k}{m}=-1 \)

\( a+k=A-m=8-5=3 \)

\( 3 \) está en entre \( 2 \) y \( 2+5-1 \) y es congruente con \( 8 \) módulo \( 5 \).

Saludos.

20 Diciembre, 2018, 03:22 am
Respuesta #2

Adrianaprendiendo

  • $$\pi$$
  • Mensajes: 21
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Perdon. La cuestion es que si es una fraccion, sea k el proximo mayor negativo (eso salio mal al escribirlo al principio de la publicacion, perdon)

Y si a+k= A+K.m entonces

2+(-1)= 8-5=3

Y tampoco entiendo la parte que dice que todos los cocientes estan ubicados entre k-1 y k+1; por lo que solo uno de ellos puede ser entero.
Si k=-1 entonces su cociente sera o 0 o -2

Y pregunto, este ejercicio es asi o lo faltaria una letra para simplicar todo, osea, que esto podria estar mejor formulado, no?

20 Diciembre, 2018, 11:11 am
Respuesta #3

Luis Fuentes

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

Perdon. La cuestion es que si es una fraccion, sea k el proximo mayor negativo (eso salio mal al escribirlo al principio de la publicacion, perdon)

Y si a+k= A+K.m entonces

2+(-1)= 8-5=3

¿Cuál es la pregunta o la duda ahí?.

Citar
Y tampoco entiendo la parte que dice que todos los cocientes estan ubicados entre k-1 y k+1; por lo que solo uno de ellos puede ser entero.
Si k=-1 entonces su cociente sera o 0 o -2

Lo que te dicen es que \( k \) es el menor entero mayor que \( \dfrac{a-A}{m} \) (que estamos suponiendo que no es entero). Eso significa que:

\( \dfrac{a-A}{m}<k<\dfrac{a-A}{m}+1 \)

Equivalentemente quitando denominadores y sumando \( A \) que:

\( a<A+mk<a+m \) (*)

Por tanto \( A+mk \) es un número comprendido entre \( a+1 \) y \( a+m-1 \) ambos incluidos.

Además de (*),

\( A+m(k+1)=A+mk+m>a+m \)
\( A+m(k-1)=A+mk-m<a \)

Por tanto todos los cocientes \( \dfrac{a-A+s}{m} \) con \( 1\leq s<m-1 \) están entre \( k-1 \) y \( k+1 \).

Citar
Y pregunto, este ejercicio es asi o lo faltaria una letra para simplicar todo, osea, que esto podria estar mejor formulado, no?

No se muy bien que decirte. A mi no me gusta especialmente como está explicado.

Yo lo haría así. Dado \( A \) se tiene que por el algoritmo de la división \( A-a=cm+r \) donde \( 0\leq r<m \) y por tanto:

\( A=a+r \) mod \( m \) con \( 0\leq r<m \)

Además si hubiese otro \( r' \) con \( 0\leq r'<m \) tal que \( A=a+r' \) mod \( m \) restando tendriamos:

\( r-r'=0 \) mod \( m \)

es decir:

\( r-r'=km\quad \Rightarrow{}\quad |r-r'|=|k|m \)

Pero como \( 0\leq r,r'<m \) se tiene que \( |r-r'|<m \) y por tanto \( |k|m<m \) y \( |k|=0 \). Es decir \( r=r' \) y de ahí la unicidad.

Saludos.