Explanation of OEIS:A000236 - Residue Classes

Question

I'm looking at OEIS:A000236, whose definition states:

Maximum m such that there are no two adjacent elements belonging to the same n-th power residue class modulo some prime p in the sequence 1,2,...,m (equivalently, there is no n-th power residue modulo p in the sequence 1/2,2/3,...,(m-1)/m).

I can't quite understand this. Here's what I have so far:

• The power residue class $b=[a]_m$ represents all $b$ for which $a=b \pmod m$ (thanks to Inceptio's answer). This represents all possible remainders of $a \div m$.
• A necessary and sufficient condition for $t \in R$ where $R$ consists of the $n$th power residues $\pmod p$ is that $x^k \equiv t \mod p$ is solvable ($x$ exists). Source: CMS
• If $z$ is the maximum value such that there are no two adjacent elements in 1, 2, ..., m belonging to the same power residue class, then that means the $z$ and $z+1$ belong to the same power residue class

This leads me to believe that if two numbers $z_1, z_2$ are in the same $n$th power residue class $\pmod p$, it means that there exist $y_1, y_2$ such that $y_1^n \equiv z_1 \pmod p$ and $y_2^n \equiv z_2 \pmod p$

If this is correct, great. If it is incorrect, could someone explain to me where my ideas are wrong and what this sequence means? Thanks!

Answer 1

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$.

Answer 2

This answer is not entirely correct, as pointed out by @HyperNeutrino. I don't know what the correct reading is so I will leave this up for posterity. Max Alekseyev has another answer here which may be correct, however I don't understand his explanation.

Let's break this down a bit.

You are given $n$ as the placement in the sequence and you are looking for some $m$. $m$ is the largest number such that no two members of the sequence $1, 2, 3, 4, ... , m-1, m$ satisfy a specific property, $P(x,y)$.

$P(x,y)$ is true if $x$ and $y$ belong to a power residue class mod some prime. It looks like in your question you have confused residue classes and power residue classes. In general the residue class of some function mod $p$ is all the values that function can express mod $p$, or all the remainders that function can have when divided by $p$. For a power residue class that function is $n$th powers (our index) that means that $f:\mathbb{N}\mapsto\mathbb{N} : f(x) = x^n$.

The definition also stipulates a specific variety of power residue classes. Classes where our $p$ is prime.

This means that $P(x,y)$ is true if there exists some prime $p$ such that there exists some $a$ and $b$ such that

\begin{equation} x \equiv a^n \mod p \end{equation}

and

\begin{equation} y \equiv b^n \mod p \end{equation}

---

To state this in a way that I find more intuitive:

For some $n$, $m$ is the smallest number such that $P(m,m+1)$.

I don't know why the OEIS goes out of its way to define a sequence when it is pretty clear that the first sequence with adjacent members satisfying the property must always satisfy with the last two members, thus we only really care about $m$ and $m+1$.

Hopefully this helps.