9
$\begingroup$

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!

$\endgroup$
9
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks for your help! I'm reading through your email as well and this makes a lot more sense. Thanks! $\endgroup$ – HyperNeutrino Aug 3 '17 at 16:16
  • $\begingroup$ 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. $\endgroup$ – HyperNeutrino Aug 3 '17 at 18:08
  • $\begingroup$ @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 $\endgroup$ – Max Alekseyev Aug 3 '17 at 19:48
  • $\begingroup$ Ah okay. That makes sense, thanks. $\endgroup$ – HyperNeutrino Aug 3 '17 at 21:35
  • $\begingroup$ By $x \div y$, you're referring to multiplication of $x$ by the multiplicative inverse of $y$ modulo $p$, right? $\endgroup$ – HyperNeutrino Aug 5 '17 at 0:13
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – HyperNeutrino Aug 3 '17 at 0:53
  • $\begingroup$ Oh so the bases of the exponents need to be adjacent as well? Thanks $\endgroup$ – HyperNeutrino Aug 3 '17 at 1:00
  • $\begingroup$ 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? $\endgroup$ – HyperNeutrino Aug 3 '17 at 1:06
  • $\begingroup$ @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. $\endgroup$ – Sriotchilism O'Zaic Aug 3 '17 at 1:33
  • $\begingroup$ Ah okay thanks. I'll keep trying to figure it out. Thanks for the help. $\endgroup$ – HyperNeutrino Aug 3 '17 at 1:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.