$X_{n} = (d^2X_{n-1} + aX_{n-1} + c) \operatorname{mod} m$

Knuth lists out the necessity and sufficiency of 4 conditions (Exercise 8 in page 49 of "The art of computer programming Vol.II"):

  1. $c$ is relatively prime to $m$
  2. $d$ and $a-1$ are both multiples of $p$, for all odd primes $p$ dividing $m$
  3. $d \equiv a-1$(mod 2) when $2|m$; $d$ is even and $d \equiv a-1$(mod 4) when $4|m$
  4. $d \not \equiv 3c$ (mod 9) when $9|m$

Knuth writes in the answer to exercise 8:

If $p \leqslant 3$, it's easy to establish the necessity of condition (iii) and (iiii) by trial and error method

I do try to find my own way to prove (the necessity of) condition (iii) and (iiii). Here's how i prove the first one:

Assume $m=p^e$. Firstly, we consider the case when $p=2,e=1$

So, the sequence $X_n$ with ($X_0 = 0$ and $m=2$) has the period of $2$ when:
$$X_2 = X_0 = 0 $$

We can prove: $X_2=dc+a+1 \operatorname{mod}$ 2 (due to the relatively prime $c$)

Obviously, we have: $$d \equiv a-1 (\operatorname{mod} 2)\space \tag1$$

If $e \geqslant 2$ then $4|m$. The same sequence $X_n$ with $(X_0=0,m=4)$ must have the period of 4 which means: $X_0\not=X_1\not=X_2\not=X_3$

$X_2 \not=X_0$. So, $X_2 = 2$ and $X_3 \not=X1$. The fact then implies: $$aX_2 \not\equiv 0 (\operatorname{mod} 4)\space\tag2$$

Due to (1), (2), $a \operatorname{mod} 4$ and $d \operatorname{mod} 4$ can only adopt odd and even values. After some trials on $X_2 = dc + a + 1 \operatorname{mod} 4= 2$ (c is odd), we easily prove: $d \equiv a-1(\operatorname{mod} 4)$

I have also proved the condition (iiii) by my "trial and error method" but i'm not sure if they are what Knuth mentions. So my first question:
1. What's exactly "trial and error method" applying for this situation?

Finally, the proof of condition (ii) confuses me:

If $d \not\equiv 0(\operatorname{mod} p)$ then $dx^2+ax+c \equiv d(x+a_1)^2 + c_1(\operatorname{mod} p^e)$ for some integers $a_1$, $c_1$ and for all integers x

$d\not\equiv 0 (\operatorname{mod} p)$ leads to d relatively prime to $p^e$. But i can't go on any further from this.

  1. Why does $dx^2+ax+c\equiv d(x+a_1)^2 + c_1(\operatorname{mod} p^e)$ hold when $d \not\equiv 0(\operatorname{mod} p)$ ?

What's exactly "trial and error method" applied in this situation?

$\newcommand{\mymod}{\operatorname{modulo}}$As I understand, "trial and error method" here means checking all cases from a few simple natural or known perspectives until we have found a satisfactory solution or proof. It is useful and efficient in this situation because the number of cases $\mymod 2$ or $\mymod 4$ or $\mymod 9$ is very small.

What you have done seems pretty good.

Why does $dx^2+ax+c\equiv d(x+a_1)^2 + c_1(\mymod{p^e})$ hold when $d \not\equiv 0\,(\mymod{p})$ ?

Prime $p\not=2$ since it has been assumed $p\ge5$. Since $d \not\equiv 0\,(\mymod p)$, $2d$ and $p^e$ are relatively prime, which implies $2d$ is invertible $\mymod p^e$. Let $(2d)d'\equiv1\,(\mymod p^e)$ fro some $d'$. Then

$$\begin{aligned} dx^2+ax+c &\equiv dx^2+2dd'ax + c\\ &\equiv d(x+d'a)^2 -d(d'a)^2+c\ (\mymod p^e)\\ \end{aligned}$$

Letting $a_1=d'a$ and $c_1=-d(d'a)^2+c$, we are done.

| cite | improve this answer | |

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.