Denote by $a \bmod b$ the remainder of the euclidean division of $a$ by $b$. Determine all pairs of positive integers $(a,p)$ such that $p$ is prime and \[ a \bmod p + a\bmod 2p + a\bmod 3p + a\bmod 4p = a + p. \]
Problem
Source: Iberoamerican Olympiad 2005
Tags: number theory solved, number theory
manuel
29.09.2005 23:35
is $p$ a prime?
cyshine
01.10.2005 03:41
Oh yes, $p$ is a prime. Sorry. I edited the statement.
Pascual2005
02.10.2005 23:16
modulo $p$ we get $3a=0$ so $p=3$ or $a=0$ modp With $p=3$ we need to check cases, since our expression is at most $2+5+8+11=26$ so a is at most $23$ (I checked them manually actually) With $a=0$ mod p, we can use that $ap$ mod $bp$=$p(a$mod$b)$. And it also reduces to check some cases. The solutions $(p,3p)$ and $(3,1)$, $(3,17)$
RMACR7LP
02.01.2018 20:55
The idea is to consider cases of $a$ that depend on $p$. Notice that the remainders can be at most $p-1, 2p-1, 3p-1, 4p-1$ respectively. and thus $a$ is at most $9p-4$ for a given prime. Now consider cases $a<p, p\leq a<2p, 2p \leq a<3p,..., 8p \leq a<9p$. For each case because of division algorithm, $a mod kp$ is equal to the difference between $a$ and the greatest multiple of $k$ that is less or equal than the lower bound, so for example if we're considering the case $5p \leq a<6p$ we would have,
\[a mod p = a-5p, a mod 2p=a-4p, a mod 3p= a-3p, a mod 4p=a-4p\]when examining all the cases we see that there are valid solutions only when $a<p$ and $5p\leq a<6p$ namely, $(1,3)$ and $(17,3)$.