Rincón Matemático
Matemática => Matemática Discreta y Algoritmos => Mensaje iniciado por: manooooh en 18 Octubre, 2019, 07:21 am
-
Hola!
Marcar la opción correcta y justificar. La ecuación de congruencia \[390x\equiv114\pmod{462}\] tiene (soluciones principales):
- Solución única.
- \( 2 \) soluciones.
- \( 6 \) soluciones.
- No tiene solución.
Creo que la respuesta es la (c).
En primer lugar verifiquemos si la ecuación dada posee o no solución, a través de la condición necesaria y suficiente:
Puesto que \( \gcd(390,462)=6 \) (a través del algoritmo de Euclides, son suficientes \( 5 \) iteraciones) y además \( 6\mid114 \) ya que \( 114=19\cdot6 \) luego existen \( 6 \) soluciones principales en \( \Bbb{Z}_{462} \). La (d) por tanto queda descartada.
Para descartar las otras podemos encontrar todas las soluciones principales de la ecuación. En primer lugar dividamos todo por \( 6 \) para trabajar más fácil: \[65x\equiv19\pmod{77}.\] Sabemos que una solución es \( x=65^{\varphi(77)-1}\cdot19 \), donde \( \varphi(\alpha) \) es la función de Euler.
Sabemos que \( \varphi(77)=77(1-1/7)(1-1/11)=60 \), de esta manera \( x=65^{59}\cdot19 \). Y a partir de aquí no supe cómo demostrar que \( 65^{59}\cdot19\equiv69\pmod{77} \).
Intenté usar el teorema de Euler-Fermat que dice que si \( \gcd(a,n)=1 \) entonces \( a^{\varphi(n)}\equiv1\pmod{n} \), pero no logro calcular \( 65^{-1}\pmod{77} \) ???. Sé que es \( 32 \) ya que \( 65\cdot32\equiv1\pmod{77} \), pero ¿cómo? :laugh:.
Finalmente, las soluciones serán de la forma \( x=69+77k \), con \( k\in\{0,1,\dots,5\} \).
Gracias!!
Saludos
-
Hola
Hola!
Marcar la opción correcta y justificar. La ecuación de congruencia \[390x\equiv114\pmod{462}\] tiene (soluciones principales):
- Solución única.
- \( 2 \) soluciones.
- \( 6 \) soluciones.
- No tiene solución.
Creo que la respuesta es la (c).
En primer lugar verifiquemos si la ecuación dada posee o no solución, a través de la condición necesaria y suficiente:
Puesto que \( \gcd(390,462)=6 \) (a través del algoritmo de Euclides, son suficientes \( 5 \) iteraciones) y además \( 6\mid114 \) ya que \( 114=19\cdot6 \) luego existen \( 6 \) soluciones principales en \( \Bbb{Z}_{462} \). La (d) por tanto queda descartada.
Si ya te han probado ese resultado que usas para determinar el número de soluciones, en él ya está justificado que tal número es 6 y no cualquiera de las otras opciones. No hace falta que argumente nada más.
En incluso si no te lo han probado, vale la pena que lo pruebes que no es difícil.
Es decir tener que resolver la ecuación para determinar el número de soluciones es trabajar innecesariamente.
Para descartar las otras podemos encontrar todas las soluciones principales de la ecuación. En primer lugar dividamos todo por \( 6 \) para trabajar más fácil: \[65x\equiv19\pmod{77}.\] Sabemos que una solución es \( x=65^{\varphi(77)-1}\cdot19 \), donde \( \varphi(\alpha) \) es la función de Euler.
Sabemos que \( \varphi(77)=77(1-1/7)(1-1/11)=60 \), de esta manera \( x=65^{59}\cdot19 \). Y a partir de aquí no supe cómo demostrar que \( 65^{59}\cdot19\equiv69\pmod{77} \).
Intenté usar el teorema de Euler-Fermat que dice que si \( \gcd(a,n)=1 \) entonces \( a^{\varphi(n)}\equiv1\pmod{n} \), pero no logro calcular \( 65^{-1}\pmod{77} \) ???. Sé que es \( 32 \) ya que \( 65\cdot32\equiv1\pmod{77} \), pero ¿cómo? :laugh:.
Es que si quieres resolver la ecuación yo no usaría el teorema de Euler-Fermat sino el algoritmo de Euclides y la forma usual de resolver una ecuación diofántica lineal (http://rinconmatematico.com/foros/index.php?topic=26781.0):
\( \cancel{65x+19y=77} \)
\( 65x+77y=19 \)
(en el enlace tienes como hacerlo).
Saludos.
CORREGIDO.
-
Hola
Si ya te han probado ese resultado que usas para determinar el número de soluciones, en él ya está justificado que tal número es 6 y no cualquiera de las otras opciones. No hace falta que argumente nada más.
En incluso si no te lo han probado, vale la pena que lo pruebes que no es difícil.
Es decir tener que resolver la ecuación para determinar el número de soluciones es trabajar innecesariamente.
Pues... Quiero resolver la ecuación "Como no cuesta demasiado yo por curarme en salud y dejar todo más claro si daría los contraejemplos" (en este caso justificaciones):
Pero bueno tomado al pie de la letra el enunciado tampoco pide justificar la respuesta y entiendo que si se exige hacerlo.
Como no cuesta demasiado yo por curarme en salud y dejar todo más claro si daría los contraejemplos.
¿Por qué en ese hilo es más conveniente descartar todos los demás casos y en este no?
Es que si quieres resolver la ecuación yo no usaría el teorema de Euler-Fermat sino el algoritmo de Euclides y la forma usual de resolver una ecuación diofántica lineal (http://rinconmatematico.com/foros/index.php?topic=26781.0):
\( 65x+19y=77 \)
(en el enlace tienes como hacerlo).
¿Cómo se pasa de la expresión \( ax\equiv b\pmod{n} \) a \( ax+by=n \)?
Creo que así: si \( ax\equiv b\pmod{n} \) entonces \( n\mid(ax-b) \) si y sólo si existe \( -y\in\Bbb{Z} \) tal que \( (ax-b)(-y)=n \). Distribuyendo, \( ax(-y)+by=n \) y como \( x(-y)\in\Bbb{Z} \) tenemos \( am+by=n \) con \( m=x(-y) \). Ahora podemos reemplazar \( m \) por \( x \) y ya tenemos la ecuación.
¿Es correcto?
Saludos
-
Hola
¿Por qué en ese hilo es más conveniente descartar todos los demás casos y en este no?
Es que aquí las respuesta son excluyentes. Si yo digo cuantos dedos tiene tu mano: y las opciones son 4,5 o 6. Tu mano no puede tener al mismo tiempo 4 dedos y 5 dedos. Entonces si tu justificas que tienes 5 dedos automáticamente estás justificando que las otras opciones están descartadas.
No obstante, añado otra cosa, al hilo de tus últimos mensajes. Una cosa es entender un ejercicio, las matemáticas y conceptos que hay detrás de él y otra lo que uno debe de escribir para responder al ejercicio en un examen, prueba o ante un profesor. Esto último es necesariamente subjetivo. Ya lo hemos hablado otras veces. El si hay que precisas o detallar más tal o cual argumento depende de los acuerdos y convenios implícitos o explícitos profesor-alumnos. Si uno se pone "picajoso" siempre se podría pedir más y más y más detalle hasta basar todo en las primeras definiciones de cada concepto. Obviamente esto sería prolijo; interminable. Entonces como norma general uno debe basarse en resultados ya probados en la asignatura u otras asignaturas previas y con todo lo que tiene de subjetivo, en los "usos y costumbres" del nivel académico en el que te encuentres.
¿Cómo se pasa de la expresión \( ax\equiv b\pmod{n} \) a \( ax+by=n \)?
Creo que así: si \( ax\equiv b\pmod{n} \) entonces \( n\mid(ax-b) \) si y sólo si existe \( -y\in\Bbb{Z} \) tal que \( (ax-b)(-y)=n \). Distribuyendo, \( ax(-y)+by=n \) y como \( x(-y)\in\Bbb{Z} \) tenemos \( am+by=n \) con \( m=x(-y) \). Ahora podemos reemplazar \( m \) por \( x \) y ya tenemos la ecuación.
¿Es correcto?
Si.
Saludos.
P.D. Una pregunta y no te la tomes a mal, que es por echarle un poco de sentido del humor. ¿Si alguien te pregunta por la calle: "Disculpe, por favor, ¿tiene hora?". Le dices: "Si" (suponiendo que tengas reloj o forma de saber la hora)…y luego te vas sin decirle que hora es?.
-
Hola
Soy consciente de lo que decís en negrita y de la justificación que das sobre por qué no hace falta resolver la ecuación (¡gracias.por el ejemplo de los dedos!).
Pero ahora veo que me equivoqué en la expresión: debería ser \( ax-b=n(-y) \), porque si \( a\mid b \) entonces \( b=ka \). \( 2\mid4 \) ya que existe \( k \) tal que \( 4=2k \).
¿Cómo se soluciona este inconveniente?
Saludos
R.P.D. :laugh: Ámbito callejero no es lo mismo que ámbito educativo, y más cuando de matemáticas se trata. Estando en la calle y si viene una persona ("alguien" puede ser un ángel también, de acuerdo a mi definición de alguien) y bajo condiciones normales (si no estoy involucrado en una situación potencial de robo); si se cumplen todas esas condiciones, por los convenios establecidos y por no ser tacaño, pues claro que le daría la hora :laugh:.
-
Hola
Pero ahora veo que me equivoqué en la expresión: debería ser \( ax-b=n(-y) \), porque si \( a\mid b \) entonces \( b=ka \). \( 2\mid4 \) ya que existe \( k \) tal que \( 4=2k \).
¿Cómo se soluciona este inconveniente?
¡Ah!. Perdona fui yo el que cometí el error. Ya lo he corregido. Es:
\( \cancel{65x+19y=77} \)
\( 65x+77y=19 \)
Es decir \( ax\equiv b \) mod \( n \) equivale a \( ax+yn=b \).
Saludos.
-
Hola, manooooh, buenas tardes.
¿Cómo se pasa de la expresión \( ax\equiv b\pmod{n} \) a \( ax+by=n \)?
Creo que así: si \( ax\equiv b\pmod{n} \) entonces \( n\mid(ax-b) \) si y sólo si existe \( -y\in\Bbb{Z} \) tal que \( (ax-b)(-y)=n \). Distribuyendo, \( ax(-y)+by=n \) y como \( x(-y)\in\Bbb{Z} \) tenemos \( am+by=n \) con \( m=x(-y) \). Ahora podemos reemplazar \( m \) por \( x \) y ya tenemos la ecuación.
Yo lo hago así siempre
\( ax-b\equiv0\pmod{n}\Rightarrow ax-b=kn
\)...
Cambias “k” por “y” y ya está, basta despejar. Pongo primero “k” porque hasta ahí es más típica para representar un múltiplo de algo y “la veo” antes. De esta manera la puedes escribir directamente, de memoria, y te acuerdas siempre (bueno, cambia por -y, para que quede positiva al despejar si quieres, es igual).
(ya sé que sólo es una tontería, pero era para saludarte principalmente; que éste es de los pocos hilos ya, entre los que pones, en los que me sé algo para decir).
Saludos
-
Hola
Yo lo hago así siempre
\( ax-b\equiv0\pmod{n}\Rightarrow ax-b=kn
\)...
Cambias “k” por “y” y ya está, basta despejar. Pongo primero “k” porque hasta ahí es más típica para representar un múltiplo de algo y “la veo” antes. De esta manera la puedes escribir directamente, de memoria, y te acuerdas siempre (bueno, cambia por -y, para que quede positiva al despejar si quieres, es igual).
(ya sé que sólo es una tontería, pero era para saludarte principalmente; que éste es de los pocos hilos ya, entre los que pones, en los que me sé algo para decir).
Gracias feriva!
Saludos
-
Hola
Yo lo hago así siempre
\( ax-b\equiv0\pmod{n}\Rightarrow ax-b=kn
\)...
Cambias “k” por “y” y ya está, basta despejar. Pongo primero “k” porque hasta ahí es más típica para representar un múltiplo de algo y “la veo” antes. De esta manera la puedes escribir directamente, de memoria, y te acuerdas siempre (bueno, cambia por -y, para que quede positiva al despejar si quieres, es igual).
(ya sé que sólo es una tontería, pero era para saludarte principalmente; que éste es de los pocos hilos ya, entre los que pones, en los que me sé algo para decir).
Gracias feriva!
Saludos
De nada, manooooh :) Cuánto tiempo sin saludarnos.
Buenas noches.