A alguien le salió?
$$i)\textrm{Sea }a \textrm{ un entero impar. Probar que }2^{n+2}|a^{2^n}-1 \textrm{ para todo }n\in\mathbb{N}$$
$$ii)\textrm{Hallar el resto de la division de }5^{2267} \textrm{ por }32$$
Firma
Tema
[A resolver]Práctica 5 - Ejericicio 5
$$\textrm{i) Sea a un entero impar... }$$
\(P(n)\,:\; \,"\, 2^{n+2} \mid a^{2n} -1 \,"\)
$$\textrm{Veamos que vale P(1)}$$
$$2^{2+1}\mid a^{2^1} -1$$
$$2^3\mid \left(2k-1\right)^2 -1$$
$$2^3\mid 4k^2 -4k$$
$$2\mid k \left(k-1)\quad \forall \;k \in \mathbb{Z}$$
$$\textrm{Quiero ver que}\; P(n)\Longrightarrow P(n+1)$$
$$2^{n+2}\mid a^{2^n} -1 \; \Longrightarrow 2^{n+3}\mid a^{2^{n+1}} -1$$
$$2^{n+3}\mid a^{2^{n+1}} -1 \; \iff 2^{n+2} \cdot 2 \mid \left(a^{2^n} -1\right) \cdot \left(a^{2^n} +1\right)$$
$$\por\; H.I\; \left(a^{2^n} -1\right) \,= \, 2^{n+2} \cdot q \quad \quad q \in \mathbb{Z}$$
$$Luego,$$
$$\quad 2^{n+2} \cdot 2 \mid 2^{n+2} \cdot q \cdot \left(a^{2^n} +1\right)$$
$$2 \mid q \cdot \left((2k-1)^{2n} +1\right)$$
\(Vale, \; pues\quad \left((2k-1)^{2n} +1\right) \;es\; par \; \forall \;k \in \textbb{Z}\;, n \in \textbb{N}\)
$$\textrm{Creo que esta bien.. chequealo por las dudas, Saludos}$$
Firma
$$Que\; no\; es\; lo\; que\; queriamos\; demostrar... \hspace{3cm}\Box$$
$$\textrm{ii)Hallar el resto de la divi..}$$
\(5^3 \equiv 29 (32)\)
$$5^8 \equiv 1 (32)$$
$$5^{2267} \; =\; 5^{2264} \cdot 5^3$$
$$2264 \; = \; 8 \cdot 283$$
$$Luego, \quad (5^8)^{283} \equiv 1^{283} (32)$$
$$Mas\; aun\; (5^8)^{283} \cdot 5^3 \equiv 1 \cdot 5^3 (32)$$
$$Entonces\; 5^{2267} \equiv 29 (32)$$
\(\textrm{El resto es 29}\)
$$\textrm{Espero que sirva, Saludos che}$$
Esta es otro forma de resolver el i) que usa congruencia
\({2}^{n+2} \mid {a}^{2^n}-1 \Leftrightarrow {a}^{2^n} \equiv 1 ({2}^{n+2})\)
$$\textrm{ Uso induccion sobre n }$$
$$\textrm{ Caso base: ${a}^{2} \equiv 1 ({2}^{3})$ }$$
$$\textrm{ Lo pruebo por induccion con $|a|=2k-1$ }$$
$$\textrm{ Caso base2: ${1}^{2} \equiv 1 (8)$ }$$
$$\textrm{ Paso ind2: Supongo ${(2k-1)}^{2} \equiv 1 (8).$ }$$
$$\textrm{ Qvq ${(2k+1)}^{2} \equiv 1 (8)$ }$$
$${(2k+1)}^{2}={((2k-1)+2)}^{2}={(2k-1)}^{2}+4(2k-1)+4 \equiv 1+8k \equiv 1 (8)$$
$$\textrm{ Paso ind: supongo ${a}^{2^n} \equiv 1 ({2}^{n+2})$ }$$
$$\textrm{Qvq ${a}^{2^{n+1}} \equiv 1 ({2}^{n+3})$}$$
$${a}^{2^{n+1}}={({a}^{2^n})}^{2}\equiv{1}^2=1 ({2}^{n+2}) \Leftrightarrow$$
$$\Leftrightarrow 2 \cdot {a}^{2^{n+1}} \equiv 2 ({2}^{n+3}) \Leftrightarrow$$
\(\Leftrightarrow {a}^{2^{n+1}} \equiv 1 ({2}^{n+3})\)
Perdón por no poner las propiedades de congruencia que uso, pero es un bardo escribirlas en Tex, si no entienden de dónde salió algo en particular díganme y se los aclaro..
Matias escribió:
Esta es otro forma de resolver el i) que usa congruencia
$$2 \cdot {a}^{2^{n+1}} \equiv 2 ({2}^{n+3}) \Leftrightarrow {a}^{2^{n+1}} \equiv 1 ({2}^{n+3})$$
Este último renglón tiene un error. De izquierda a derecha estás dividiendo por 2 en \(\mathbb{Z}_{2^{n+3}}\), pero 2 no es inversible ahí. La primera solución está bien. De alguna manera hay que usar que \(a^{2^{n+1}}+1\) es par.
Yo lo que usé ahí en realidad, es que \(2 \cdot a^{2^{n+1}}\) es igual a \(a^{2^{n+1}} + a^{2^{n+1}}\) y que la única forma de que eso sea congruente a 2 es que \(a^{2^{n+1}\) sea congruente a 1.. Ahora que lo decís no estoy tan seguro que esto sea cierto, voy a pensar un toque si lo puedo probar y de ser así lo pongo..
Puede también ser \(1+2^{n+2}\).