¿Qué significa aquí pasar la prueba de la base 3?

Question

Tengo este:

Sea $n$ sea un entero impar positivo que pase la prueba de base 3, es decir $3^n\equiv 3\pmod n$ . Demostrar que $\frac{3^n-1}{2}$ también pasa la prueba de base 3.

Mi intento:

$3^n\equiv 3\pmod n$

$\Rightarrow 3^n-1\equiv 2\pmod n$

$\Rightarrow \frac{3^n-1}{2}\equiv 1 \pmod n$

Así, $3^{\frac{3^n-1}{2}}\equiv3^1\pmod n$

¿Es eso lo que significa pasar la prueba de base 3 para $\frac{3^n-1}{2}$ ?

Answer 1

Para simplificar el álgebra, digamos

$$r = \frac{3^n-1}{2} \tag{1}\label{eq1A}$$

Nótese que el problema en realidad pide demostrar que, dado $n$ supera la prueba, entonces $r$ también pasa la "base $3$ prueba", es decir $r$ es un número entero impar positivo y $3^r \equiv 3 \pmod{r}$ .

Desde $n$ es un número entero impar positivo, entonces $r \ge 1$ y $3^n \equiv (-1)^n \equiv 3 \pmod{4}$ Así que $3^n-1 \equiv 2 \pmod{4} \; \; \to \; \; \frac{3^n-1}{2} \equiv 1 \pmod{2}$ es decir, $r$ también es un entero impar positivo. En \eqref {eq1A}, también tenemos

$$3^n \equiv 1 \pmod{r} \tag{2}\label{eq2A}$$

A continuación

$$m = \operatorname{ord}_{r}(3) \; \; \to \; \; 3^m \equiv 1 \pmod{r} \tag{3}\label{eq3A}$$

donde $\operatorname{ord}_{r}(3)$ es el orden multiplicativo de $3$ modulo $r$ . Desde $n$ pasa la "base $3$ prueba", y \eqref {eq2A} muestra que $m \mid n$ tenemos

$$3^n \equiv 3 \pmod{n} \; \; \to \; \; 3^n \equiv 3 \pmod{m} \tag{4}\label{eq4A}$$

Como ya has hecho básicamente, $3^n - 1 \equiv 2 \pmod{m} \; \to \; r = \frac{3^n-1}{2} \equiv 1 \pmod{m}$ . Esto significa que hay un número entero $k$ donde $r = km + 1$ . Así, utilizando este y \eqref {eq3A}, obtenemos que

$$3^r \equiv 3^{km + 1} \equiv \left(3^m\right)^k(3) \equiv 3 \pmod{r} \tag{5}\label{eq5A}$$

Esto demuestra que $r = \frac{3^n-1}{2}$ también pasa la "base $3$ prueba".