Very cool problem. We instead consider the expression \[ 1 + \frac{(1-p)x}{1 + \frac{(2-p)x}{1 + \frac{\ddots}{1 - x}}} = \frac{P_{p-1}(x)}{Q_{p-1}(x)} \]We then have the relation \[ \frac{P_k(x)}{Q_k(x)} = 1 + \frac{-kx}{\frac{P_{k-1}(x)}{Q_{k-1(x)}}} = \frac{P_{k-1}(x) -kx Q_{k-1}(x)}{P_{k-1}(x)} \]We inductively then have that $\gcd(P_i, Q_i) = 1$. Define $P_1' = 1-x, P_0' = 1$, so this rewrites as $P_k'(x) = P_{k-1}' - kx P_{k-2}'(x)$. Now, replace $x$ with $-x$ and shift to instead get $P_0 = 1, P_1 = 1, P_k = P_{k-1} + (k-1)x P_{k-2}$, and we want to show that instead $P_{p} \equiv 1 \pmod{p}$ and $P_{p-1}$ has all nonzero coefficients. Here's a table of the first few entries of $p$. \begin{tabular}{c|ccccccccc} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ $x$ & 0 & 0 & 1 & 3 & 6 & 10 & 15 & 21 & 28 \\ $x^2$ & 0 & 0 & 0 & 0 & 3 & 15 & 45 & 105 & 210 \\ $x^3$ & 0 & 0 & 0 & 0 & 0 & 0 & 15 & 105 & 420 \\ $x^4$ & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 105 \end{tabular} Claim: We have that $[x^k]P_x = A_k(x)$ where \[ A_k(x) = \frac{x(x-1) \cdots (x-(2k-2))(x-(2k-1))}{2^k k!} \]Proof. We have that $[x^t] P_k = [x^t] P_{k-1} + [x^{t-1}] (k-1) P_{k-2}$. This rewrites as showing that \[ A_t(k) - A_t(k-1) = (k-1) A_{t-1}(k-2) \]Expand this and factor out \[ \frac{1}{2^{t-1} (t-1)!} (k-2) \cdots (k-(2t+1)) \]to simplify this as $\frac{1}{2t} \left((k(k-1) - (k-1)(k - 2t))\right) = k-1$ which finishes. $\blacksquare$ This then finishes by plugging in $t = p, t = p-1$. Remark: Trying to represent each row as a polynomial follows from noticing the fact that the first three rows are in fact $1$, $\binom{n}{2}$, and $\binom{\binom{n}{2}}{2}$ or noticing that $P_k \equiv P_{p} \pmod{p}$. Getting this specific form for the polynomial comes from fundamental theorem of algebra. As a matter of fact, this is enough to prove that $P_{p-1} \equiv 1 \pmod{p}$. EDIT: CANBANKAN points out some valid concerns about the correspondence between the new polynomials and old ones. Coprimality and being the same degree both follow by expansion so it's nothing too major but it's still an issue.

Representing this as a continued fraction and using the well known convergents relations (e.g. Wikipedia, section Infinite continued fractions and convergents) should work. EDIT: The computations are actually very inconvenient, my bad.

Assassino9931 wrote: Representing this as a continued fraction and using the well known convergents relations (e.g. Wikipedia, section Infinite continued fractions and convergents) should work. Are you sure about that?

Let \[1 + \cfrac{kx}{1 + \cfrac{(k+1)x}{1 + \cfrac{\ddots}{1 + (p-1)x}}} = \frac{P_k(x)}{Q_k(x)}\]for coprime $P_k,Q_k$, each with constant term $1$. Note that \[1 + kx\frac{Q_{k+1}(x)}{P_{k+1}(x)} = \frac{P_k(x)}{Q_k(x)}\implies Q_k(P_{k+1} + kxQ_{k+1}) = P_{k+1}P_k.\]This means $Q_k\mid P_{k+1}P_k$, and since $P_k$ is coprime with $Q_k$, we have $Q_k\mid P_{k+1}$. Also, note that $P_{k+1}$ and $P_{k+1} + kxQ_{k+1}$ are coprime, so $P_{k+1}\mid Q_k$. Since $Q_k, P_{k+1}$ both have constant term $1$, we get $P_{k+1} = Q_k$. It follows that \[Q_k + kxQ_{k+1} = Q_{k-1}.\]Work in $\mathbb{F}_p[x]$ for the rest of the problem. We have $Q_{p-1} = 1$ and $Q_{p-2} = 1 + (p-1)x = 1-x$. Claim: We have \[Q_{p-m} = \sum_{n\ge 0}\frac{(-1)^nm!}{2^nn!(m-2n)!}x^n.\]proof: Induct. It's just a big bash so I won't write it $\square$ Now take $m = p-1$ to get \[Q_1 = \sum_{n\ge 0}\frac{(-1)^{n}(p-1)!}{2^{n}n!(p-1 - 2n)!}x^n,\]and all of the coefficients of that are clearly nonzero. Next note that \[P_1 = Q_0 = \sum_{n\ge 0}\frac{(-1)^np!}{2^nn!(p-2n)!}x^n,\]all of whose terms vanish aside from $1x^0$. This is all we needed to prove.

"a five year old with a CAS could do it" We instead consider the expression $$1-\cfrac{kx}{1-\cfrac{(k-1)x}{1+\cfrac{\ddots}{1-x}}}:=\frac{P_k(x)}{Q_k(x)},$$and wish to show that for any odd prime $p$, $P_{p-1}(x)$ has all coefficients except the constant divisible by $p$, and $Q_{p-1}(x)$ has all coefficients not divisible by $p$. Clearly we have $A_1(x)=1-x$ and $B_1(x)=1$ as well as $A_k(x)=A_{k-1}(x)-kxB_k(x)$ and $B_k(x)=A_{k-1}(x)$. Defining $A_0=B_1$ we thus have $A_k(x)=A_{k-1}(x)-kxA_{k-2}(x)$ for all $x$. To extract coefficients we note that $[x^t]A_k=[x^t]A_{k-1}-k[x^{t-1}]A_{k-2}$. Now I claim that $$[x^t]A_k=\frac{(-1)^n(k+1)_{2t}}{(2t)!!},$$which follows by induction since $$(k+1)_{2t}-(k)_{2t}=((k+1)-(k-2t+1))(k)_{2t-1}=k(2t((k-2)+1)_{2t-2}).$$Note that for $k \leq 2t-1 \iff t\geq \tfrac{k+1}{2}$ we have $[x^t]A_k=0$. Now just plug in $k=p-1$ and $k=p-2$ and note that for any $t<\tfrac{k+1}{2}$ the denominator doesn't vanish modulo $p$, but if $k=p-1$ the numerator does and if $k=p-2$ the numerator doesn't. $\blacksquare$ edit: should be noted that we want the rewrite of the expression and the redefinition of the polynomials to not change their degree - this is obviously true edit edit: it has been pointed out that you also need to show relatively prime. it’s obvious that simplifying the fraction will achieve this (in both scenarios) because everything you get has constant coeff 1

We work in $\mathbb F_p[x]$ instead and consider $$1-\cfrac{nx}{1-\cfrac{(n-1)x}{1-\cfrac{\ddots}{1-x}}}=\frac{P_n(x)}{Q_n(x)}$$We get the two recursive relations $$Q_n(x) = P_{n-1}(x), P_n(x) = P_{n-1}(x) - nxQ_{n-1}(x) = P_{n-1}(x) - nxP_{n-2}(x)$$with $P_1(x) = 1- x, Q_1(x) = 1$. Note that $P_i(x), Q_i(x)$ are always relatively prime by Euclidean algorithm. Now we let $$P_n(x) = \sum_{m=0}^\infty a_{m,n}x^m$$Note that we get $a_{m,n} = a_{m,n-1} - na_{m-1,n-2}$. Now I claim $$a_{m,n} = (-1)^n(2m-1)!!\binom{n+1}{2m}.$$We can verify this works since $$a_{m,n} = -\sum_{i = 0}^{n-2} na_{m-1, i} = (-1)^m \sum_{i = 0}^{n-2} (i+2)\cdot (2m-3)!! \binom{i+1}{2m-2} =(-1)^m \sum_{i = 0}^{n-2}(2m-3)!! \cdot (2m-1) \binom{i+2}{2m-1} = (-1)^m (2m-1)!!\sum_{i = 0}^{n-2} \binom{i+2}{2m-1} = (-1)^m(2m-1)!!\binom{n+1}{2m}.$$Now we conclude that $a_{m,p-1} \equiv 0 \pmod{p}$ for $m \ge 1$ and $a_{m,p-2} \not\equiv 0 \pmod{p}$. Since $p\mid \binom pk$ and $p \nmid \binom{p-1}k$ which is equivalent to the result.

YaoAOPS wrote: Very cool problem. We instead consider the expression \[ 1 + \frac{(1-p)x}{1 + \frac{(2-p)x}{1 + \frac{\ddots}{1 - x}}} = \frac{P_{p-1}(x)}{Q_{p-1}(x)} \]We then have the relation \[ \frac{P_k(x)}{Q_k(x)} = 1 + \frac{-kx}{\frac{P_{k-1}(x)}{Q_{k-1(x)}}} = \frac{P_{k-1}(x) -kx Q_{k-1}(x)}{P_{k-1}(x)} \]We inductively then have that $\gcd(P_i, Q_i) = 1$. Define $P_1' = 1-x, P_0' = 1$, so this rewrites as $P_k'(x) = P_{k-1}' - kx P_{k-2}'(x)$. Now, replace $x$ with $-x$ and shift to instead get $P_0 = 1, P_1 = 1, P_k = P_{k-1} + (k-1)x P_{k-2}$, and we want to show that instead $P_{p} \equiv 1 \pmod{p}$ and $P_{p-1}$ has all nonzero coefficients. Here's a table of the first few entries of $p$. \begin{tabular}{c|ccccccccc} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ $x$ & 0 & 0 & 1 & 3 & 6 & 10 & 15 & 21 & 28 \\ $x^2$ & 0 & 0 & 0 & 0 & 3 & 15 & 45 & 105 & 210 \\ $x^3$ & 0 & 0 & 0 & 0 & 0 & 0 & 15 & 105 & 420 \\ $x^4$ & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 105 \end{tabular} Claim: We have that $[x^k]P_x = A_k(x)$ where \[ A_k(x) = \frac{x(x-1) \cdots (x-(2k-2))(x-(2k-1))}{2^k k!} \]Proof. We have that $[x^t] P_k = [x^t] P_{k-1} + [x^{t-1}] (k-1) P_{k-2}$. This rewrites as showing that \[ A_t(k) - A_t(k-1) = (k-1) A_{t-1}(k-2) \]Expand this and factor out \[ \frac{1}{2^{t-1} (t-1)!} (k-2) \cdots (k-(2t+1)) \]to simplify this as $\frac{1}{2t} \left((k(k-1) - (k-1)(k - 2t))\right) = k-1$ which finishes. $\blacksquare$ This then finishes by plugging in $t = p, t = p-1$. Remark: Trying to represent each row as a polynomial follows from noticing the fact that the first three rows are in fact $1$, $\binom{n}{2}$, and $\binom{\binom{n}{2}}{2}$ or noticing that $P_k \equiv P_{p} \pmod{p}$. Getting this specific form for the polynomial comes from fundamental theorem of algebra. As a matter of fact, this is enough to prove that $P_{p-1} \equiv 1 \pmod{p}$. This is also the initial solution I found while testsolving. I however don't see a way to see how to show the original $P,Q$ are coprime using this method, since the image of $P$ in $\mathbb{F}_p[x]$ is just 1. This is very minor.

The coefficient of $x^k$ in $P$ is $(2k-1)!!\binom{p}{2k}$ and in $Q$ is $\sum_{n=0}^k (-1)^n(2k-2n-1)!!(2n-1)!!\binom{p}{2(k-n)}$ Here we adapt the assumption $(-1)!! = 1$.

Misleadingly, $P\equiv1$ is doable without a closed form: denote \[\frac{P_n(x)}{P_{n-1}(x)}=1+\frac{(p-n)x}{1+\frac{(p-n+1)x}{1+\frac{\ddots}{1+(p-1)x}}}=1+\frac{(p-n)x}{\frac{P_{n-1}(x)}{P_{n-2}(x)}}=\frac{P_{n-1}(x)+(p-n)xP_{n-2}(x)}{P_{n-1}(x)}.\]Coprimality is easy inductively, as $(P_n,P_{n-1})=(P_{n-1}+(p-n)xP_{n-2},P_{n-1})=(P_{n-1},(p-n)xP_{n-2})=1$ by Euclid. The key claim is that $[x^k]P_n=S_k[p-n,p-1]'$, the $k^\text{th}$ symmetric sum of integers in $[p-n,p-1]$ no two of which are consecutive (hence the ${}'$). Indeed, inductively, \begin{align*} [x^k]P_n&=[x^k]P_{n-1}+(p-n)[x^k]xP_{n-2}\\ &=S_k[p-n+1,p-1]'+(p-n)S_{k-1}[p-n+2,p-1]', \end{align*}which span $k$-factor products in $[p-n,p-1]'$ without and with the factor $(p-n)$, respectively, giving $S_k[p-n,p-1]'$. Since $P=P_{p-1}$ in the problem statement, we want to show $[x_k]P_{p-1}=S_k[1,p-1]'\equiv0~(p)$. The trick is to rewrite $S_k[1,p-1]'$ as $S_k[0,p-1]'$ to "complete" $\mathbb{Z}_p$ and somehow use symmetry. Take inspiration from the necklace proof of Fermat's little theorem: by primality, we may partition $S_k[0,p-1]'$ into "cyclic size-$p$ rings" of the form \[\sum_{x=0}^{p-1}\prod_{i=1}^k(a_i+x):=\prod_{i=1}^ka_i+\prod_{i=1}^k(a_i+1)+\dots+\prod_{i=1}^k(a_i+(p-1)),\]where each $k$-factor product in $S_k[0,p-1]'$ belongs to exactly one such ring. We claim that each such ring vanishes $(\text{mod }p)$, which finishes. Expanding each product and grouping by degree in $x$, we have \[\sum_{d=0}^kS_{k-d}[a_i]\sum_{x=0}^{p-1}x^d:=S_0[a_i]\sum_{x=0}^{p-1}x^k+S_1[a_i]\sum_{x=0}^{p-1}x^{k-1}+\dots+S_k[a_i]\sum_{x=0}^{p-1}x^0,\]where for any given $d$, $\textstyle\sum x^d=\sum g^{di}\equiv\sum g^i=\sum x\equiv0$ for $g$ a primitive root. $\square$ Unfortunately, for $Q=P_{p-2}$, showing $[x_k]P_{p-2}=S_k[2,p-1]\not\equiv0$ seems much more difficult, since the aforementioned "completeness" is lost. Indeed, it suffices to show that its complement in the complete $S_k[1,p-1]\equiv0$ is nonzero; but said complement is simply $S_{k-1}[3,p-1]$, and everything spirals out of control from there. It was here that I finally realized I would need to say something about general $[x_k]P_n$—"here" as in "with 15 minutes left", after finding and writing up the non-closed-form solution to part (a) for 2+ hours with the expectation that part (b) would be identical . Then I found and wrote up the closed-form solution in the last 15 minutes . Personally, I was rather bummed when I discovered the closed form, since the problem essentially becomes a mid-AIME binomial recursion with polynomial flavortext and a Legendre-like extraction. (The first thing that came to mind was 1993 #5, though there's bound to be a better example.) Indeed, I suspect that if the problem were computationalized with said extraction and presented to the students as an AIME problem with a 15-minute timer (as I had), everyone would have solved it .