A positive integer is called $\emph{lucky}$ if it is divisible by $7$, and the sum of its digits is also divisible by $7$. Fix a positive integer $n$. Show that there exists some lucky integer $l$ such that $\left|n - l\right| \leq 70$.
Problem
Source: PMO 2021
Tags: algebra, number theory, PMO
20.03.2021 13:47
go_placidly wrote: A positive integer is called $\emph{lucky}$ if it is divisible by $7$, and the sum of its digits is also divisible by $7$. Fix a positive integer $n$. Show that there exists some lucky integer $l$ such that $\left|n - l\right| \leq 70$. Let $n=\overline{muv}$ where $m=\left\lfloor\frac n{100}\right\rfloor$ and $u,v\in\{0,1,2,...,8,9\}$ Let $S(m)$ be the sum of digits of $m$ Let $a\equiv 4S(m)+6m\pmod 7$ where $a\in\{0,1,2,3,4,5,6\}$ Let $b\equiv 2S(m)+m\pmod 7$ where $b\in\{0,1,2,3,4,5,6\}$ Note that $l=\overline{mab}$ is a lucky number. If $u\le 6$, then $|l-n|\le 70$. Q.E.D. If $u\ge 7$ and $a\ge 3$, then $|l-n|\le 70$. Q.E.D. If $u\ge 7$ and $a<3$, and $l1=\overline{m(a+7)b}$ is a lucky number too and $|l1-n|\le 70$. Q.E.D.
20.03.2021 16:29
pco wrote: go_placidly wrote: A positive integer is called $\emph{lucky}$ if it is divisible by $7$, and the sum of its digits is also divisible by $7$. Fix a positive integer $n$. Show that there exists some lucky integer $l$ such that $\left|n - l\right| \leq 70$. Let $n=\overline{muv}$ where $m=\left\lfloor\frac n{100}\right\rfloor$ and $u,v\in\{0,1,2,...,8,9\}$ Let $S(m)$ be the sum of digits of $m$ Let $a\equiv 4S(m)+6m\pmod 7$ where $a\in\{0,1,2,3,4,5,6\}$ Let $b\equiv 2S(m)+m\pmod 7$ where $b\in\{0,1,2,3,4,5,6\}$ Note that $l=\overline{mab}$ is a lucky number. If $u\le 6$, then $|l-n|\le 70$. Q.E.D. If $u\ge 7$ and $a\ge 3$, then $|l-n|\le 70$. Q.E.D. If $u\ge 7$ and $a<3$, and $l1=\overline{m(a+7)b}$ is a lucky number too and $|l1-n|\le 70$. Q.E.D. Why did you prove only for a 3 digit number n?Also the number is chosen by you with some conditions?Don't we have to prove it for any n?
20.03.2021 16:58
a_bc wrote: Why did you prove only for a 3 digit number n?Also the number is chosen by you with some conditions?Don't we have to prove it for any n? 1) No. As I clearly wrote, $m=\left\lfloor\frac n{100}\right\rfloor$ and so $m$ is the whole part left to the two rightmost digits. 2) The number is not chosen " with some conditions". Where did you see any condition over $n$ ? I choosed with some condition the lucky number $l$ (or $l1$) - which seems quite normal : the requested lucky number depends on the initial $n$ ... .
20.03.2021 17:11
Examples : 1) $n=112864$ $m=1128$ $S(m)=12$ $a=4\times 12+6\times 1128=6816\equiv 5\pmod 7$ $b=2\times 12+1128=1152\equiv 4\pmod 7$ And so $l=\overbrace{1128}^m\overbrace 5^a\overbrace 4^b$ which indeed is lucky and such that $|112864-112854|\le 70$ 2) $n=112097$ $m=1120$ $S(m)=4$ $a=4\times 4+6\times 1120=6736\equiv 2\pmod 7$ $b=2\times 4+1120=1128\equiv 1\pmod 7$ And so $l=\overbrace{1120}^m\overbrace 2^a\overbrace 1^b$ which indeed is lucky but not such that $|112097-112021|\le 70$ So we choose $l_1=\overbrace{1120}^m\overbrace 9^{a+7}\overbrace 1^b$ which indeed is lucky and such that $|112097-112091|\le 70$
25.03.2021 05:57
How to proof that $ \overline{mab} $ is always divisible by $ 7 $
25.03.2021 09:32
ineqcfe wrote: How to proof that $ \overline{mab} $ is always divisible by $ 7 $ Because it is $100m+10a+b\equiv 100m+10(4S(m)+6m)+(2S(m)+m)\equiv 161m+42S(m)=7(23m+6S(m))\equiv 0\pmod 7$