I want to prove the following statement :
If $n$ is an odd composite number, not being a power of $3$ (or, equivalent, having a prime factor $p>3$), $n$ is a fermat-pseudoprime to same base $a$, in other words, there is a number $a$ with $$1<a<n-1$$ and $$a^{n-1}\equiv 1\ (\ mod\ n\ )$$
I was able to prove the converse:
If $$a^{n-1}\equiv 1\ (\ mod\ n\ )$$ for some number $a$ with $1<a<n-1$, then the number $o\ :=\ ord_a(n)$ divides both $n-1$ and $\phi(n)$. Since $o=1$ is impossible because $a\equiv 1\ (\ mod\ n\ )$ contradicts $1<a<n-1$ and $\phi(3^k)=2\times 3^{k-1}$ , it follows that $o=2$. But $a^2\equiv 1\ (\ mod\ 3^k\ )$ implies $a\equiv \pm1\ (\ mod\ 3^k\ )$ because of $gcd(a-1,a+1)\le 2$. But this contradicts $1<a<n-1$, so the number cannot be a power of $3$
Is my proof of the converse correct ?
How can I show the original statement ?
Yes, your proof of the converse is correct.
To prove the original statement:
If $n = p^k$ for a prime $p > 3$, then the group of units modulo $n$ is cyclic, and therefore contains an element $a$ of order $p-1 \geqslant 4$. This is a base for which $n$ is a Fermat pseudoprime, and $a \not\equiv \pm 1 \pmod{n}$.
If $n$ has at least two distinct prime factors $p,q$, say $n = p^kq^m\cdot r$ with $\gcd(r,pq) = 1$, then let
$$a \equiv 1 \pmod{p^kr},\quad a \equiv -1 \pmod{q^m}.$$
Then $a^2 \equiv 1 \pmod{n}$, and $n$ is a Fermat pseudoprime for the base $a$.