Continued fraction

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Continued fraction

G H J

Reveal topic tags

continued fraction

L

G H BBookmark kLocked kLocked NReply

Source: TSTST 2024, problem 2

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

71 posts

#1 h Jun 24, 2024, 6:36 PM • 1 Y

Y by Rounak_iitr

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 not divisible by $p$ .

Andrew Gu

This post has been edited 2 times. Last edited by tapir1729, Jan 6, 2025, 2:37 AM
Reason: fixed italics

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1541 posts

#2 h Jun 24, 2024, 6:49 PM • 1 Y

Y by sami1618

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.

This post has been edited 1 time. Last edited by YaoAOPS, Jun 27, 2024, 7:03 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1336 posts

#3 h Jun 24, 2024, 7:23 PM

Y by

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.

This post has been edited 1 time. Last edited by Assassino9931, Jun 25, 2024, 9:14 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

223 posts

#4 h Jun 24, 2024, 11:30 PM

Y by

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?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1831 posts

#5 h Jun 26, 2024, 1:19 AM • 2 Y

Y by sami1618, KevinYang2.71

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.

This post has been edited 1 time. Last edited by brainfertilzer, Jun 26, 2024, 1:21 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5001 posts

#6 h Jun 26, 2024, 6:15 PM • 1 Y

Y by crazyeyemoody907

"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

This post has been edited 2 times. Last edited by IAmTheHazard, Jun 26, 2024, 6:35 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

180 posts

dkedu

#7 h Jun 27, 2024, 6:04 PM

Y by

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.

This post has been edited 2 times. Last edited by dkedu, Jun 27, 2024, 8:50 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1301 posts

#8 h Jun 27, 2024, 6:08 PM

Y by

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.

This post has been edited 1 time. Last edited by CANBANKAN, Jun 27, 2024, 6:34 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1039 posts

#9 h Jun 28, 2024, 3:43 AM • 1 Y

Y by OronSH

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

This post has been edited 1 time. Last edited by Gogobao, Jun 28, 2024, 3:44 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5419 posts

#10 h Jul 13, 2024, 5:33 PM • 6 Y

Y by OronSH, avisioner, dolphinday, ihatemath123, awesomeguy856, Rounak_iitr

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 :blush:

:blush:

. Then I found and wrote up the closed-form solution in the last 15 minutes :blush:

:blush:

.

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 :blush:

:blush:

.

This post has been edited 1 time. Last edited by peace09, Jul 13, 2024, 5:34 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1752 posts

#11 h Apr 27, 2025, 2:40 AM

Y by

Very nice and instructive problem to solve, horrible problem to type up.

The idea is to work modulo $p$ and build the fraction from the bottom up. In particular, let us define the function $R_k(x)$ recursively by $R_1(x) = 1+(p-1)x$ and $R_k(x) = 1 + \frac{(p-k)x}{R_{k-1}(x)}.$ We claim that $R_n(x) \equiv \frac{P_n(x)}{P_{n-1}(x)} \pmod{p},$ where $P_n(x) = \sum_{i=0}^{\infty} (-1)^i (2i-1)!! \cdot \binom{n+1}{2i} x^i$ with $(2n+1)!! = (2n+1) \cdot (2n-1) \cdots 3 \cdot 1$ letting $(-1)!! = 1$ . We will prove this claim by induction on $n,$ with the base case $n=1$ following from $R_1(x) \equiv 1 - x \pmod{p}.$ For the inductive step, we have
$\begin{align*} R_n(x) &= 1 + \frac{(p-n)x}{R_{n-1}(x)} \\ &\equiv 1 - \frac{nx}{R_{n-1}(x)} \pmod{p} \\ &= 1 - \frac{nx P_{n-2} (x)}{P_{n-1} (x)} \\ &= \frac{P_{n-1} (x) - nx P_{n-2} (x)}{P_{n-1} (x)} \\ &= \frac{\sum_{i=0}^{\infty} (-1)^i (2i-1)!! \cdot \binom{n}{2i} x^i - n \sum_{i=1}^{\infty} (-1)^{i-1} (2i-3)!! \cdot \binom{n-1}{2i-2} x^i}{P_{n-1} (x)} \\ &= \frac{1 + \sum_{i=1}^{\infty} \left((-1)^i (2i-1)!! \cdot \binom{n}{2i} - n(-1)^{i-1} (2i-3)!! \cdot \binom{n-1}{2i-2}\right) x^i}{P_{n-1}(x)} \\ &= \frac{1 + \sum_{i=1}^{\infty} (-1)^i (2i-3)!! \left((2i-1) \binom{n}{2i} + n \binom{n-1}{2i-2}\right) x^i}{P_{n-1}(x)} \\ &= \frac{1 + \sum_{i=1}^{\infty} (-1)^i (2i-1)!! \cdot \binom{n+1}{2i} x^i}{P_{n-1}(x)} \\ &= \frac{P_n (x)}{P_{n-1} (x)}, \end{align*}$ where we used the identity $\binom{n}{2i} + \frac{n}{2i-1} \binom{n-1}{2i-2} = \binom{n+1}{2i}$ (which can be proven by Pascal's Identity). This completes the induction.

In particular, the desired expression is just $R_{p-1} (x),$ which after taking coefficients modulo $p$ is just $\frac{P_{p-1} (x)}{P_{p-2} (x)}.$ It is easy to see by the recursion that this cannot be further simplified. Now, in the numerator, the binomial coefficients $\binom{p}{2i}$ are always divisible by $p$ except when $i=0,$ making all the coefficients except for the constant coefficient divisible by $p.$ Similarly, in the denominator, the binomial coefficients $\binom{p-1}{2i}$ are always not divisible by $p$ unless $i > \frac{p-1}{2},$ and similarly $(2i-1)!!$ is not divisible by $p$ either unless $i > \frac{p-1}{2}.$ In any case, the coefficients of $x^i$ in $P_{p-2} (x)$ for $0 \le i \le \frac{p-1}{2}$ are not divisible by $p.$ However, by a much easier induction, we have that the degree of $Q(x)$ is exactly $\frac{p-1}{2}$ . Thus $P(x)$ has all its coefficients divisible by $p$ except for the constant coefficient, and $Q(x)$ has all its coefficients not divisible by $p,$ as desired.

This post has been edited 6 times. Last edited by EpicBird08, Apr 27, 2025, 5:53 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a