Explanation of OEIS:A000236 - Residue Classes

The answer of @EpsilonNeighborhoodWatch is not quite correct.

First, it makes an impression that prime $p$ is selected independently for each pair of $x,y$, while in fact prime $p$ should be the same for all elements $1,2,\dots,m$.

Second, the $n$-th power residue class is defined as follows. Two non-zero residues $x$ and $y$ modulo $p$ belong to the same $n$-th power residue class iff $x/y\equiv z^n\pmod{p}$ for some $z$ (in other words, $x/y$ is an $n$-th power residue modulo $p$).

Equivalently, the $n$-th power residue class can be defined via a primitive root $r$ modulo $p$ as follows. Let $x\equiv r^k\pmod{p}$ (i.e., $k$ is the discrete log of $x$ base $r$ modulo $p$). Then the $n$-th power residue class of $x$ is uniquely determined by the value $k\bmod\gcd(p-1,n)$. In particular, there exist exactly $\gcd(p-1,n)$ different $n$-th power residue classes modulo $p$. To maximize the number of classes for a given $n$, one needs a prime $p$ such that $n\mid p-1$, giving the total of $n$ $n$-th power residue classes modulo $p$.