Let $p$ be a prime dividing the order of $G.$ Let $\mathcal{P}$ be a set of $p$-tuples of elements from $G$ whose product equals the identity in $G.$ That is,

Step 1: $|\mathcal{P}| = |G|^{p-1}.$

Our goal is to count the size of the set $\mathcal{P}$ in terms of the size of $G.$

How would we construct a tuple in $\mathcal{P}?$ Since the only requirement is that the product of all entries $g_i$ equals the identity, we can freely choose any of the first $p-1$ entries in $(g_1,g_2,\cdots ,g_p)$ from the $|G|$ elements in the group $G.$ Then, we must have the last element be $g_p=(g_1g_2\cdots g_{n-1})^{-1}$ to ensure that $g_1g_2\cdots g_p=1_G.$ Therefore, we have fo $|\mathcal{P}| = |G|^{p-1}.$

Step 2: Define an Equivalence Relation on $\mathcal{P}$

Let $\sim$ be the relation on $\mathcal{P}$ such that $x\sim y$ if $y$ is a cyclic permutation of $x,$ for $x, y\in \mathcal{P}.$ For example, $(a,b,c),\;(b,c,a),\;(c,a,b)$ are cyclic permutations of one another. We want to show two things: (i) that $\sim$ is a well-defined relation on $\mathcal{P}$ and (ii) that $\sim$ is an equivalence relation.

Step 2a: $\sim$ is Well-Defined on $\mathcal{P}$

By well-defined, we mean that given $x\in \mathcal{P},$ any cyclic permutation of $x$ is also in $\mathcal{P}.$ Indeed, let $x=(g_1,g_2,\cdots ,g_p)\in \mathcal{P}.$ Then, $g_1g_2\cdots g_p=1_G.$ We will show that $g_pg_1g_2\cdots g_{p-1}=1_G.$

Applying this argument multiple times demonstrates that any cyclic permutation of $x=(g_1,g_2,\cdots ,g_p)$ is also in $\mathcal{P}.$

Step 2b:¹ $\sim$ is an Equivalence Relation on $\mathcal{P}$

Recall that to show that $\sim$ is an equivalence relation, we must show that $\sim$ is reflexive, symmetric, and transitive. That is, we must show that $x\sim x$ for all $x\in \mathcal{P},$ if $x\sim y,$ then $y\sim x.$ and finally if $x\sim y$ and $y\sim z,$ then $x\sim z.$

This is left to you, as a fun exercise!

Step 3: Consider the Sizes of the Equivalence Classes²

We claim that the equivalence classes under $\sim$ have order $1$ or $p.$ Indeed, note that if $g_i = g$ for all $i$ and $g^p = 1_G,$ then the equivalence class of $x=(g,g,\cdots ,g)$ has size equal to $1.$ If there is at least one instance for which $g_i\neq g_{i+1},$ then the following $p$ elements are in the same equivalence class:

Which has order $p.$

Step 4: $G$ has an element of order $p.$

Note that the equivalance class of the element $\mathbb{1}:= (1_G,1_G,\cdots,1_G)\in \mathcal{P}$ has size equal to 1. Recall that equivalence classes partition a set; here, $\sim$ partitions $\mathcal{P}$ into equivalence classes. In particular, the order of $G$ is equal to the sum of the sizes of its equivalence classes. Suppose, for the hope of a contradiction, that there are no other elements in $\mathcal{P}$ with order $p$ other than the one containing $\mathbb{1}.$ Thus, there is only one equivalence class of order $1,$ the one containing $\mathbb{1}.$ That is, every other equivalence class has order $p,$ by Step 3. We deduce that

Where there are $k$ equivalence classes of order $p,$ and the $1$ is from the element $(1_G,1_G,\cdots,1_G)\in \mathcal{P}$ which is in its own equivalence class. Cool! We have reached our contradiction! By assumption, $p$ divides $|G| = 1+pk.$ But this implies that $p\mid 1!$ Impossible!

Thus, our assumption that there are no other elements in $\mathcal{P}$ with order $p$ other than the one containing $\mathbb{1}$ is false. Consequently, another equivalence class contains only one element: $(g,g,\cdots ,g).$ Hence, $g^p=1.$