Maths Olympiad Prep

Library / /376 of 520

Number theory Difficulty 5.6 AIME, harder Prove it

Example 2 Let pp be an odd prime greater than 3, q=p−12q=\frac{p-1}{2}. Prove: ∑i=0qC2ii≡1( mod p)\sum_{i=0}^{q} \mathrm{C}_{2 i}^{i} \equiv 1(\bmod p) or ∑i=0qC2ii≡−1( mod p)\sum_{i=0}^{q} \mathrm{C}_{2 i}^{i} \equiv-1(\bmod p).

Solution

【Analysis】When p=5p=5,
∑i=02C2ii=1+2+6=9≡−1( mod 5);  \sum_{i=0}^{2} \mathrm{C}_{2 i}^{i}=1+2+6=9 \equiv-1(\bmod 5) \text {; }

When p=7p=7,
∑i=03C2ii=9+20=29≡1( mod 7);  \sum_{i=0}^{3} \mathrm{C}_{2 i}^{i}=9+20=29 \equiv 1(\bmod 7) \text {; }

When p=11p=11,
∑i=05C2ii=29+70+252=351≡−1( mod 11);  \sum_{i=0}^{5} \mathrm{C}_{2 i}^{i}=29+70+252=351 \equiv-1(\bmod 11) \text {; }

When p=13p=13,
∑i=06C2ii=351+924=1275≡1( mod 13);  \sum_{i=0}^{6} \mathrm{C}_{2 i}^{i}=351+924=1275 \equiv 1(\bmod 13) \text {; }

When p=17p=17,
∑i=08C2ii=1275+C147+C168=17577≡−1( mod 17); \begin{array}{l} \sum_{i=0}^{8} C_{2 \mathrm{i}}^{i}=1275+\mathrm{C}_{14}^{7}+\mathrm{C}_{16}^{8}=17577 \\ \equiv-1(\bmod 17) ; \end{array}

When p=19p=19,
∑i=09C2ii=17577+C189=66197≡1( mod 19). \begin{array}{l} \sum_{i=0}^{9} C_{2 i}^{i}=17577+C_{18}^{9}=66197 \\ \equiv 1(\bmod 19) . \end{array}

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.