Suppose I have a group $G$ of order $|G|=pq, q < p$ where $p,q$ are primes. Also, suppose that $a$ has order $p$, then prove that for any $b\not \in \langle a \rangle$, the order of $b$ is not $p$.
I know there is a way to do it with Sylow's theorems, but since we didn't cover Sylow theorems, I was hoping for another approach perhaps?
On
More generally, if $q$ is the smallest prime dividing $|G|$, then any subgroup $H$ of index $q$ is normal.$^1$
Now in the given problem, what can you say about the image of $b$ in $G/\langle a\rangle$?
$^1$ Namely, $G$ acts by left multiplication on the set $X=\{\,gH\mid g\in G\,\}$ of the $q$ cosets, which gives us a homomorphism $\phi\colon G\to S_q$. Clearly, $\ker\phi\subseteq H$. Note that $H$ leaves the point $H\in X$ fixed, hence is in fact mapped by $\phi$ into $S_{q-1}$. As $|S_{q-1}|$ is co-prime to $|G|$, we must have $H\subseteq \ker\phi$.
I'll make my comment into an answer.
If $b \not\in \langle a \rangle$ and $o(b)=p$, then $\langle b \rangle \cap \langle a \rangle = \{1\}$, and so $|\langle b \rangle\langle a \rangle|=p^2 > |G|$, contradiction.
Since you are looking for an elementary proof, I will justify the claim that $|\langle b \rangle\langle a \rangle|=p^2$. If not, then there exist $i,j,k,l \in [0 .. p-1]$ with $(i,j) \ne (k,l)$ and $a^ib^j = a^kb^l$, but then $a^{i-k} = b^{l-j}$ is a nontrivial element of $\langle b \rangle \cap \langle a \rangle$.
There is a general result that, for finite subgroups $A$ and $B$ of a group $G$, we have $|AB| = |A||B|/|A \cap B|$