Attempting to prove the claim: "Every prime greater than $3$ can be written in the form $6n + 1$ or $6n + 5$" by induction. Claim:

Every prime greater than $3$ can be written in the form $6n + 1$ or $6n + 5$ for some $n\in \mathbb Z^+$.

Proof (my attempt):
Base case: $n=0$.

$6n + 5 = 6*0 + 5 = 5$, which is prime.

Inductive hypothesis: Suppose the statement $S(n)$ is true for some $n\in\mathbb Z^+$.
Inductive step: $S(n + 1)$

$6(n + 1) + 1 = p > 3$ or $6(n + 1) + 5 = p > 3$

By induction, the claim is true.
This is my attempt, but it seems fishy.
Is this proof sound?
 A: Usually we don’t use induction to prove this. Honestly I want to know a sound induction proof if there exists one.
You can clearly see

*

*$2|6n+2$

*$2|6n+4$

*$2|6n$

*$3|6n+3$
So except for $2$ and $3$, all the primes can be written as $6n+1$ or $6n+5$, where $n \in \mathbb{Z}$.
A: Hint $ $ As for many induction problems often the key is to strengthen the induction hypothesis to a form that eases the inductive step. Note that the primes $> 3$ are coprime to $\,2,3\,$ so coprime to $\,6$.
Thus it suffices to prove that naturals coprime to $\,6\,$ have form $\,1+6k\,$ or $\,5+6k,\,$ and this has an obvious (complete) induction step because  $\,\gcd(n+6,6) = \gcd(n,6)\,$ by Euclid, therefore we infer that $\,n+6\,$ is coprime to $\,6\iff n$ is coprime to $6,\,$ so a (complete) induction reduces the truth of the statement to that of the obviously true base case of naturals $\,< 6$.
A: Since $p$ must be coprime to $6$ and $\phi(6)=2$, "Euler's Theorem" gives us
$$p^2\equiv1\pmod6$$
Therefore, $6\mid p^2-1$ and so also $6\mid p^2-1-6p+6=(p-1)(p-5)$. From $3\mid6$, we also have $3\mid (p-1)(p-5)$, and (since $p$ is a prime) it follows that $3\mid p-1$ or $3\mid p-5$. Since $2$ devides both factors (and $2$ and $3$ are coprime), we conclude that $2\cdot3=6\mid p-1$ or $6\mid p-5$. This means that there exists some integer $n$ such that $6n=p-1$ or $6n=p-5$, in other words $p=6n+1$ or $p=6n+5$.
