Generator of group, find the inverse, solve equation Given the prime number $p=101$


*

*Find a generator of the group $\mathbb{Z}_p^{\star}$. How many generators of $\mathbb{Z}_p^{\star}$ are there? Find $5$ generators.

*Find the inverse of $\overline{83}$ at the group $\mathbb{Z}_p^{\star}$.

*Solve the equation $\overline{83} x=\overline{10}$ at the group $\mathbb{Z}_p^{\star}$.

*We have that $\mathbb{Z}_{101}^{\star}=\{ 1,2, \dots, 100 \} $. So do we have to check if it holds that $1^{100}\equiv1 \mod{101}, 2^{100}\equiv 1 \mod{101}, 3^{100} \equiv 1 \mod{101}, \dots$ and if this holds for a number we know that it is a generator of the group? Or am I wrong?
I found the following proposition:
The number of generators of $\mathbb{Z}_p^{\star}$ is $\phi(p-1) \geq \frac{p}{\log{\log{p}}}$. Does this mean that we cannot find the exact number but there is only a lower bound?

*We want to find a $x \in \{1,2 , \dots, 100 \}$ such that $83 \cdot x \equiv 1 \mod{101}$, right? Is the only way to find such a $x$ to check all the products $83 \cdot 1, 83 \cdot 2, \dots$ till we find one that is equivalent to $1$ modulo $101$?
 A: It is a theorem that $a^{100} \equiv 1 \mod{101}$ will hold for every $a$ not divisible by 101.  Being a generator means that 100 is the least such exponent, so that $a^{i} \not\equiv 1\mod{101}$ for any $1 \le i< 100$.  As an example, 10 is not a generator because $10^2 \equiv -1 \mod{101}$ and thus $10^4 \equiv (-1)^2 = 1\mod{101}$.  
To make it easier than checking by brute force that $a^{i} \not\equiv 1\mod{101}$ for any $1 \le i< 100$, use the fact that the multiplicative order (the least number $i$ such that $a^{i} \equiv 1\mod{101}$) will be a divisor of $100$.  This means that $a$ is a generator if and only if $a^{20} \ne 1 \mod{101}$ and $a^{50} \ne 1 \mod{101}$.
Note that $\phi(p-1)$ can be explicitly calculated if a prime factorization for $p-1$ is known.  In general we have $\phi(n) = n\Pi_{q \mid n} (1 - 1/q)$, where $q$ ranges over the prime divisors of $n$.  Here we have $\phi(100) = 100(1-1/2)(1-1/5) = 40$.
The traditional way of computing multiplicative inverses is using the extended Euclidean algorithm to solve for $83a + 101b = 1$, which will generally be substantially faster than trying every possible inverse.
A: First of all, with $p$ prime, for any $a$ we have $a^{p-1} \equiv 1 \mod p$ by Fermat's little theorem.  But it is possible for some values $a$ to not be generators, if $a^{q-1} \equiv 1 \mod p$ with $q < p-1$.  For example, in mod $7$, $3$ is a generator, but $2$ is not since $2^3 = 8 \equiv 1$. So the answer to  "or am I wrong" is yes, you am wrong.
Secondly, $\phi(p-1)$ is the exact number of generators; for that purpose, the interesting lower bound is irrelevant.  It is as easy to find  $\phi(p-1)$ as it is to factor $(p-1)$.  In general that is not easy, but for the case $p=101$ it is easy. $$100 = 2^2 \cdot 5^2\\\phi(100) = 100 \left( 1 - \frac12 \right) \left( 1 - \frac15 \right) = 40$$ 
So there are 40 generators.
If we find one generator $g$, then any number $g^n$ will also be a generator if $n$ is relatively prime to $100$. So if we find one generator, it  will be easy to find 5 generators. 
