OIMC 2021 P2: NT Polynomial

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

OIMC 2021 P2: NT Polynomial

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: OIMC 2021 P2 (mock contest)

The post below has been deleted. Click to close.

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

1721 posts

oVlad

#1 h Aug 18, 2021, 12:01 PM • 8 Y

Y by phoenixfire, EpicNumberTheory, i3435, KPBY0507, Orestis_Lignos, brickmaster8, megarnie, Rounak_iitr

Let $p>3$ be a prime number and $m$ a positive integer such that $p$ divides $m^2-m+1.$ Prove that $p$ divides the numerator of $P(m)$ written in lowest terms, where $P$ is a polynomial defined as follows $P(x):=\sum_{i=1}^{p-1}\frac{x^i}{i}.$ Proposed by Alexandru Gica, Romania

This post has been edited 2 times. Last edited by oVlad, Sep 11, 2021, 9:16 AM

Z K Y

The post below has been deleted. Click to close.

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

478 posts

#2 h Aug 18, 2021, 12:10 PM • 1 Y

Y by oVlad

My favourite problem on the test :-)

:-)

Solution

This post has been edited 4 times. Last edited by Sprites, Aug 18, 2021, 1:39 PM

Z K Y

The post below has been deleted. Click to close.

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

892 posts

#3 h Aug 18, 2021, 12:26 PM • 1 Y

Y by oVlad

Here $C(p,k)$ shows the coefficent of $x^k$ in $(x+1)^p$

$\textbf{Lemma:}$ For $1\le k\le p-1$ , $\frac{1}{k}\equiv \frac{1}{p} (-1)^{k-1} C(p,k) (mod p)$
$\textbf{Proof:}$ $C(p,k)= \frac{p}{k}\cdot \frac{(p-1)!}{(p-k)!(k-1)!}=\frac{(p-k)!(p-k+1)(p-k+2)\cdot ... \cdot (p-1)}{(p-k)!(k-1)!}\cdot \frac{p}{k}$ $\equiv \frac{(p-k)!(k-1)!(-1)^{k-1}}{(p-k)!(k-1)!} \cdot \frac{p}{k}=(-1)^{k-1}\cdot \frac{p}{k} \implies \frac{1}{k}\equiv \frac{1}{p} (-1)^{k-1} C(p,k) (mod p).\square$
$P(x)=\sum_{i=1}^{p-1} \frac{x^i}{i} \equiv -\frac{1}{p} \sum_{i=1}^{p-1} x^i(-1)^kC(p,i)=-\frac{1}{p}((-x+1)^p+x^p-1))=\frac{1}{p}((x-1)^p-x^p+1)$

We want to prove that $p|P(m)=\frac{1}{p}((m-1)^p-m^p+1)$ or $p^2|(m-1)^p-m^p+1$ .

$\textbf{Claim:}$ $a\equiv b (mod p) \implies a^p \equiv b^p (mod p^2)$

$\textbf{Proof:}$ $a^p-b^p=(a-b)(a^{p-1}+a^{p-2}b+...+ab^{p-2}+b^{p-1})$ . Because we have $a\equiv b (mod p)$ , $a-b \equiv 0(mod p)$ ,
$a^{p-1}+a^{p-2}b+...+ab^{p-2}+b^{p-1} \equiv pa^{p-1} \equiv 0 (mod p)$ we have $p^2|a^p-b^p$ as desired. $\square$

By the claim and noting that $m^2\equiv m-1(mod p)$ we have $(m-1)^p-m^p+1 \equiv m^{2p}-m^p+1 (mod p^2)$ .

We have $m^p+1 \equiv m+1 (mod p)$ . If $p|m^p+1$ then $m \equiv -1( mod p)$ and $m^2-m+1 \equiv 3 (modp)$ which shows we cannot have $p|m^p+1$ because $p>3$ .

Thus $p^2|(m-1)^p-m^p+1 \leftrightarrow p^2|m^{2p}-m^p+1 \leftrightarrow p^2|(m^p+1)(m^{2p}-m^p+1)\leftrightarrow p^2|m^{3p}+1$ . $m^3+1=(m+1)(m^2-m+1) \equiv 0 (modp)$ . So from the claim $m^3\equiv -1 (mod p) \implies m^{3p} \equiv -1(mod p^2)$ as desired.

Z K Y

The post below has been deleted. Click to close.

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

96 posts

#4 h Aug 18, 2021, 12:29 PM • 1 Y

Y by oVlad

See 2011 ISL N7

https://artofproblemsolving.com/community/c6h488544p2737656

This post has been edited 1 time. Last edited by KPBY0507, Aug 18, 2021, 12:40 PM

Z K Y

The post below has been deleted. Click to close.

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

429 posts

hakN

#5 h Aug 18, 2021, 2:23 PM • 2 Y

Y by oVlad, MrOreoJuice

Also a very similar problem : ELMO 2009 P6

Z K Y

The post below has been deleted. Click to close.

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

495 posts

NJOY

#6 h Aug 18, 2021, 2:39 PM • 15 Y

Y by rama1728, oVlad, Hyperbolic_, Orestis_Lignos, lneis1, Prabh2005, CantonMathGuy, phoenixfire, BVKRB-, nixon0630, SK_pi3145, Aritra12, amar_04, Bongcloud, lazizbek42

I found the exact same problem though here

Z K Y

The post below has been deleted. Click to close.

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

1721 posts

oVlad

#7 h Aug 18, 2021, 2:41 PM • 1 Y

Y by KPBY0507

@above Haha,good one, you got me!

This post has been edited 1 time. Last edited by oVlad, Aug 18, 2021, 2:43 PM

Z K Y

The post below has been deleted. Click to close.

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

396 posts

#8 h Aug 19, 2021, 1:35 AM

Y by

My solution...
This is very similar to USA Team Selection Test -2 2017 P-3..

Attachments:

OIMC - P-2 MATBOY_compressed.pdf (295kb)

This post has been edited 1 time. Last edited by MatBoy-123, Aug 19, 2021, 1:45 AM

Z K Y

The post below has been deleted. Click to close.

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

1721 posts

oVlad

#9 h Aug 20, 2021, 10:41 AM

Y by

Here's the official solution:

We begin by proving two claims, which we will use later on.

Claim 1: For any positive integer $k, \ P(k+1)\equiv P(-k)\pmod{p}.$

Proof: We will begin by rewriting $P(x+1)$ using the binomial expansion, as follows $P(x+1)=\sum_{i=1}^{p-1}\frac{(x+1)^k}{k}=\sum_{i=1}^{p-1}\sum_{j=1}^{i}\binom{i}{j}\frac{x^j}{k}+\sum_{i=1}^{p-1}\frac{1}{i}=\sum_{i=1}^{p-1}\bigg(x^i\sum_{j=i}^{p-1}\frac{1}{j}\binom{j}{i}\bigg)+\sum_{i=1}^{p-1}\frac{1}{i}.$ Moreover, observe that we can rewrite $\binom{j}{i}j^{-1}$ like such $\frac{1}{j}\binom{j}{i}=\frac{1}{j}\cdot\frac{j!}{i!\cdot(j-1)!}=\frac{(j-1)!}{(i-1)!\cdot(j-i)!}\cdot\frac{1}{i}=\binom{j-1}{i-1}\frac{1}{i}.$ Therefore, by substituting in the first equation we can deduce that

$P(x+1)=\sum_{i=1}^{p-1}\bigg(\frac{x^i}{i}\sum_{j=i}^{p-1}\binom{j-1}{i-1}\bigg)+\sum_{i=1}^{p-1}\frac{1}{i}.$ Notice that the coefficient of $x^i$ can furthermore be computed via the Hockeystick Identity $\sum_{j=i}^{p-1}\binom{j-1}{i-1}=\binom{p-1}{i}\implies P(x+1)=\sum_{i=1}^{p-1}\frac{x^i}{i}\binom{p-1}{i}+\sum_{i=1}^{p-1}\frac{1}{i}.$ We will now proceed to analyse $P(k+1)$ modulo $p.$ Observe that $\binom{p-1}{i}=\frac{(p-1)!}{i!\cdot(p-i-1)!}\equiv (-1)^{i}\frac{(p-1)!}{(p-1)!}\equiv (-1)^i\pmod{p}.$ Finally, introducing this into the formula we have previously deduced, we get $P(k+1)=\sum_{i=1}^{p-1}\frac{k^i}{i}\binom{p-1}{i}+\sum_{i=1}^{p-1}\frac{1}{i}\equiv\sum_{i=1}^{p-1}\frac{k^i\cdot (-1)^i}{i}+\sum_{i=1}^{p-1}\frac{1}{i}\equiv P(-k)+\sum_{i=1}^{p-1}\frac{1}{i}\pmod{p}.$ However, the sum of all inverses of the residues modulo $p$ is clearly equal to the sum of all residues modulo $p$ themselves, $p(p-1)/2,$ which is divisible by $p.$

Thus, $P(k+1)\equiv P(-k)\pmod{p}.$

Claim 2: For any positive integer $k$ such that $p\nmid k, \ P(k)\equiv -k\cdot P(1/k)\pmod{p}.$

Proof: To achieve this congruence, we simply manipulate $P(k)$ as follows

$P(k)=\sum_{i=1}^{p-1}\frac{k^i}{i}=\sum_{i=1}^{p-1}\frac{k^{p-i}}{p-i}\equiv -k^p\sum_{i=1}^{p-1}\frac{(1/k)^i}{i}\equiv -k\cdot P(1/k)\pmod{p}.$ Notice that $p\mid m^2-m+1\implies m\equiv 1-1/m\pmod{p}$ and $m\not\equiv 0\pmod{p}.$ Therefore $P(m)\equiv P\bigg(1-\frac{1}{m}\bigg)\equiv\text{(by claim 1) }P\bigg(\frac{1}{m}\bigg)\equiv\text{(by claim 2) }\frac{P(m)}{-m}\pmod{p}.$ If $p\nmid P(m)$ then $m\equiv -1\pmod{p}$ and so $0\equiv m^2-m+1\equiv 3\pmod{p}.$ Since $p\neq 3$ this is clearly a contradiction and thus, $p$ must divide $P(m).$ This finishes the proof.

Z K Y

The post below has been deleted. Click to close.

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

181 posts

hyay

#10 h Aug 20, 2021, 10:50 AM • 3 Y

Y by oVlad, megarnie, Aritra12

My solution is pretty much brute force using summations...
Solution

Z K Y

The post below has been deleted. Click to close.

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

71 posts

PUjnk

#11 h Aug 21, 2021, 4:22 PM • 1 Y

Y by oVlad

Lemma: If $p \mid a^2+a+1$ , then $(a+1)^p \equiv a^p+1 (mod p^2)$ .
{proof}:
We have $p \mid x^2+x+1 \Longrightarrow x^3 \equiv 1 mod p \Longrightarrow p \equiv 1 (mod 3)$ (since order of x mod p is 3 as $x \neq 1 (mod p)$ ).
Let $f(x)=(x+1)^p-x^p-1$ . We prove $(x^2+x+1)^2 \mid f(x)$ .
Note that $f(w)=(w+1)^p-w^p-1=-w^{2p}-w^p-1=-(w^2+w+1)=0$ when w is a cube root of unity.
Now note that $f'(x)=p[(x+1)^{p-1}-x^{p-1}]$ .
So $f'(w)=p[w^{2(p-1)}-w^{p-1}]=0 \forall$ w which are cube roots of unity since $p \equiv 1 mod 3$ .
So each cube root of unity has multiplicity atleast 2 in f.
Now observing $(x-w)(x-w^2)=x^2+x+1$ where w is a cube root of unity proves the claim.

Now let $a \equiv -m (mod p)$ .
Then $p \mid a^2+a+1$ .
Now note that $\frac{(-1)^{i-1}p}{i} \equiv {p \choose i} (mod p^2)$ .
So it suffices to show $\sum_{i=1}^{p-1} {p \choose i} a^i$ (by multiplying, desired conclusion, by p).

$\iff p^2 \mid (1+a)^p-a^p-1$ . But we know this is true by the Lemma. This completes the problem.

This post has been edited 1 time. Last edited by PUjnk, Aug 21, 2021, 4:29 PM
Reason: typo

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a