Putnam 2019 A5

Art of Problem Solving

AoPS Online

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Putnam 2019 A5

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

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

35 posts

hoeij

#1 h Dec 10, 2019, 1:03 AM • 1 Y

Y by Adventure10

Let $p$ be an odd prime number, and let $\mathbb{F}_p$ denote the field of integers modulo $p$ . Let $\mathbb{F}_p[x]$ be the ring of polynomials over $\mathbb{F}_p$ , and let $q(x) \in \mathbb{F}_p[x]$ be given by $q(x) = \sum_{k=1}^{p-1} a_k x^k$ where $a_k = k^{(p-1)/2}$ mod $p$ . Find the greatest nonnegative integer $n$ such that $(x-1)^n$ divides $q(x)$ in $\mathbb{F}_p[x]$ .

Z K Y

The post below has been deleted. Click to close.

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

35 posts

hoeij

#3 h Dec 10, 2019, 1:03 AM • 3 Y

Y by OmicronGamma, Guardiola, Adventure10

Answer: For $f(x) \in \mathbb{F}_p[x] - \{0\}$ let $m(f)$ denote its multiplicity at $x=1$ so $f(x) = (x-1)^{m(f)} g(x)$ for some $g(x) \in \mathbb{F}_p[x]$ with $g(1) \neq 0$ . If $m(f) \not\equiv 0$ mod $p$ , then $m(f') = m(f)-1$ by the product rule. We are asked to compute $m(q)$ .

Let $f_n := \sum_{k=0}^{p-1} k^n x^k \in \mathbb{F}_p[x]$ . Then $f_0 = x^{p-1}+\cdots+x^0 = (x^p-1)/(x-1) = (x-1)^{p-1}$ using the fact that $x^p-1 = (x-1)^p$ in $\mathbb{F}_p[x]$ . Since $f_{n+1} = x f_n'$ it follows that $m(f_n) = m(f_0) - n$ for $n = 1,2,\ldots, m(f_0)$ . In particular $m(q) = m(f_{(p-1)/2}) = m(f_0) - (p-1)/2 = (p-1)/2$ .

Z K Y

The post below has been deleted. Click to close.

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

126 posts

#4 h Dec 10, 2019, 1:42 AM • 3 Y

Y by Guardiola, Adventure10, Mango247

Kiran's solution uses the transformation $D^m(f)=xf'$ , which is way neater. Here's a solution that repeats the above, i.e. $D^m(f)=f'$ and as usual we find the smallest $n$ with $D^n(f)(1)\neq 0$ . Finding derivative term wise, get
$D^m(q)(1) = \sum_{k=1}^{p-1} k^{(p-1)/2}k(k-1)\cdots (k-m+1)$ (some explanation needed as $k-m$ could go to 0. We can now write the above in terms of the following polynomial:
$s_m(x)=x^{(p-1)/2}x(x-1)\cdots (x-m+1) =\sum_{k=1}^{m}b_kx^{(p-1)/2+k}$ and
$D^m(q)(1) = \sum_{j=1}^{p-1}s_m(j) =\sum_{k=1}^m b_k\sum_{x=1}^{p-1}x^{(p-1)/2+k}$ Now for $k<\frac{p-1}{2}$ each term $\sum_{x=1}^{p-1}x^{(p-1)/2+k}=0$ (primitive root argument), which means the sum will be $0$ for $0\le m<\frac{p-1}{2}$ . For $m=\frac{p-1}{2}$ , only $k=m=\frac{p-1}{2}$ is left and
$D^m(q)(1)=\sum_{k=1}^m b_k(-1)$ but $b_k$ is the coefficient of the monic polynomial $s_m(x)$ , hence equal 1, so $D^m(q)(1)=-1\neq 0$ for $m=\frac{p-1}{2}$ .

Z K Y

The post below has been deleted. Click to close.

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

35 posts

hoeij

#5 h Dec 10, 2019, 2:06 AM • 2 Y

Y by Adventure10, Mango247

Note that the exponent $(p-1)/2$ in the problem is irrelevant. If you replace it by another positive integer $n<p$ then the answer is simply $p-1-n$ .

Z K Y

The post below has been deleted. Click to close.

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

TheStrangeCharm

290 posts

TheStrangeCharm

#6 h Dec 10, 2019, 3:12 AM • 2 Y

Y by Adventure10, Mango247

We first claim that for each $0\leq \ell < \frac{p - 1}{2}$ , we have that
$(*) \sum_{k\in \mathbb{F}_p^{\times}}k^{\ell}a_k = 0.$ Indeed, the above sum can be written as
$\sum_{k\in \mathbb{F}_p^{\times 2}}k^{\ell} - \sum_{k\in \mathbb{F}_p^{\times} - \mathbb{F}_p^{\times 2}}k^{\ell}.$ But we have that
$\sum_{k\in \mathbb{F}_p^{\times 2}}k^{\ell} + \sum_{k\in \mathbb{F}_p^{\times} - \mathbb{F}_p^{\times 2}}k^{\ell} = \sum_{k\in \mathbb{F}_p^{\times}}k^{\ell} = 0.$ To see this, take some $\alpha\in \mathbb{F}_p^{\times}$ with $\alpha^{\ell} \neq 1$ , which is possible as $\ell < p - 1$ , to see that
$\sum_{k\in \mathbb{F}_p^{\times}}k^{\ell} = \sum_{k\in \mathbb{F}_p^{\times}}(\alpha k)^{\ell} \implies (1 - \alpha^{\ell})\sum_{k\in \mathbb{F}_p^{\times}}k^{\ell} = 0 \implies \sum_{k\in \mathbb{F}_p^{\times}}k^{\ell} = 0.$ Thus, we have that
$\sum_{k\in \mathbb{F}_p^{\times 2}}k^{\ell} - \sum_{k\in \mathbb{F}_p^{\times} - \mathbb{F}_p^{\times 2}}k^{\ell} = 2\sum_{k\in \mathbb{F}_p^{\times 2}}k^{\ell} = \sum_{m\in \mathbb{F}_p^{\times}}m^{2\ell} = 0,$ as $2\ell < p - 1$ , so we can use the trick of taking some $\alpha\in \mathbb{F}_p^{\times}$ with $\alpha^{2\ell}\neq 1$ as above, thus establishing $(*)$ .

Now, return to our polynomial
$\sum_{k = 1}^{p - 1}a_kx^k.$ Note that this polynomial always vanishes at $x = 1$ by taking $(*)$ with $\ell = 0$ . Suppose we take $\ell > 0$ derivatives of this expression and evaluate the result at $1$ . The result will be
$\sum_{k = 1}^{p - 1}k(k - 1)\cdots k(k - \ell + 1)a_k.$ But we can expand out $k(k - 1)\cdots k(k - \ell + 1)$ as some polynomial in $k$ with integer coefficients and degree $\ell$ . Thus, as long as $\ell < \frac{p - 1}{2}$ , this expression will vanish by repeatedly applying (*). Thus, $(x - 1)^{\ell}$ divides our polynomial for $\ell < \frac{p - 1}{2}$ . To see that $(x - 1)^{\frac{p - 1}{2}}$ does not divide our polynomial, it suffices to show that
$\sum_{k\in \mathbb{F}_p^{\times}}k^{\frac{p - 1}{2}}a_k \neq 0,$ by expanding out $k(k - 1)\cdots k(k - \frac{p - 1}{2} + 1)$ as a polynomial in $k$ and applying $(*)$ to all $\ell < \frac{p - 1}{2}$ . But this sum is just
$\sum_{k\in \mathbb{F}_p^{\times}}k^{p - 1} = p - 1\neq 0. \text{ }\square$

Z K Y

The post below has been deleted. Click to close.

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

341 posts

#7 h Dec 10, 2019, 3:23 AM • 2 Y

Y by JohnDoeSmith, Adventure10

Let $\chi(k) = k^{(p-1)/2} = \left(\frac{k}{p}\right)$ . Then $q(x)^2 \equiv \sum_{k=0}^{p-1} (\chi\ast\chi)(k)x^k \pmod{x^p - 1}$ . But it's fairly well known that $\chi \ast \chi$ is a non-zero constant.

(Note: $(\chi\ast\chi)(k) = \sum_{i\in \mathbb F_p} \chi(i)\chi(k-i)$ .)

Z K Y

The post below has been deleted. Click to close.

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

35 posts

hoeij

#8 h Dec 10, 2019, 3:51 AM • 1 Y

Y by Adventure10

Short proof for A5: Let $f = 1+x+\cdots+x^{p-1} = (x-1)^{p-1}$ and denote $D(f) = xf'$ . Then $q(x) = D^{(q-1)/2}(f)$ . For $n=0,1,\ldots,p-1$ , the multiplicity of $x-1$ in $D^n(f)$ is $p-1-n$
(because any time the multiplicity is not 0 mod p, it drops by 1 when you differentiate).

This post has been edited 1 time. Last edited by hoeij, Dec 10, 2019, 3:57 AM
Reason: added "because any time..."

Z K Y

The post below has been deleted. Click to close.

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

3332 posts

#9 h Dec 10, 2019, 4:35 AM • 1 Y

Y by Adventure10

The answer is $\boxed{\frac{p-1}{2}}$ .

The only number theoretic fact necessary is that the $m$ th moment of $\mathbb{F}_p$ for $m\not\equiv0\pmod{p-1}$ is $0$ . There are a few different reasons this is true: (number theory) plug in a primitive root and use geometric series, (group theory) the sum is a multiple of the sum of a subgroup with zero sum, (algebra) use Newton sums on the polynomial $x^{p-1}-1$ .

An immediate corollary is that for any polynomial that has $0$ as a root has degree $\leq p-2$ , the sum of the polynomial over $\mathbb{F}_p$ is $0$ .

Take the $j$ th derivative; we get
$q^{(j)}(1)=\sum_{a\in\mathbb{F}_p}a^{\frac{p-1}{2}}a^{\underline{j}}$ where $x^{\underline{j}}=x(x-1)\cdots(x-j+1)$ is the falling factorial. When $j=0,\ldots,\frac{p-3}{2}$ , this is $0$ by the corollary. When $j=\frac{p-1}{2}$ , the corollary implies that
$q^{(j)}(1)=\sum_{a\in\mathbb{F}_p}a^{p-1}=-1.$ So the first $\frac{p-1}{2}-1$ derivatives of $q$ at $1$ (a root of $q$ ) are $0$ , so $1$ has multiplicity $\frac{p-1}{2}$ in $q$ .

Z K Y

The post below has been deleted. Click to close.

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

1614 posts

yayups

#10 h Dec 10, 2019, 5:12 AM • 4 Y

Y by pad, Vfire, Adventure10, Mango247

All statements in this solution will be over $\mathbb{F}_p[x]$ . Let $q^{(m)}(x)$ denote the $m$ th derivative of $q(x)$ . We have the following well known lemma.

Lemma 1: Suppose we have an integer $1\le n\le p$ . Then $(x-1)^n\mid q(x)$ if and only if $q^{(m)}(1)=0$ for all $m=0,1,\ldots,n-1$ .

Proof: Use the division algorithm for polynomials repeatedly to write $q(x)$ in the form $q(x)=b_0+b_1(x-1)+b_2(x-1)^2+\cdots+b_{p-1}(x-1)^{p-1}.$ In this setting, it's clear that $(x-1)^n\mid q(x)$ if and only if $b_m=0$ for all $m=0,1,\ldots,n-1$ . Differentiating $m$ times, we see that $m!b_m=q^{(m)}(1)$ , and since $m\le n-1\le p-1$ , we thus have $b_m=0\iff q^{(m)}(1)=0$ , so the result follows. $\blacksquare$

In our setting, we have $q^{(m)}(1)=\sum_{k=m}^{p-1}k^{\frac{p-1}{2}}k(k-1)\cdots(k-m+1)=\sum_{k=0}^{p-1}k^{\frac{p-1}{2}}k(k-1)\cdots(k-m+1).$ To evaluate this, we have the following useful lemma.

Lemma 2: For any integer $r=1,2,\ldots,p-2$ , we have $\sum_{k=0}^{p-1}k^r=0.$ Recall that we are working over $\mathbb{F}_p$ .

Proof: Let $g$ be a primitive root mod $p$ . Then, the sum is $\sum_{\ell=0}^{p-2}(g^\ell)^r=\sum_{\ell=0}^{p-2}=\frac{(g^r)^{p-1}-1}{g^r-1}=0,$ which works since $g^r-1$ , due to $1\le r\le p-2$ . $\blacksquare$

Lemma 2 clearly implies that $q^{(m)}(1)=0$ for $m=0,\ldots,\frac{p-1}{2}-1$ . It also implies that $q^{\left(\frac{p-1}{2}\right)}(1)=\sum_{k=0}^{p-1} k^{p-1}=p-1\ne 0,$ so the maximal $n$ such that $(x-1)^n\mid q(x)$ is $n=\boxed{\frac{p-1}{2}}$ by lemma 1.

Z K Y

The post below has been deleted. Click to close.

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

35 posts

hoeij

#11 h Dec 11, 2019, 1:27 PM • 2 Y

Y by Adventure10, Mango247

Trumpeter: The only number theoretic fact needed for this exercise is the Freshman's dream: $(x-1)^p = x^p - 1$ . The rest is calculus: the formula for a geometric sum, the fact that $x d/dx$ applied to $x^k$ gives $k x^k$ , and the fact that if a multiplicity of a root is not zero in our field then it decreases by 1 when you differentiate. Nothing else is needed for the proof.

Complete proof for A5: The geometric sum $f := 1+x+\cdots+x^{p-1}$ can be written as $f = (x^p-1)/(x-1) = (x-1)^{p-1}$ . Starting with $f$ and its multiplicity $p-1$ , keep applying $x d/dx$ until you reach $q(x)$ and its multiplicity.

Z K Y

The post below has been deleted. Click to close.

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

1180 posts

donot

#12 h Dec 19, 2019, 5:27 AM • 2 Y

Y by Adventure10, Mango247

It seems I'm late, but I had a more number-theoretic solution

Z K Y

The post below has been deleted. Click to close.

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

168 posts

Alex2

#13 h Feb 16, 2020, 5:20 PM • 1 Y

Y by Adventure10

Sol

Z K Y

The post below has been deleted. Click to close.

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

6877 posts

#14 h Sep 2, 2020, 11:51 AM • 3 Y

Y by XbenX, Mathematicsislovely, v4913

Solution from Twitch Solves ISL:

The answer is $n = \frac{1}{2}(p-1)$ as claimed.

We use derivatives in the following way.
Claim: Define $q_0 = q$ , and $q_{i+1} = x \cdot q_i'$ . Suppose $n$ is such that $q_1$ , \dots, $q_{n-1}$ has $x=1$ as a root, but $q_n$ does not have $x=1$ as a root. Then $n$ is the multiplicity of $x=1$ in $q$ .
Proof. This follows from the fact that $q_{i+1}$ will have multiplicity of $x=1$ one less than in $q_i$ . $\blacksquare$
On the other hand, we may explicitly compute $q_n(1) = \sum_{k=1}^{p-1} k^n \left( \frac kp \right) = \sum_{k \text{ qr}} k^n - \underbrace{2 \sum_{k=1}^{p-1} k^n}_{=0 \text{ for } n < p-1}$ Let $g$ be a primitive root modulo $p$ . The first sum then equals $g^0 + g^{2n} + g^{4n} + \dots + g^{(p-3) n}$ which equals $\frac{p-1}{2}$ if $n = (p-1)/2$ but $\frac{g^{(p-1)n}-1}{g^{2n}-1} = 0$ otherwise.
Consequently, the answer is $n = \frac{1}{2}(p-1)$ as claimed.

Z K Y

The post below has been deleted. Click to close.

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

779 posts

#15 h Nov 11, 2020, 3:01 AM • 1 Y

Y by SK_pi3145

I believe this is a new solution, can someone confirm that it works?

The answer is $\boxed{\frac{p-1}{2}}.$

Work in $\mathbb{F}_p,$ and let $f(n)=n^{(p-1)/2}.$ Additionally, define $S_k(n)$ inductively by $S_0(n)=1$ and $S_{k}(n)=\sum_{i=1}^{n}S_{k-1}(i).$

By synthetic division, it suffices to show the following. $\sum_{i=1}^{p-1}S_{0}(i)f(i)=\sum_{i=1}^{p-1}S_{1}(i-1)f(i)=\sum_{i=1}^{p-1}S_{2}(i-2)f(i)=\dots=\sum_{i=1}^{p-1}S_{(p-3)/2}\left(i-\frac{p-1}{2}\right)f(i)=0,$ $\sum_{i-1}^{p-1}S_{(p-1)/2}\left(i-\frac{p-1}{2}\right)f(i)\ne 0.$ To show that the sums on top evaluate to $0,$ induct from left to right; the base case follows from the fact that the number of nonzero QRs and QNRs are equal.

Now consider the $k$ th sum from the left. By the inductive hypothesis, we may shift to obtain $\sum_{i=1}^{p-1}S_{k-1}(i)f(i).$ Therefore, since $S_{k-1}$ is a polynomial of degree $k-1,$ it suffices to show that $\sum_{i=1}^{p-1}i^{k-1}f(i)=0.$

This follows from Newton's sums on the polynomials $x^{(p-1)/2}\pm 1$ precisely when $k\ne\frac{p-1}{2},$ so we are done.

Z K Y

The post below has been deleted. Click to close.

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

8863 posts

#16 h Oct 21, 2023, 5:47 PM

Y by

Kind of a boring problem; you just keep taking derivatives.

The answer is $\frac{p-1}2$ . Notice that including all terms with negative powers that evaluate to zero, the $n$ th derivative of $q(x)$ is equal to $q^(n')(x) =\sum_{k=1}^{p-1} k^{\frac{p-1}2} \cdot k(k-1)(k-2)\cdots(k-n+1) x^{k-n}.$ In particular, for $n < \frac{p-1}2$ , we can always split this into sums of the form $c\sum_{k=1}^{p-1} k^i$ for some $c \in \mathbb Z$ and $0 \leq i \leq p-2$ . All these sums evaluate to zero modulo $p$ , hence $q^(n')(1) = 0$ .

On the other hand, when $n = \frac{p-1}2$ , the leading $k$ term has exponent $p-1$ , and the sum $c\sum_{k=1}^{p-1} k^{p-1}$ evaluates to $-1$ , and hence the process terminates. It follows by the definition of derivative that the multiplicity of $1$ in $q$ is $\frac{p-1}2$ .

Z K Y

The post below has been deleted. Click to close.

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

4187 posts

#17 h Sep 30, 2024, 9:38 PM

Y by

The answer is $n=\frac{p-1}{2}$ .

Using the Legendre symbol, define $P(x)=\sum_{k=1}^{p-1} \left ( \frac{k}{p} \right )x^k.$
The problem is asking to find the smallest positive integer $n$ such that
$P^{(n)}(1)\not\equiv 0\pmod{p}.$
Using the definition of $P(x)$ , we can explictly write $P^{(n)}(x)$ as
$P^{(n)}(1)=\sum_{QR}r(r-1)\dots(r-n+1)-\sum_{NQR}r(r-1)\dots(r-n+1).$
However, since
$\sum_{NQR}r(r-1)\dots(r-n+1)=\sum_r r(r-1)\dots(r-n+1)-\sum_{QR}r(r-1)\dots(r-n+1),$ we have
$P^{(n)}(1)=2\sum_{QR}r(r-1)\dots(r-n+1)-\sum_r r(r-1)\dots(r-n+1)$ $=\sum_{r}(r^2)(r^2-1)\dots (r^2-n+1)-\sum_r r(r-1)\dots(r-n+1).$
Now, we will use the following lemma (well-known):

Quote:

The sum of $k^m$ over $k=1,2,\dots,p-1$ vanishes mod $p$ unless $p-1\mid m$ .

When $n<\frac{p-1}{2}$ , everything is degree less than $p-1$ , and the constant terms are the same, so everything vanishes. However, when $n=\frac{p-1}{2}$ , the first sum has a non-vanishing component $r^{p-1}$ , so it will not be zero as everything else vanishes. Thus, $n=\frac{p-1}{2}$ fails and we are done.

Z K Y

The post below has been deleted. Click to close.

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

1745 posts

OronSH

#18 h Jan 26, 2025, 1:33 AM • 1 Y

Y by centslordm

Answer $\tfrac{p-1}2$ .

Fix a primitive root $g$ so that $a_{g^i}=(-1)^i$ . Then notice we can write $\sum_{k=1}^{p-1}a_kk^n$ as a sum of $q(1),q'(1),\dots,q^{(n)}(1)$ . In particular to preserve degrees the last term is added once. Thus the first time $q^{(n)}(1)\ne 0$ is the same as the first time $\sum_{k=1}^{p-1}a_kk^n\ne 0$ . However, the idea is that we can rewrite this as $\sum_{i=1}^{p-1}(-g^n)^i$ which equals $g^n\frac{(-g^n)^{p-1}-1}{g^n+1}$ so if this is $\ne 0$ then we must have $g^n=-1$ so $n=\frac{p-1}2$ . In fact for this $n$ we get $\sum_{k=1}^{p-1}a_kk^n=\sum_{k=1}^{p-1}a_k^2=p-1\ne 0$ as desired.

Z K Y

The post below has been deleted. Click to close.

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

627 posts

#19 h Apr 19, 2025, 5:34 AM

Y by

Differentiate and multiply by $x$ $\frac{p - 1}{2} - 1$ times. We are left with $P(x) = \sum_{k = 1}^{p - 1}\frac1{k}x^k$ . Plugging in $x = 1,$ we get that the sum is diviisble by $x - 1.$ Differentiate one more time and we get $\sum_{k = 1}^{p - 1}x^k = \frac{x^k - 1}{x - 1}$ which obviously has 0 powers of $x - 1.$ This implies that there are exactly $\frac{p - 1}{2}$ factors of $x - 1$ in the original expression.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a