> 
> Show that every prime number greater than $3$ is of the form $6k+1$ or $6k+5$, where $k \in \mathbb{Z^+}.$
> 
> 
> 

Looking at couple of cases it seems that $6(0)+1=5$ and $6(1)+1=7$ starting from $5$ every other prime can be expressed as $6k+1$. My inital guess was if I could use induction to show this, but didn't quite get it to work. I also considered if I could get a contradiction, but couldn't formalize that also. Is this possible with either option?