Maths Olympiad Prep

Library / /42 of 69

Number theory Difficulty 6.2 National olympiad Prove it Mongolia

Denote Sa=a1+a22++ap1p1S_a = \frac{a}{1} + \frac{a^2}{2} + \dots + \frac{a^{p-1}}{p-1} for any whole number aa. Prove that if for any whole number nn the relation S2n+S2n12SnS2=mkS_{2n} + S_{2n-1} - 2S_n - S_2 = \frac{m}{k}, (where m,km, k are relatively prime) holds then mm is divisible by pp.

Solution

If rational numbers p1q1,p2q2\frac{p_1}{q_1}, \frac{p_2}{q_2} satisfy the conditions q1q2(mod p)q_1 \cdot q_2 \neq (\text{mod } p) and p1q2p2q10(modp)p_1q_2 - p_2q_1 \equiv 0 \pmod{p}, then we write p1q1p2q2(modp)\frac{p_1}{q_1} \equiv \frac{p_2}{q_2} \pmod{p}. Then our task is to show S2n+S2n12SnS20(modp)S_{2n} + S_{2n-1} - 2S_n - S_2 \equiv 0 \pmod{p}.

1pCpk(p1)(p2)(pk+1)k!(1)(2)(k+1)k!(1)k1k(modp). \begin{align*} \frac{1}{p} C_p^k &\equiv \frac{(p-1) \cdot (p-2) \cdots (p-k+1)}{k!} \\ &\equiv \frac{(-1) \cdot (-2) \cdots (-k+1)}{k!} \equiv \frac{(-1)^{k-1}}{k} \pmod{p}. \end{align*}

Proposition 2:
Sa(a1)pap+1p(modp) S_a \equiv \frac{(a-1)^p - a^p + 1}{p} \pmod{p}
** *Proof:* **Sa=k=1p1(a)k(1)k1kk=1p1(a)k1pCpk1p(1(a)p+k=0p1(a)kCpk)(a1)pap+1p(modp) \text{** *Proof:* **} \blacktriangle S_a = - \sum_{k=1}^{p-1} \frac{(-a)^k (-1)^{k-1}}{k} \equiv \sum_{k=1}^{p-1} (-a)^k \frac{1}{p} C_p^k \equiv - \frac{1}{p} \left( -1 - (-a)^p + \sum_{k=0}^{p-1} (-a)^k C_p^k \right) \equiv \frac{(a-1)^p - a^p + 1}{p} \pmod{p} \blacktriangle

By proposition 2, it follows S2n+S2n12SnS21p((2n1)p(2n)p+1+(2n2)p(2n1)p+12(n1)p+2np21+2p1)1p(2p2)((npn)((n1)p(n1)))(modp)S_{2n} + S_{2n-1} - 2S_n - S_2 \equiv \frac{1}{p}((2n-1)^p - (2n)^p + 1 + (2n-2)^p - (2n-1)^p + 1 - 2(n-1)^p + 2n^p - 2 - 1 + 2^p - 1) \equiv -\frac{1}{p}(2^p - 2) \cdot ((n^p - n) - ((n-1)^p - (n-1))) \pmod{p}.

By Fermat's theorem we can write p2p2p \mid 2^p - 2, pnpnp \mid n^p - n, p(n1)p(n1)p \mid (n-1)^p - (n-1). Thus we have S2n+S2n12SnS20(modp)S_{2n} + S_{2n-1} - 2S_n - S_2 \equiv 0 \pmod{p} and the problem is solved.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.