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.$
For the second question, notice that in the proof $[H:K]=k$, so $k\mid |H|\mid |G|$ since $H\leq G$. So any prime divisor of $k$ is also a divisor of $|G|$. But every prime divisor of $k$ divides $(p-1)!$, hence is less than $p$. Since $p$ is the least prime dividing $|G|$, $k$ cannot have any prime divisors, else we would have a prime divisor of $|G|$ strictly less than $p$. But the only positive integer with no prime factors is $1$, so $k=1$.
But then $[H:K]=1$, and since $H$ and $K$ are finite groups, that means $|H|=|K|$, so necessarily $H=K$.
Added: For the first question, recall that if $q$ is a prime, and $q\mid ab$, then either $q\mid a$ or $q\mid b$. This is Euclid's Lemma. So if $q$ is a prime factor of $(p-1)!=1\cdot 2\cdot 3\cdots p-1$, we must have $q\mid j$ for some $j=1,2,\dots,p-1$. So necessarily $q<p$.
If you're not familiar with that property of primes, another way to see this is to observe that the prime factorization of $(p-1)!$ is the product of the prime factorizations of $1,2,\dots,p-1$. But for each $1\leq j\leq p-1$, the prime factorization of $j$ must not have any prime factors greater or equal to $p$. So the prime factorization of $(p-1)!$ consists only of primes less than $p$.
Best Answer
For $p=4$ you have tuples such as $(1,2,1,2)$ which have order $2$.
The point is that the cyclic group of order $p$ acts on the set of $p$-tuples by cyclic permutations. When $p$ is prime, the size of each orbit of this action is a factor of $p$, so is $1$ or $p$. When $p$ is not prime, then one gets orbits whose size is a proper factor of $p$, and the argument collapses.