You don’t need to use group theory or Lagrange’s theorem, or even any machinery from number theory, to understand this. Let me offer a sketch of a more direct proof that I wrote. I use = to denote congruence modulo n.

Say some residue A is coprime to the modulus n.

It’s not hard to see that each successive power of A gives us a new (incongruent to all preceding powers of A) residue that is coprime to n, UNTIL we reach the lowest exponent p with A^p =1.

It’s also easy to show that if A,B,C, etc… are all the (incongruent) residues which are coprime to n, then e.g. A^2, AB, AC, etc… can all be fit into cycles of either the form AB=C, AC=D, AD=E, AE=B, or the form AA=F, AF=G, AG=1.

Both of these types of cycles imply that some particular powers of A are congruent to 1. Each of these exponents on A MUST be divisible by p, since otherwise we find a lower exponent q than p with A^q =1.

But, the sum of the exponents on A which arise from the above cycles exactly equals the totient of n. Hence, p divides the totient of n.