Show that a group of order $pq$ has subgroup of order $p$ and $q$ without using sylow's and cauchy's theorem

If $o(G)$ is $pq$, $p>q$ are primes, prove that $G$ has a subgroup of order $p$ and a subgroup of order $q$.

[This question is from Herstein and it comes before Sylow's and Cauchy's theorem. So I'm expecting an answer without using any of these]

Here's what I got so far:

If $G$ is cyclic then we are done otherwise, we can assume that it is not cyclic which means every non-identity element must be of order $p$ or $q$.

Case $(1)$ if there exists $a\in G$ such that $o(a) = p$ and if there also exists an element of order $q$ then we are done. So we can assume that every non-identity element is of order $p$. Now pick $b\in G$ such that $b\notin \langle a \rangle$ then $o(b) = p$ and $\langle a \rangle\cap\langle b \rangle =(e)$

So we have $\langle a\rangle \langle b\rangle\subset G$ but $o(\langle a \rangle \langle b \rangle) = \dfrac {o(\langle a \rangle)o(\langle b \rangle)}{o(\langle a\rangle \cap \langle b\rangle)} = p^2$ but $p^2 > pq$ [since $p>q$] so we got a contradiction.

Give me a hint for the second case and correct me if my argument for the first case is wrong

Assume that every non-identity element generates a cyclic group of order $q$, the smaller of the primes.

Conjugacy is an equivalence relation on a group. So, we should be able to partition the group into its equivalence classes. The size of the equivalence class an element belongs to is the index of the centralizer of the element. Why? Fix $x\in G$. Make a homomorphism from $G \rightarrow G$ by sending $g \rightarrow xgx^{-1}$. The size of the equivalence class is the order of the image. What is the kernel of this map?

If the centralizer is of order $p$ or $pq$, we are done. Assume every centralizer is of order $q$, the index of the centralizer is $pq/q=p$. Every element would belong in a equivalence class of size $p$, except for the identity element.

A simple cardinality calculation shows that $pq= kp+1$, where represents the number of equivalence classes. However, this is absurd and therefore, not every subgroup of order $q$.