Below is a presentation that I devised to clarify McKay's proof (from an old sci.math post).
Lemma $\ $ If $g$ is an element of a group and $p$ is prime then $g^p = 1\:\Rightarrow\:$ $g$ has order $p$ or $1$.
Proof $\ $ If $g$ has order $n$ then $g^n = g^p = 1 \Rightarrow\ g^{(n,p)} = 1.$ But $(n,p) = p$ or $1$ by $p$ prime.
Theorem $\ $ Suppose that $p$ is prime, $G$ is a finite group of order $n,$ and
$R =$ #$p$'th roots of $1$ in $G,$ i.e. $\: R = \#\{ g \in G :\ g^p = 1 \}.\:$ Then
$$ R \equiv n^{p-1}\ ({\rm mod}\ p),\ \ {\rm and}\ \ R > 1 \iff p\mid n$$
Proof $\ $ Let $S$ be the set of all $p$-tuples of elements from $G$
whose product is $1,$ i.e.
$$ S = \{ (g_1,g_2,\ldots,g_p) :\ g_1 g_2\cdots g_p = 1,\ g_i \in G \}$$
Let $F$ be the cyclic rotation on $p$-tuples
$$ F(\color{#C00}{g_1},g_2,\ldots,g_p) = (g_2,g_3,\ldots,g_p,\color{#C00}{g_1}) $$
Clearly $F^p = 1,$ so $F$ is a permutation on $S.$ Recall that
a permutation $F$ decomposes into disjoint cycles (orbits)
$\:\langle F\rangle s = \{F^k s :\, k \in \Bbb Z\},$ the classes of the equivalence
relation $s \sim t \!\iff\! s = F^k t,$ for some $k \in \Bbb Z.$ Thus the cycles
of $F$ form a partition $S = \langle F\rangle s_1 \cup \cdots \cup \langle F\rangle s_m.$
Consider the permutation $F$ restricted to some cycle $C.$
Notice the order of $F$ on $C$ is the cycle length $n$ of $C.$
But since $F^p = 1,$ the lemma implies that $n = p$ or $1.$
So $S$ decomposes into disjoint cycles of length $p$ or $1,$ yielding one count for $|S|$. For another, notice
$S$ has $n^{p-1}$ elements since, after freely choosing the
first $p-1$ elements of a $p$-tuple in $S,$ the last element
must be the inverse of the product of the others. Comparing both counts
$$ |S| = n^{p-1}\! =\, Q\,p + R,\ \ \ Q = \#p{\rm\!-\!cycles,}\ \ R = \#1{\rm\!-\!cycles} $$
A $\:1$-cycle has $Fs = s,$ so $s$ has all entries identical,
say $g,$ so $g^p = 1,$ i.e. $g$ is a $p$'th root of $1$ in $G$
iff $g$ is a $1$-cycle of $R.$ Hence mod $p: n^{p-1} = R,$
the number of $p$'th roots of $1$ in $G.$ If $p\mid n$ then $p\mid R.$
But $R > 0$ since always $1^p = 1,$ hence $R \ge p > 1.$
Conversely, if $R > 1$ then $G$ has $g \ne 1$ with $g^p = 1,$
so the lemma implies $g$ has order $p.$ But also $g^n = 1,$
so $p\mid n.\ \ $ QED
Corollary 1 $\ $ (Cauchy's Theorem) $\ $ If a group $G$ has order $n$
divisible by a prime $p$ then $G$ has a subgroup of order $p.$
Proof $\ \ p\mid n\:$ so the theorem implies $R > 1,$ i.e. $G$ has a
$g \ne 1$ with $g^p = 1.$ The lemma implies that $g$ has order $p,$
so $g$ generates a cyclic subgroup $\langle g\rangle$ of order $p.$
Corollary 2 $\ $ (F$\ell$T: Fermat's $\ell$ittle Theorem) $\ $
If $p$ is prime and $p\nmid n$ then $n^{p-1} \equiv 1 \pmod p.$
Proof $\ $ Apply the theorem to any (e.g. cyclic) group of order $n.$
Corollary 3 $\ \ $ Theorem $\Rightarrow$ Lemma
Proof $\ $ Suppose $g^p = 1,\ g \ne 1.$ Let $n$ be the order of $g.$
Apply the theorem to the cyclic group $\langle g\rangle$ generated by $g.$
Note $g^p = 1^p = 1\:\Rightarrow\: R > 1,$ so $p\mid n,$ therefore $n = p.$
Best Answer
For the backwards direction, let $s=|G|$, $p_1^{e_1}\cdot \cdots \cdot p_m^{e_m}$ be the prime factorization of $s$, and $H_d$ denote the subgroup of $G$ of size $d$. One of my previous results implies that for each $i$, $H_{p_i^{e_i}}$ is cyclic (normal in $G$). Furthermore, since these groups are normal with relatively prime sizes, it follows that $H_{p_i^{e_i}}\cap H_{p_j^{e_j}}$ is trivial if and only if $i\neq j$. Thus, for each $i$ and $j$, the elements of $H_{p_i^{e_i}}$ and $H_{p_j^{e_j}}$ commute. Now for each $i$, set $g_i\in H_{p_i^{e_i}}$ to be an element of order $p_i^{e_i}$. Since the elements $g_1,\dots,g_m$ commute with each other, it follows that $$\prod_{i=1}^{m}g_i$$ will have order $p_1^{e_1}\cdot \cdots \cdot p_m^{e_m}=s$.
Here I am using the fact that if $x$ and $y$ commute and if $\text{ord}(x)=s$ and $\text{ord}(y)=t$, then $\text{ord}(xy)=\text{lcm}(s,t)$.