Help understanding basic definition involving Primitive Roots I need some help understanding the language of the following theorem and help for how to prove it. Please note that my understanding of Number Theorem is only at the most basic and elementary level.

For a prime $p$ and a natural number $d$, at most $\phi(d)$ incongruent integers modulo $p$ have order $d$ modulo $p$

So the order of a modular congruence is the smallest value $k$ which satisfies $a^k\equiv 1 \pmod{n}$. That is, the order of modulo $n$ is the value $k$. The word "incongruence" for Number Theory means that two numbers have a different remainder when divided by the same number. So "incongruent integers modulo $p$" represents $a\neq b\pmod{p}$.
Where I'm confuse is the phrase "have order $d$ modulo $p$". I think it may be telling me that the incongruent integers $a$ and $b$ have the same order  $d$ when in the form $a^d\equiv 1\pmod{p}$ and $b^d\equiv 1\pmod{n}$. Is this correct?
Following that, what exactly do I need to prove in this theorem? Thank you for any help.
 A: Your nomenclature is a bit off.
“Order” does not refer to a congruence, it refers to an element. Here, “the (multiplicative) order of $a$ modulo $n$” is the smallest positive integer $k$ such that $a^k\equiv 1\pmod{n}$. The “order modulo $n$” is attached to $a$, not to a congruence. (You could say it attaches to a congruence class, but you aren’t using that language in your post.)
Two integers $a$ and $b$ a “congruent modulo $n$” if and only if $a\equiv b\pmod{n}$. They are “incongruent modulo $n$” if and only if this does not occur, that is, $a\not\equiv b\pmod{n}$. Depending on how you defined “congruent modulo $n$”, that could mean to you “different remainders when divided by $n$”, or it could mean “$n$ does not divide the difference $a-b$”.
The statement says: there are at most $\phi(d)$ integers $a_1,\ldots,a_{\phi(d)}$, such that:

*

*$a_i\equiv a_j\pmod{p}$ if and only if $i=j$; (equivalently, if $i\neq j$ then $a_i\not\equiv a_j\pmod{p})$ and

*The order of $a_i$ modulo $p$ is $d$ for $i=1,\ldots,\phi(d)$.

You cannot have a list of more than $\phi(d)$ integers that satisfy both 1 and 2 above.
What you need to show is that if you already have a list with $\phi(d)$ integers satisfying 1 and 2 above, and $b$ is any integer such that the order of $b$ modulo $p$ is $d$, then $b$ must be congruent to (at least, but because of item 1, exactly) one of $a_1,\ldots,a_{\phi(d)}$. (Or a statement equivalent to this assertion.).
