Four consecutive three-digit numbers are divided respectively by four consecutive two-digit numbers. What minimum number of different remainders can be obtained? (A. Golovanov)
Problem
Source: Tuymaada 2014, Day 1, Problem 1, Senior League
Tags: modular arithmetic, number theory, greatest common divisor, least common multiple, relatively prime, number theory proposed, Tuymaada
13.07.2014 20:07
$100=1*51+49, 101=1*52+49, 102=1*53+49, 103=1*54+49$
13.07.2014 20:45
In fact, we can find all the possible solutions. Let the four three-digit numbers be $x,x+1,x+2,x+3$ and the moduli be $a,a+1,a+2,a+3$, the common remainder $r$. Then we have $x+i\equiv r\pmod{a+i}$ for $i=0,1,2,3$, rewritable as $x-r-a\equiv 0 \pmod{a+i}$. Put $y=x-r-a$, then $a+i|y$ for $i=0,1,2,3$. Note that $a,a+1$ and $a+2,a+3$ are relatively prime, so this implies $a(a+1)|y$ and $(a+2)(a+3)|y$. Here $\text{gcd}(a,(a+2)(a+3))|6$ and $\text{gcd}(a+1,(a+2)(a+3))|2$, meaning that $\text{gcd}(a(a+1),(a+2)(a+3))|12$. So we get $\text{lcm}(a(a+1),(a+2)(a+3))|y$, and hence if $y\neq 0$, then \[|y|\ge \text{lcm}(a(a+1),(a+2)(a+3))\ge\] \[\ge \frac{a(a+1)(a+2)(a+3)}{12}\ge \frac{10\cdot 11\cdot 12\cdot 13}{12}>1000,\] where $x\ge y=x-a-r$, so if $y>0$, then this contradicts $x$ having only three digits, and if $y<0$, then as $a+r<2a<200$, we find $x<0$. Therefore $y=0$ and $x=a+r$. So all the solutions are given by $x=a+r$, where $r<a<100$ is arbitrary with $r+a\ge 100$.
14.07.2014 11:54
For history, jury wanted to ask: Four consecutive three-digit numbers GREATER THAN 200 are divided respectively by four consecutive two-digit numbers. What minimum number of different remainders can be obtained?
04.03.2015 04:19
What is the Tuymaada math contest?
04.03.2015 14:23
I'm guessing this: http://en.wikipedia.org/wiki/Tuymaada