# Explanation of OEIS:A000236 - Residue Classes

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!

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

• Thanks for your help! I'm reading through your email as well and this makes a lot more sense. Thanks! – HyperNeutrino Aug 3 '17 at 16:16
• I have a question about your last paragraph. How is $r$ generated? $p$ is selected to maximise $\gcd(p-1,n)$ and $n$ is the sequence index/input but it isn't clear to me where $k$ and $r$ come from. – HyperNeutrino Aug 3 '17 at 18:08
• @HyperNeutrino: Nothing is generated here, these are just definitions. I described just one desirable property of $p$, but an optimal choice of $p$ for A000236(n) is a separate big question. For properties of primitive roots, see en.wikipedia.org/wiki/Primitive_root_modulo_n – Max Alekseyev Aug 3 '17 at 19:48
• Ah okay. That makes sense, thanks. – HyperNeutrino Aug 3 '17 at 21:35
• By $x \div y$, you're referring to multiplication of $x$ by the multiplicative inverse of $y$ modulo $p$, right? – HyperNeutrino Aug 5 '17 at 0:13

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

$$x \equiv a^n \mod p$$

and

$$y \equiv b^n \mod p$$

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.

• I have a question: For power 2, there exists 23 such that 1 and 2 are in the power residue class (1 ** 2 % 23 == 1, 5 ** 2 % 23 == 2). What's with that? – HyperNeutrino Aug 3 '17 at 0:53
• Oh so the bases of the exponents need to be adjacent as well? Thanks – HyperNeutrino Aug 3 '17 at 1:00
• Hm. So then that means that for power 2, there exists a prime with adjacent a and b such that a squared mod the prime is 3 and b squared mod the prime is 4. However, I can't seem to find such a prime. Do you have any idea? – HyperNeutrino Aug 3 '17 at 1:06
• @HyperNeutrino That was wrong. I should read my own explanation. When I have access to a computer I'll figure this out. Sorry for the confusion I am surely causing. My answer should be correct, disregard my comments. – Sriotchilism O'Zaic Aug 3 '17 at 1:33
• Ah okay thanks. I'll keep trying to figure it out. Thanks for the help. – HyperNeutrino Aug 3 '17 at 1:34