Conditions for maximum period of quadratic congruential method (PRNG) $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"):


  
  $c$ is relatively prime to $m$
  $d$ and $a-1$ are both multiples of $p$, for all odd primes $p$ dividing $m$
  $d \equiv a-1$(mod 2) when $2|m$; $d$ is even and $d \equiv a-1$(mod 4) when $4|m$
  $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.  


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
&amp;\equiv dx^2+2dd'ax + c\\
&amp;\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.