Demuestra que $\frac{(3^{77}-1)}{2}$ es impar y compuesto

Question

La pregunta que se me hace es:

Demuestra que $\large\frac{(3^{77}-1)}{2}$ es impar y compuesto.

Podemos demostrar que $\forall n\in\mathbb{N}$ :

$$3^{n}\equiv\left\{ \begin{array}{l l} 1 & \quad \text{if $n\equiv0\pmod{2}$ }\\ 3 & \quad \text{if $n\equiv1\pmod{2}$}\\ \end{array} \right\} \pmod{4}$$

Por lo tanto, podemos demostrar que $3^{77}\equiv3\pmod{4}$ . Así, podemos determinar que $(3^{77}-1)\equiv2\pmod{4}$ . Así, podemos demostrar que $\frac{(3^{77}-1)}{2}$ es impar as:

$$\frac{(3^{77}-1)}{2}\equiv\pm1\pmod{4}$$

Sin embargo, no estoy seguro de cómo demostrar que este número es compuesto. El libro que estoy leyendo simplemente indica dos de los factores, $\frac{(3^{11}-1)}{2}$ y $\frac{(3^{7}-1)}{2}$ pero no sé cómo los autores descubrieron estos factores.

Agradecería cualquier ayuda que me indique la dirección correcta, gracias.

Answer 1

Otra forma de verlo es escribiendo el número en base 3 :

$$3^{77}=1\underbrace{00\dots00}_{77}\ _3$$

Aquí el índice $3$ denota la base 3, y $77$ es el número de dígitos. Restando uno, obtenemos:

$$3^{77}-1=\underbrace{22\dots22}_{77}\ _3$$

Por lo tanto, dividiendo esto por dos,

$$\frac{3^{77}-1}{2}=\underbrace{11\dots11}_{77}\ _3$$

De esto podemos leer directamente que el número es impar, ya que es la suma de 77 números Impares, y compuesto, ya que $$\underbrace{11\dots11}_{77}\ _3=1111111_3\cdot\underbrace{10000001000000\dots100000010000001}_{71}\ _3$$

(Aunque, esto es básicamente lo mismo que algunas de las otras respuestas).

Answer 2

Una pista: $$a^n-1=(a-1)(a^{n-1}+a^{n-2}+...+a+1)\,,\,\,\forall n\in\mathbb{N} \wedge \forall a\in\mathbb{R}$$

Añadido Por supuesto, también tenemos en este caso, aplicando lo anterior: $$3^{77}-1=\left(3^7\right)^{11}-1=(3^7-1)\left(\left(3^7\right)^{10}+\left(3^7\right)^9+...+3^7+1\right)\,,\,etc.$$ y algo similar se puede hacer con $\,3^{77}=\left(3^{11}\right)^7$

Answer 3

Bueno siguiendo tu idea de congruencias tenemos que $$ 3^{77} \equiv 3^{11} \equiv 1 \pmod{23} $$ Así que $$ 3^{77} - 1\equiv 0 \pmod{23} $$ Desde $2^{-1} \equiv 12 \pmod{23}$ tenemos que $$ \dfrac{3^{77}-1}{2} \equiv 0 \pmod{23} $$ Por lo tanto, $23 \mid \dfrac{3^{77}-1}{2}$ y, por lo tanto, es compuesto.

Answer 4

Tenga en cuenta que si $m=kn$ para algunos $k\in\mathbb{N}$ entonces $$a^m-1=(a^n)^k-1=(a^n-1)(a^{n(k-1)}+a^{n(k-2)}+\cdots+a^n+1)$$ para que $a^n-1$ divide $a^m-1$ .

Answer 5

Sugerencia $\, $ Lo que se busca factores demostrar la compostura de su número surgen muy simplemente de una factorización composicional $\rm\:g\:\!f = g\circ f\:$ de un polinomio, combinado con el Teorema del factor.

$$\begin{eqnarray}\rm z\,\ -\,\ c\ & | &\,\rm\ g\:\!(\,z\,) - g\:\!(\,c\,) \\ \rm f(x)\!-\!f(a) &|&\,\rm\ g\:\!f(x) - g\:\!f(a) \\ \rm x^7\, -\, a^7\, & | &\,\rm (x^{7})^{11} - (a^{7})^{11} \\ 3^7-\,1\ & | &\:\!\ (3^{7})^{11} - 1 \end{eqnarray}$$

Obsérvese que si empleamos la notación $\rm\:x^f = f(x)\:$ (por ejemplo, como en la teoría de Galois) entonces es más claro

$$\begin{eqnarray}\rm z\,\ -\,\ c\,\:\! & | &\rm\ (\,z\,)^g - \:\!(\,c\,)^g \\ \rm x^f\ -\ a^f\, &|&\rm\ (x^f)^g - (a^f)^g \\ \rm x^7\, -\, a^7\, & | &\:\rm (x^{7})^{11}\!\! - (a^{7})^{11} \\ 3^7-\,1\ & | &\:\!\ (3^{7})^{11\!} - 1 \end{eqnarray}$$

En el caso de Galois, la notación exponencial pone de manifiesto otra estructura, por ejemplo, de mi puesto aquí

$\quad\quad\begin{align}{} \rm g^{\:\sigma^4-1} \;=\;& \rm g^{\:(1\:+\;\sigma\:+\;\sigma^2\:+\;\:\sigma^3)\:(\sigma-1)} \\\\ \iff\quad\quad\rm \frac{\sigma^4 g}g \;=\;& \rm (g \;\: \sigma\:g \;\:\sigma^2 g \;\:\sigma^3 g)^{\sigma - 1} \;=\; \frac{\phantom{g\;\;\:} \sigma\:g \;\;\: \sigma^2 g \;\;\:\sigma^3 g \;\;\:\sigma^4 g}{g \;\;\:\sigma\:g \;\;\:\sigma^2 g \;\;\:\sigma^3 g\phantom{\;\;\:\sigma^4 g}} \\\\ \end{align}$