Problem: Let $p$ be an odd prime number. Suppose $P$ and $Q$ are polynomials with integer
coefficients such that $P(0)=Q(0)=1$, there is no nonconstant polynomial
dividing both $P$ and $Q$, and
\[
  1 + \cfrac{x}{1 + \cfrac{2x}{1 + \cfrac{\ddots}{1 +
  (p-1)x}}}=\frac{P(x)}{Q(x)}.
\]
Show that all coefficients of $P$ except for the constant coefficient are
divisible by $p$, and all coefficients of $Q$ are \emph{not} divisible by $p$.

Solution: \paragraph{Solution 1.}
We first make some general observations about rational functions represented
through continued fractions.

\begin{claim*}
  Let $a_1$, $a_2$, \dots, be a sequence of nonzero integers. Define the
  sequence of polynomials $P_1(x) = 1$, $P_2(x) = 1 + a_1x$, and
  \[P_{k+1}(x) = P_k(x) + a_kxP_{k-1}(x)\]
  for $k\geq 1$.
  Then the following properties hold for all $k\geq 0$:
  \begin{itemize}
    \item $P_k(0) = 1$,
    \item $\gcd(P_{k+1}, P_{k}) = 1$, and
    \item $\deg P_k = \left\lfloor k/2\right\rfloor$.
    \item \(
      1 + \cfrac{a_kx}{1 + \cfrac{a_{k-1}x}{1 + \cfrac{\ddots}{1 + a_1x}}}=\dfrac{P_{k+1}(x)}{P_k(x)}.
    \)
  \end{itemize}
\end{claim*}

\begin{proof}
  These all follow by induction.
\end{proof}

With the setup of the claim, the polynomials $P$ and $Q$ in the problem are
exactly $P_{p}$ and $P_{p}$ for the sequence $a_1=p-1$, $a_2=p-2$, \dots, $a_{p-1}=1$.
From here, we will define $P$ and $Q$ in terms of this recurrence
and make two transformations on the $a_i$.

First, subtract $p$ from each $a_i$ so we now have $a_1 = -1$, $a_2 = -2$,
\dots, $a_{p-1} = -(p-1)$. The coefficients of $P$ and $Q$ only have changed
by a multiple of $p$. The claim also shows that $P(0)=Q(0)=1$, $\gcd(P, Q)=1$,
and the degrees of $P$ and $Q$ have not changed, i.e.\ no leading terms have been
added or removed. Therefore it is equivalent to work with this sequence instead.

Similarly, we can multiply $a_i$ by $-1$ to get $a_1 = 1$, $a_2 = 2$, $\dots$,
$a_{p-1} = p-1$.  This is equivalent to replacing $x$ with $-x$, so some
coefficients of $P$ and $Q$ are negated by this. The key conditions still remain
unchanged.

\begin{remark*}
  For rigor, it's important to prove the facts about continued fractions first
  rather than going straight to the coefficient replacement as the requirements
  imposed by the problem statement on $P$ and $Q$ are not always preserved
  modulo $p$.
\end{remark*}

At this point, we are ready to directly calculate the polynomials $P_n$.
\begin{claim*}
  For all $n$, we have
  \[P_n(x) = \sum_{k\geq 0} \frac{n!}{2^kk!(n-2k)!}x^k.\]
  Here, we define $\frac{n!}{(n-2k)!} = n(n-1)\dots(n-2k+1)$ so the sum actually stops at $k=\lfloor n/2\rfloor$.
\end{claim*}
\begin{proof}
  We use induction. The base cases are clear, and
  \begin{align*}
    P_n + nxP_{n-1} & = \sum_{k \ge 0} \frac1{2^k k!} \frac{n!}{(n-2k)!} x^k
    + nx \sum_{k \ge 0} \frac1{2^k k!} \frac{(n-1)!}{(n-2k-1)!} x^k\\
    & = \sum_{k \ge 0} \frac1{2^k k!} \frac{n!}{(n-2k)!} x^k
    + \sum_{k \ge 0} \frac1{2^k k!} \frac{n!}{(n-2k-1)!} x^{k+1}\\
    & = \sum_{k \ge 0} \frac1{2^k k!} \frac{n!}{(n-2k)!} x^k
    + \sum_{k \ge 1} \frac1{2^{k-1} (k-1)!} \frac{n!}{(n-2k+1)!} x^k\\
    & = 1 + \sum_{k \ge 1} \left[\frac1{2^k k!} \frac{n!}{(n-2k)!}
    + \frac1{2^{k-1} (k-1)!} \frac{n!}{(n-2k+1)!}\right] x^k\\
    & = 1 + \sum_{k \ge 1} \frac1{2^k k!} \frac{n!}{(n-2k+1)!}
    \left[(n - 2k + 1) + 2k\right] x^k\\
    & = 1 + \sum_{k \ge 1} \frac1{2^k k!} \frac{(n + 1)!}{(n-2k+1)!} x^k\\
    & = \sum_{k \ge 0} \frac1{2^k k!} \frac{(n + 1)!}{(n-2k+1)!} x^k\\
    & = P_{n+1}. \qedhere
  \end{align*}
\end{proof}

At this point we can directly check the coefficients of $P$ and $Q$. We have
\[P(x) = P_p(x) = \sum_{k\geq 0} \frac{p!}{2^kk!(p-2k)!}x^k.\]
For $k=0$, we get a coefficient of $1$. For $k\geq 1$, the denominator is not a
multiple of $p$, so the remaining coefficients are multiples of $p$. Meanwhile,
the coeffiicents for $Q$ are $\frac{(p-1)!}{2^kk!(p-1-2k)!}$. None of these are
divisible by $p$ because $(p-1)!$ is not divisible by $p$.

\begin{remark*}
  This problem was created from the identity
  \[
    \cfrac{1}{1-\cfrac{x}{1-\cfrac{2x}{1-\cfrac{3x}{1-\dotsc}}}} = \sum_{i=0}^{\infty}(2i-1)!!x^i.
  \]
  You can use this to solve the problem. However, the proof of the identity as
  well as the details to convert this into the given problem are very lengthy so
  this is only left as a remark.
\end{remark*}

\paragraph{Solution 2.}
\begin{lemma*}
  Define a series of polynomials $A_n$, $B_n$, $C_n$, $D_n$ by letting
  $A_1 = 1$, $B_1 = x$, $C_1 = 1$, and $D_1 = 0$, and for $n \geq 2$,
  \begin{align*}
    A_n &= A_{n-1} + B_{n-1} &
    B_n &= nxA_{n-1} \\
    C_n &= C_{n-1} + D_{n-1} &
    D_n &= nxC_{n-1}.
  \end{align*}
  Then, if we define $f_k(t) = 1 + \frac{kx}{t}$, then
  \[( f_1 \circ f_2 \circ \dotsb \circ f_n)(t) = \frac{A_n t + B_n}{C_n t + D_n}. \]
\end{lemma*}
\begin{proof}
Straightforward by induction: the $n=1$ case is true and for $n \geq 2$,
\[ \frac{A_{n-1} f_n(t) + B_{n-1}}{C_{n-1} f_n(t) + D_{n-1}} =
  \frac{A_{n-1} (t + nx) + B_{n-1} t}{C_{n-1}(t + nx) + D_{n-1} t} =
  \frac{(A_{n-1} + B_{n-1})t + nxA_{n-1}}{(C_{n-1} + D_{n-1})t + nxD_{n-1}}. \qedhere \]
\end{proof}

It is possible to solve these recurrences algebraically,
but there is in fact a nice combinatorial interpretation of these polynomials:

\begin{lemma*}
  Let $\mathcal{I}_n$ be the set of involutions on $\{1,2,\dotsc,n\}$
  and for $\pi \in \mathcal{I}_n$, let $a(\pi)$ denote the number of transpositions in $\pi$.
  Let $\mathcal{J}_n \subseteq \mathcal{I}_n$ be the set of involutions $\pi$
  where the minimal fixed point is less than the minimal $x$ with $\pi(x) < x$.
  Then, for all $k \geq 1$, we have
  \begin{align*}
    A_n &= \sum_{\pi \in \mathcal{I}_n} x^{a(\pi)} &
    B_n &= \sum_{\substack{\pi \in \mathcal{I}_{n+1} \\\pi(n+1)\neq n+1}} x^{a(\pi)} \\
    C_n &= \sum_{\pi \in \mathcal{J}_n} x^{a(\pi)} &
    D_n &= \sum_{\substack{\pi \in \mathcal{J}_{n+1} \\\pi(n+1)\neq n+1}} x^{a(\pi)}.
  \end{align*}
\end{lemma*}

\begin{proof}
  We use induction on $n$, with the case $n=1$ being easily verified.
  For $n \geq 2$, note that
  \[A_n - B_{n-1} = \sum_{\substack{\pi \in \mathcal{I}_{k+1} \\\pi(k+1)= k+1}} x^{a(\pi)} = A_{n-1}.\]
  Moreover, every $\pi \in \mathcal{I}_{n+1}$ swapping $n+1$ with something else
  can be characterized by one of $n$ choices for $\pi(n+1)$
  and an involution on the remaining $n-1$ elements.
  Therefore $B_n = nxA_{n-1}$.
  A similar proof holds for the $C_n$ and $D_n$.
\end{proof}

We now note that
\[ \frac{P(x)}{Q(x)} = (f_1 \circ f_2 \circ \dotsb \circ f_{p-1})(1)
  = \frac{A_{p-1} + B_{p-1}}{C_{p-1} + D_{p-1}} = \frac{A_p}{C_p}. \]
It suffices to show that all nonconstant coefficients of $A_p$ are divisible by $p$
and that all coefficients of $C_p$ are not divisible by $p$.
If we show this, then any nonconstant factor dividing $A_p$
must have a leading coefficient divisible by $p$
(proof: reduce the factorization mod $p$),
then any nonconstant factor dividing $C_p$ cannot have a leading coefficient divisible by $p$.
Moreover, since $A_p$ and $C_p$ have constant terms of $1$,
they are relatively prime and thus $P = A_p$ and $Q = C_p$ (up to sign).

We now evaluate the coefficients of $A_p$ and $C_p$.
We observe that
\[A_p = \sum_{k=0}^{\frac{p-1}{2}}\binom{p}{2k} (2k-1)!! x^k,\]
and it is easy to see that $A_p \equiv 1 \pmod{p}$.
Computing the coefficients of $C_n$ is a bit harder.
Consider elements of $\mathcal{J}_p$ with $0 \leq k \leq \frac{p-1}{2}$ swaps
and a minimal fixed point of $a+1$ (for $0 \leq a \leq k$).
Everything in $\{1,\dotsc,a\}$ must be paired with something greater than $a+1$,
and there are $k-a$ swaps among the remaining elements.
It follows that
\begin{align*}
  C_p &= \sum_{k=0}^{\frac{p-1}{2}} \sum_{a=0}^k \frac{(p-a-1)!}{(p-2a-1)!} \binom{p-2a-1}{2k-2a}(2k-2a-1)!! \cdot x^k \\
  &= \sum_{k=0}^{\frac{p-1}{2}} \sum_{a=0}^k \frac{(p-a-1)!}{(p-2k-1)! 2^{k-a} (k-a)!} x^k \\
  &= \sum_{k=0}^{\frac{p-1}{2}} \frac{(p-1)!}{(p-2k-1)!} \left(\sum_{a=0}^k \frac{1}{2^{k-a} (k-a)! \prod_{j=1}^a (p-j)}\right) x^k \\
  &\equiv \sum_{k=0}^{\frac{p-1}{2}} \frac{(p-1)!}{(p-2k-1)!} \left(\sum_{a=0}^k \frac{(-1)^a}{2^{k-a} (k-a)! a!}\right) x^k \\
  &= \sum_{k=0}^{\frac{p-1}{2}} \frac{(p-1)!}{(p-2k-1)!k!} \left(\sum_{a=0}^k \binom{k}{a}\frac{(-1)^a}{2^{k-a}}\right) x^k \\
  &= \sum_{k=0}^{\frac{p-1}{2}} \frac{(p-1)!}{(p-2k-1)!k!} \left(-1+\frac{1}{2}\right)^k x^k.
\end{align*}
The result follows.
\begin{remark*}
It is not hard to see that $C_p$ simplifies further mod $p$ to
\[ \sum_{k=0}^{\frac{p-1}{2}}(-1)^k (2k-1)!! x^k. \]
\end{remark*}