Maths Olympiad Prep

Library / /3 of 16

Number theory Difficulty 5.3 AIME, harder Prove it Brazil

Let q=2p+1q = 2p+1, p,q>0p, q > 0 primes. Prove that there exists a multiple of qq whose digits sum in decimal base is positive and at most 3.

Solution

First notice that 1010 is a multiple of 5=22+15 = 2 \cdot 2 + 1, so we are done if qq and 1010 are not coprime. If qq and 1010 are coprime, since qq is prime, by Fermat's theorem q10q11q102p1q10p1q \mid 10^{q-1} - 1 \Leftrightarrow q \mid 10^{2p} - 1 \Leftrightarrow q \mid 10^p - 1 or q10p+1q \mid 10^p + 1. If q10p+1q \mid 10^p + 1, we are done: the sum of the digits of 10p+110^p + 1 is 22. From now on, suppose that q10p1q \mid 10^p - 1.

Consider the minimum positive integer dd such that 10d1(modq)10^d \equiv 1 \pmod{q}, that is, d=ordq10d = \text{ord}_q 10. Then dpd \mid p, that is, the possible values of dd are 11 and pp. If d=1d = 1, q1011q=3q \mid 10^1 - 1 \Leftrightarrow q = 3, which is not acceptable. So d=pd = p, which means that 1,10,102,,10p11, 10, 10^2, \dots, 10^{p-1} are all distinct mod qq.

Now let A={0}{10k mod q:0k<p}A = \{0\} \cup \{10^k \text{ mod } q : 0 \le k < p\} and B={q1}{110k mod q:0k<p}B = \{q-1\} \cup \{-1 - 10^k \text{ mod } q : 0 \le k < p\}. Since 10k≢0(modq)10^k \not\equiv 0 \pmod{q}, A=B=p+1|A| = |B| = p+1. This and the obvious fact that ABq=2p+1|A \cup B| \le q = 2p+1 implies ABA \cap B \ne \emptyset.

So either there are integers r,sr, s such that 10r110s(modq)10^r \equiv -1 - 10^s \pmod{q}, in which case 10r+10s+110^r + 10^s + 1, whose digit sum is 33, is a multiple of qq, or 10r1(modq)10^r \equiv -1 \pmod{q}, in which 10r+110^r + 1, whose digit sum is 22, is a multiple of qq, or 0110s(modq)0 \equiv -1 - 10^s \pmod{q}, which is analogous to the previous case. So, in all cases, we are done.

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.