Prove that if $G$ is a group of order $39$ then $G$ has a subgroup of order $3$

I was able to show this by first proving $G$ requires and element of order $3$. However I am looking for alternative proofs without the use of Sylow theorems or Cauchy's theorem. Any hints would be appreciated.

• 39 is 13 times 3, and one can classify groups of order pq for p,q primes. In your case either G is C_3 x C_13 which admits manifestly an element of order 3, or a semidirect product of those, which also admits an element of order 3 by the C_3 factor. – Pedro Tamaroff Dec 18 '15 at 22:54

If there is no subgroup of order 3, then there are no elements of order 3. The only other possible orders are 1, 13, and 39, and there can be no elements of order 39 (otherwise there is an element of order 3). Thus, every element has order 1 or 13. Since 13 is prime, the distinct subgroups generated by the elements of the group intersect trivially, and these subgroups cover the group. Thus, there are $12n+1$ elements, for some $n$. Since 39 is not of this form, this is a contradiction.
Let $g$ be an element of $G$ other than $e$. It has order $3$, $13$ or $39$.
If the order is $3$, then you are done. If it's $39$ then $g^{13}$ has order $3$.
If the order is $13$ then $g^k$ is a generator of $\langle g\rangle$ for any $k=1,\ldots,12$.
Let $h$ be an element of $G$ that is not in $\langle g\rangle$. Again it's order is $3$, $13$ or $39$ and the only concerning case is if the order is $13$. Then $h^k$ is a generator of $\langle h\rangle$ for $k = 1,\ldots, 12$ and since $h$ is not in $\langle g\rangle$ then it follows that $\langle g\rangle \cap \langle h\rangle = \{e\}$.
We consider now an element $i$ that is not in $\langle g\rangle \cup \langle h\rangle$. We have the same scenario as before and if its order is $13$ then the only element of $\langle i\rangle$ in common with $\langle g\rangle \cup \langle h\rangle$ is $e$. That means that $\langle g\rangle \cup \langle h\rangle\cup \langle i\rangle$ has $37$ elements. The two remaining elements cannot have order $13$ or $1$, and therefore have order $3$ or $39$ and we are done.