Hint $ $ The hypotheses imply the order $\,k\,$ of $\,x\,$ is a divisor of $\,n-1\,$ but not a proper divisor, so $\, k = n-1.\, $ By here and Euler, $\,n-1\mid \phi(n)\ $ so $\ n-1\, \le\, \phi(n).\, $ This implies $\,n\,$ is prime, by$\ \phi(n) \,\le\, n-\color{red}{2}\ $ for composite $\,n,\,$ by at least $\color{red}2\,$ smaller naturals $1<n\!-\!1$ are noncoprime to $\,n$.
Optimization $ $ We can we can restrict to maximal proper divisors $\,q\,$ using the following.
Order Test $\ \,a\,$ has order $\,n\iff a^n \equiv 1\,$ but $\,a^{n/p} \not\equiv 1\,$ for every prime $\,p\mid n.\,$
Proof $\ (\Leftarrow)\ $ If $\,a\,$ has $\,\color{#c00}{{\rm order}\ k}\,$ then $\,k\mid n\,$ (proof). If $\:k < n\,$ then $\,k\,$ is proper divisor of $\,n\,$ therefore $\,k\,$ arises by deleting at least one prime $\,p\,$ from the prime factorization of $\,n,\,$ hence $\,k\mid n/p,\,$ say $\, kj = n/p,\ $ so $\ a^{n/p} \equiv (\color{#c00}{a^k})^j\equiv \color{#c00}1^j\equiv 1,\,$ contra hypothesis. $\ (\Rightarrow)\ $ Clear.
It holds for $n=1,2$.
If it holds for $1,2,\dots,n$, then
\begin{align}
&3^{n+1}+7^{n+1}-2\\
&=3^2\cdot3^{n-1}+7^2\cdot7^{n-1}-2\\
&=(8+1)\cdot3^{n-1}+(48+1)\cdot7^{n-1}-2\\
&=8\cdot(3^{n-1}+6\cdot7^{n-1})+3^{n-1}+7^{n-1}-2\\
\end{align}
Therefore it also holds for $n+1$.
So it holds for all $n\in \mathbb N$.
Best Answer
Yes, you can do it by induction as well. Note that:
$3^{n+1}+8^{n+1}=3^n\times 3+8^n\times (3+5)=(3^n+8^n)\times 3+5\times 8^n$
By induction hypothesis the first term is not divisible by $5$ while the second term is obviously divisible by $5$. The required result follows.