Prove that there exist a natural number $a$, for which 999 divides $2^{5n}+a.5^n$ for $\forall$ odd $n\in \mathbb{N}$ and find the smallest such $a$.
Problem
Source: X International Festival of Young Mathematicians Sozopol 2019, Theme for 10-12 grade
Tags: number theory, Divisibility, greatest common divisor, modulo
23.09.2019 16:57
a.5?? So like if a=3 then it will be $(3.5)^n$
23.09.2019 17:13
It's not in brackets so no. If $a=3$ then $a.5^n=3.(5^n)$.
23.09.2019 18:24
$2^{5n}+5^na=999k=1000(k-l)+(1000l-k), (k,l)\in \mathbb{N}$ (let $l$. As $1000k$ is always a multiple of 5 and $1000l-k$ isn’t, $5^na=1000k$, and because $1000k$ and $5^n$ are natural, so is $a$. In order to get the smallest $a$, we need $5^na=0 (mod 1000)$. For $n=1$, $a$ must be greater or equal to 200; for n greater than 1, we have $5^n=25 (mod 100)$, so $a$ must be a multiple of 40, and so 200 is. Therefore, $min(a)=200$.
23.09.2019 18:33
Not true. You don't need $5^n.a\equiv (mod 1000)$.
24.09.2019 00:07
Smallest such a is 967. a=999k-32 where k is a natural number is a general solution.
24.09.2019 00:54
Here is a solution.