residuos cuadráticos y función phi

Foro fmat.cl > Sector Preparación Olimpiadas > Sector Olímpico > Teoría de Números > Problemas Propuestos

residuos cuadráticos y función phi, mañoso

Opciones

tochalo Ver Perfil del Miembro Ver los mensajes de este miembro	Sep 18 2010, 05:59 PM Publicado: #1
Dios Matemático Grupo: Usuario FMAT Mensajes: 426 Registrado: 13-January 08 Desde: desde la pieza de tu hermana Miembro Nº: 14.612 Nacionalidad: Colegio/Liceo: Sexo:	Hola, les dejo el siguiente problema. $TEX: Sea $m\geq 2$ un entero. Usando $\varphi(m)$, determine cuantos números coprimos con $m$ en $\{1,...,m-1\}$ son residuos cuadraticos módulo $m$$ Saludos

Pedantic Anarchy... Pedantic Anarchy Ver Perfil del Miembro Ver los mensajes de este miembro	Apr 9 2011, 02:38 PM Publicado: #2
Dios Matemático Supremo Grupo: Usuario FMAT Mensajes: 688 Registrado: 8-November 09 Desde: Villarrica Miembro Nº: 61.657 Nacionalidad: Colegio/Liceo: Universidad: Sexo:	$TEX: Si m=2, se tiene que la cantidad pedida es 1. Asumamos ahora que $m>2$. Sea $g$ una raiz primitiva de $m$, definamos $a_i$ como el resto de $g^i$ modulo m. Es un hecho conocido que ${a_1,a_2,....,a_{\phi (m)}}$ son los naturales menores que m y coprimos con m. Ahora si $i$ es par se obtiene facilmente que $a_i$ es un RC modulo m. Asumamos entonces que existe un $i$ impar tal que $a_i$ es un RC modulo m, se tendria que : $1=(\dfrac {a_i}{m})=(\dfrac {g^i}{m})=(\dfrac {g}{m})^i$, de donde $(\dfrac {g}{m})=1$ ya que i es impar. En consecuencia tenemos que existe un x natural tal que $x^2\equiv g(mod m)$, entonces como es un hecho conocido que $\phi (m)$ es par para $m>2$ tendriamos que $x^{\phi (m)}\equiv g^{(\dfrac {\phi m}{2})}(mod m)$ y por el teorema de euler $1\equiv g^{\dfrac {\phi (m)}{2}}(mod m)$, lo que contradice que g sea una raiz primitiva. Entonces tendriamos que $\dfrac {\phi (m)}{2}$ es la cantidad buscada para $m>2$ y por ende $\lceil \dfrac {\phi (m)}{2}\rceil $ es el resultado pedido$ -------------------- yo no soy especial a pesar que ella lo dijo tengo unos krk y un celular hechizo aún vácilo SFDK en el segundo piso y la frase final da igual la improviso

tochalo Ver Perfil del Miembro Ver los mensajes de este miembro	Apr 9 2011, 06:21 PM Publicado: #3
Dios Matemático Grupo: Usuario FMAT Mensajes: 426 Registrado: 13-January 08 Desde: desde la pieza de tu hermana Miembro Nº: 14.612 Nacionalidad: Colegio/Liceo: Sexo:	Bueena Pedantic ! Gracias por atender este propuesto. En tu prueba has tomado un natural m y luego consideraste una raíz primitiva de m para concluir que el total de números que satisface la propiedad es $TEX: $\displaystyle\frac{\varphi(m)}{2}$$ , lo cual está perfecto. Ahora bien, ten en cuenta que no todos los números tienen raíz primitiva. Siendo precisos, n tiene raíz primitiva si y sólo si $TEX: $n=4, p^k, 2p^k$$ siendo p un primo impar. Luego tu resultado es válido sólo para estos números. Chequea que para $TEX: n=12, n=15$ no se cumple que la cantidad de números que satisfacen la propiedad es $TEX: $\lceil{\displaystyle\frac{\varphi(m)}{2}}\rceil$$ Este ejercicio fue un problema de una tarea que me dieron en la u. Con mis compañeros no lo pudimos hacer (bueno, en realidad éramos sólo 5 en clases). Conjeturamos que si m es raíz primitiva entonces se tiene que el resultado es $TEX: $\displaystyle\frac{\varphi(m)}{2}$$ , que es lo que tú has expuesto y si no es raíz primitiva entonces el resultado es $TEX: $\displaystyle\frac{\varphi(m)}{4}$$ . Sería genial que pudieras demostrar o refutar esto último. Te dejo la tarea completa por si te interesa. Tarea_4.JPG ( 43.02k ) Número de descargas: 12 Saludos

« Posterior · Problemas Propuestos · Anterior »

1 usuario(s) está(n) leyendo esta discusión (1 invitado(s) y 0 usuario(s) anónimo(s))

0 miembro(s):

Modo de Ver: Estándar · Cambiar a: Lineal+ · Cambiar a: Outline

Suscribirse · Enviar por correo · Imprimir · Suscribirse a este foro

Versión Lo-Fi

Fecha y Hora actual: 23rd November 2024 - 09:56 AM