Autor Tema: Dos problemas de Matemática Discreta (Aritmética Entera y Modular)

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

17 Enero, 2008, 10:19 pm
Leído 2184 veces

Lucix_ct

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 10
  • Karma: +0/-0
  • Sexo: Femenino
Tengo dificultades para hacer estos 2 problemas:

Demuestra que siempre que calculamos \(  2x^{20} - x^{14} + x^7 - x^2 - x + 3 \) y dividimos el resultado entre 7 nos sale de resto 3.

El otro problema es:

Encuentra, si es posible, un número n sabiendo que cumple las siguientes condiciones:

- Al escribirlo en base 4 termina en 1
- Las dos últimas cifras al escribirlo en base 3 son 11
- Es divisible por 5 y por 7
- Está entre 3000 y 4500

Lo único que sé es que hay que aplicar el teorema chino del resto, pero no sé cómo utilizarlo.

Espero su respuesta lo antes posible.

Gracias.

17 Enero, 2008, 11:25 pm
Respuesta #1

Ked

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 945
  • Karma: +0/-0
  • Sexo: Masculino
Sobre el primer problema, no se me ocurre algo mejor que factorizar el polinomio \( 2x^{20} - x^{14} + x^7 - x^2 - x  \) como \( x(x + 1)(x - 1)(x^2 + x + 1)(x^2 - x + 1)(2x^{13} + x^7 + x + 1) \) y estudiar caso por caso en los enteros módulo 7... aunque no es una solución para nada elegante (debe haber algo más sencillo que no estoy viendo o no conozco).

Para el segundo me desconcierta lo que dices sobre "no sé utilizar el teorema del resto chino". ¿Quiere decir que no sabrías aplicarlo aunque te diera el sistema de congruencias "digerido"? ¿O que no sabes cómo hacerlo aparecer, en este caso?

Te voy a traducir el lenguaje natural a las congruencias, y me dices dónde te surgen dudas para que te explique con más detalle si es necesario.
Antes que nada ten en cuenta cómo es la expresión de un número en base p: \( n = a_np^n + a_{n-1}p^{n-1} + \ldots + a_2 p^2 + a_1p^1 + a_0p^0 \). Los coeficientes \( a_i \) son los que normalmente escribimos como los dígitos del número. Por ejemplo, 125 en base 10 es \( 1\cdot10^2 + 2\cdot10^1 + 5\cdot 10^0 \).

- Al escribirlo en base 4 termina en 1
\( n \equiv 1 \pmod 4 \)

- Las dos últimas cifras al escribirlo en base 3 son 11
\( n \equiv 1\cdot3^1 + 1\cdot 3^0 = 4 \pmod {3^2} \)

- Es divisible por 5 y por 7
\( n \equiv 0 \pmod 5 \)
\( n \equiv 0 \pmod 7 \)

Ahora aplicas el teorema del resto chino para resolver el siguiente sistema de congruencias:
\(
\left\{\begin{matrix}
n \equiv 1 \pmod 4\\
n \equiv 4 \pmod 9\\
n \equiv 0 \pmod 5\\
n \equiv 0 \pmod 7
\end{matrix} \right \)

Se puede aplicar directamente el teorema ya que todos los módulos son coprimos.

Spoiler
La solución del sistema de congruencias es \( n \equiv 805 \pmod{1260} \) por lo que fácilmente vemos que el número que buscas es \( 805 + 2\cdot1260 = 3325 \).
[cerrar]

Saludos

17 Enero, 2008, 11:56 pm
Respuesta #2

topo23

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 937
  • Karma: +0/-0
Por el PTF se puede saber que \( x^p = x \mod(p) \) cuando p es primo para cualquier x. Esto te sirve para simplicar el polinomio, por ejemplo \( x^{14}= x^2 \mod(p) \) y \( x^{20}= x^{14}x^{6} = x^{2}x^6 = x^8 =  x^{7}x = x^2 \mod(p) \).

Luego habria que ver los casos cuando x es multiplo de 7 muy facil, y cuando no lo es en ese caso hay que usar el PTF que dice que si a y p son coprimos entonces \( a^{p-1}=1 \mod(p) \).
.

18 Enero, 2008, 12:24 am
Respuesta #3

Lucix_ct

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 10
  • Karma: +0/-0
  • Sexo: Femenino
Ahora he comprendido cómo se hacen y también he podido ver dónde tengo las "lagunas" y los fallos.

Muchísimas gracias por vuestra ayuda. La verdad es que hacéis un trabajo maravilloso, que es ayudar a esa gente que tiene dificultades en momentos de su vida (en este caso, las Matemáticas).

De nuevo, muchísimas gracias por todo.