What does "maximum order elements to mod n" mean for a number n without primitive roots modulo n?

I apologize because probably this is trivial, but I do not understand the concept:

"maximum order elements to mod n for n".

This is the context: in the Wikipedia in the primitive roots modulo n page there is a table in the section "Table of primitive roots" (link) saying:

"The following is a list about maximum order elements to mod n for $n \le 36$,

And then the table also explains:

"maximum order elements to mod n (for ns with "*", the maximum order of n does not equal to the Euler totient function of n, so there are no primitive roots mod n, for other ns, they are primitive roots mod n)

Basically, I would like to understand the definition and how to calculate the maximum order elements to mod n for those numbers n that do not have primitive roots mod n.

For instance, according to the explanation in the Wikipedia, for $n=8$ the maximum order element to mod 8 are $\{3,5,7\}$, and $n=8$ does not have primitive roots modulo 8, but I do not understand how they are calculated.

UPDATE
As far as I can see, it would be as follows, but if somebody could confirm this, it would be very appreciated, because I do not see it clearly:

For instance:

$3^1 = 3 \equiv 3 \pmod8$

$3^2 = 9 \equiv 1 \pmod8$

$3^3 = 27 \equiv 3 \pmod8$

$3^4 = 81 \equiv 1 \pmod8$

$3^5 = 243 \equiv 3 \pmod8$

$3^6 = 729 \equiv 1 \pmod8$

$3^7 = 2187 \equiv 3 \pmod8$

So in this case the length of the cycle of the mods is 2 (only 1,3 and the again 1,3, etc.) and that is smaller than the totien function $\varphi(8)=4 \gt 2$ so 3 is not a primitive root modulo 8. Is this correct?

If it is correct then the only way to calculate the "maximum order elements to mod n" for a number n without primitive roots modulo n is as above, making all the possible exponents and deciding according to the results. Is that right?

Thank you!

UPDATE: the explanation in the answers worked like a charm, here is the Python code (very brute force but works, be aware that the variable "value" is the value for n):

from gmpy2 import gcd
def first_max_order_elem_mod_n(value): 
    lo = []
    for i in range (1,value):
        if gcd(value,i)==1:
            myexp = 1
            while ((i**myexp)%value)!=1:
                myexp = myexp + 1

            lo.append([i,myexp])

    bigger = 0
    current_pos = 0
    for k in lo:
        if k[1]>bigger:
            current_pos = k[0]
            bigger = k[1]
    return current_pos

Answer

In ${\mathbb{Z}/n}^{\times}$, look at the set of $k$, $1\le k \le n$, for which $(k,n) = 1$ (multiplicative units in $\mathbb{Z}/n$). Calculate their orders (the smallest positive integer $i$ s.t. $k^i = 1$). Denote by $o$ the largest $i$ you get from your order calculation for all units. Then the right table entry is $o$, the left those $k$ with order $o$. In your example case for $n=8$, for all units $k$ different from 1, $k^2 =1$ mod $n$; and the units other than 1 are $\{3,5,7\}$.