2017 Indonesia MO Problems/Problem 6

Revision as of 01:33, 13 August 2018 by Rockmanex3 (talk | contribs) (Solution to Problem 6 — another nice NT problem)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Problem

Find the number of positive integers $n$ not greater than 2017 such that $n$ divides $20^n + 17k$ for some positive integer $k$.

Solution

Let $n = 2^a \cdot 5^b \cdot c,$ where $c$ is relatively prime to $20.$


Since $2^a > a$ for all $a$ greater than or equal to 1, we have $2^{(2^a)} + 17k \equiv 17k \pmod{2^a}.$ When $k \equiv 0 \pmod{2^a},$ the value $17k$ is congruent to $0$ modulo $2^a.$ By using similar steps, we can also show that if $k \equiv 0 \pmod{5^b},$ the value $17k$ is congruent to $0$ modulo $5^b.$


Taking the equation modulo $c$ and using Fermat's Little Theorem, we have $20^c + 17k \equiv 20 + 17k \pmod{c}.$ In order for that to be a multiple of $c,$ then $17k \equiv -20 \pmod{c}.$ As long as $c$ is relatively prime to $17,$ we can find a $k$ where $17k \equiv -20 \pmod{c}.$


We have shown that we can find a $k$ if $n$ is a power of 2, power of 5, or a number relatively prime to 20 that is not a multiple of 17. By the Chinese Remainder Theorem, that means we can find a value $k$ for all numbers that are not a multiple of 17. There are $2017 - \lfloor \tfrac{2017}{17} \rfloor = \boxed{1899}$ numbers less than $2017$ that meet the criteria.

See Also

2017 Indonesia MO (Problems)
Preceded by
Problem 5
1 2 3 4 5 6 7 8 Followed by
Problem 7
All Indonesia MO Problems and Solutions
Invalid username
Login to AoPS