The missing factor of p in the IMO harmonic-sum congruence

kirbyonwifi·Jan 14, 2025(edited)

I can use Fermat on each power, but the denominators stop that from proving the numerator is divisible by

p

. Is there a way to package the whole sum before reducing it? Problem: Let

p

be an odd prime number. For every integer

a

, define the number

S_{a} = \frac{a}{1} + \frac{a^{2}}{2} + \cdots + \frac{a^{p-1}}{p-1}.

Let

m

and

n

be integers such that

S_{3} + S_{4} - 3 S_{2} = \frac{m}{n}

Prove that

p

divides

m

. Source: IMO 2011 Shortlist · MNET-06RO

Open MNET-06RO in the question bank →

6 replies

no_mp_left·Jan 14, 2025(edited)

The useful coefficient is

\binom pk/p

. For

1\le k<p

, it is an integer and is congruent to

(-1)^{k-1}/k

modulo

p

. All denominators here are invertible modulo

p

kirbyonwifi·Jan 14, 2025(edited)

So this is a binomial expansion in disguise? I tried

(1+a)^p

, but the signs didn't line up.

no_mp_left·Jan 14, 2025(edited)

Use

(1-a)^p

. It gives

S_a\equiv((a-1)^p-a^p+1)/p\pmod p

. This quotient is an integer, by Fermat; we are not dividing a congruence by a noninvertible residue.

ctrl_alt_yeet·Jan 15, 2025(edited)

Substitution now turns

S_3+S_4-3S_2

into

(4\cdot2^p-4^p-4)/p=-(2^p-2)^2/p

modulo

p

. The square is the extra factor you were missing.

kirbyonwifi·Jan 15, 2025

Since

p\mid2^p-2

, the numerator has

p^2

, so the integer quotient still has

p

. That distinction about dividing the congruence was exactly my sticking point.

no_mp_left·Jan 15, 2025

To finish for the displayed fraction

m/n

, first put the sum over a common denominator not divisible by

p

. Its numerator is divisible by

p

. Cross-multiplication with

m/n

then forces

p\mid m

, even if that representation is not reduced.

Join the discussion

A hint, a different approach, or a thoughtful question can help.

Loading discussion…

The missing factor of p in the IMO harmonic-sum congruence

kirbyonwifi·Jan 14, 2025(edited)

I can use Fermat on each power, but the denominators stop that from proving the numerator is divisible by

p

. Is there a way to package the whole sum before reducing it? Problem: Let

p

be an odd prime number. For every integer

a

, define the number

S_{a} = \frac{a}{1} + \frac{a^{2}}{2} + \cdots + \frac{a^{p-1}}{p-1}.

Let

m

and

n

be integers such that

S_{3} + S_{4} - 3 S_{2} = \frac{m}{n}

Prove that

p

divides

m

. Source: IMO 2011 Shortlist · MNET-06RO

Open MNET-06RO in the question bank →

6 replies

no_mp_left·Jan 14, 2025(edited)

The useful coefficient is

\binom pk/p

. For

1\le k<p

, it is an integer and is congruent to

(-1)^{k-1}/k

modulo

p

. All denominators here are invertible modulo

p

kirbyonwifi·Jan 14, 2025(edited)

So this is a binomial expansion in disguise? I tried

(1+a)^p

, but the signs didn't line up.

no_mp_left·Jan 14, 2025(edited)

Use

(1-a)^p

. It gives

S_a\equiv((a-1)^p-a^p+1)/p\pmod p

. This quotient is an integer, by Fermat; we are not dividing a congruence by a noninvertible residue.

ctrl_alt_yeet·Jan 15, 2025(edited)

Substitution now turns

S_3+S_4-3S_2

into

(4\cdot2^p-4^p-4)/p=-(2^p-2)^2/p

modulo

p

. The square is the extra factor you were missing.

kirbyonwifi·Jan 15, 2025

Since

p\mid2^p-2

, the numerator has

p^2

, so the integer quotient still has

p

. That distinction about dividing the congruence was exactly my sticking point.

no_mp_left·Jan 15, 2025

To finish for the displayed fraction

m/n

, first put the sum over a common denominator not divisible by

p

. Its numerator is divisible by

p

. Cross-multiplication with

m/n

then forces

p\mid m

, even if that representation is not reduced.