<s>[INST] What does passing the base 3 test mean here? I have got this one:
Let $n$ be a positive odd integer passing the base 3 test, i.e. $3^n\equiv 3\pmod n$. Prove that $\frac{3^n-1}{2}$ also passes the base 3 test.
My attempt:
$3^n\equiv 3\pmod n$
$\Rightarrow 3^n-1\equiv 2\pmod n$
$\Rightarrow \frac{3^n-1}{2}\equiv 1 \pmod n$
Thus, $3^{\frac{3^n-1}{2}}\equiv3^1\pmod n$
Is that what it means to pass the base 3 test for $\frac{3^n-1}{2}$?
 [/INST] For simpler algebra, let
$$r = \frac{3^n-1}{2} \tag{1}\label{eq1A}$$
Note the problem is actually asking to prove that, given $n$ passes the test, then $r$ also passes the "base $3$ test", i.e., $r$ is a positive, odd integer and $3^r \equiv 3 \pmod{r}$.
Since $n$ is a positive, odd integer, then $r \ge 1$ and $3^n \equiv (-1)^n \equiv 3 \pmod{4}$, so $3^n-1 \equiv 2 \pmod{4} \; \; \to \; \; \frac{3^n-1}{2} \equiv 1 \pmod{2}$, i.e., $r$ is a positive, odd integer too. From \eqref{eq1A}, we also have
$$3^n \equiv 1 \pmod{r} \tag{2}\label{eq2A}$$
Next, let
$$m = \operatorname{ord}_{r}(3) \; \; \to \; \; 3^m \equiv 1 \pmod{r} \tag{3}\label{eq3A}$$
where $\operatorname{ord}_{r}(3)$ is the multiplicative order of $3$ modulo $r$. Since $n$ passes the "base $3$ test", and \eqref{eq2A} shows that $m \mid n$, we have
$$3^n \equiv 3 \pmod{n} \; \; \to \; \; 3^n \equiv 3 \pmod{m} \tag{4}\label{eq4A}$$
As you've already basically done, $3^n - 1 \equiv 2 \pmod{m} \; \to \; r = \frac{3^n-1}{2} \equiv 1 \pmod{m}$. This means there's an integer $k$ where $r = km + 1$. Thus, using this and \eqref{eq3A}, we get that
$$3^r \equiv 3^{km + 1} \equiv \left(3^m\right)^k(3) \equiv 3 \pmod{r} \tag{5}\label{eq5A}$$
This proves that $r = \frac{3^n-1}{2}$ also passes the "base $3$ test".
</s>