All generators for modulo p
This is not true. In particular, consider $4\in (\mathbb{Z}/5\mathbb{Z})^\times$. We have that $4^2 = 16\equiv 1\bmod 5$, so $\langle 4\rangle = \{1, 4\}$ is not the full group.

The theorem you mention is known as Fermat's little theorem, and it states:


  $\forall x\in (\mathbb{Z}/p\mathbb{Z})^\times$, $x^{p-1}\equiv 1\bmod p$


As you mention, all elements satisfy this. Generators are distinguished in that they satisfy this, but for all $k &lt; p-1$ they satisfy $g^k\not\equiv 1\bmod p$ (so $p-1$ is the "smallest exponent" such that $g^{p-1}\equiv 1\bmod p$). As a hint, you don't need to check all $k &lt; p-1$ (and you can in fact check a single $k &lt; p-1$ which will work in all cases).