2017 Indonesia MO Problems/Problem 6

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.

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

Page

Toolbox

Search

2017 Indonesia MO Problems/Problem 6

Problem

Solution

See Also