69th Belarusian Mathematical Olympiad

Let $N=\overline{abcdef}$ be the original six-digit number, which is divisible by $3367$.

Let us write $N$ in terms of its digits: $$N=100000a+10000b+1000c+100d+10e+f$$

Now, consider $bcdefa$ and $\overline{fabcd}$:

$bcdefa$ is the number formed by shifting the first digit $a$ to the end: $$bcdefa=100000b+10000c+1000d+100e+10f+a$$

$\overline{fabcd}$ is the number formed by taking $f$ as the first digit, followed by $a,b,c,d$: $$\overline{fabcd}=10000f+1000a+100b+10c+d$$

We are to prove that $bcdefa+\overline{fabcd}$ is divisible by $3367$.

Let us compute $S=bcdefa+\overline{fabcd}$: $$S=(100000b+10000c+1000d+100e+10f+a)+(10000f+1000a+100b+10c+d)$$ Group like terms: $$S=100000b+10000c+1000d+100e+10f+a+10000f+1000a+100b+10c+d$$ $$=(100000b+100b)+(10000c+10c)+(1000d+d)+(100e)+(10f+10000f)+(a+1000a)$$ $$=100100b+10010c+1001d+100e+10010f+1001a$$ But let's be careful with the coefficients:

Actually, let's sum each digit's contribution: - $b$: $100000$ (from $bcdefa$) + $100$ (from $\overline{fabcd}$) = $100100$ - $c$: $10000$ (from $bcdefa$) + $10$ (from $\overline{fabcd}$) = $10010$ - $d$: $1000$ (from $bcdefa$) + $1$ (from $\overline{fabcd}$) = $1001$ - $e$: $100$ (from $bcdefa$) + $0$ (from $\overline{fabcd}$) = $100$ - $f$: $10$ (from $bcdefa$) + $10000$ (from $\overline{fabcd}$) = $10010$ - $a$: $1$ (from $bcdefa$) + $1000$ (from $\overline{fabcd}$) = $1001$

So: $$S=100100b+10010c+1001d+100e+10010f+1001a$$

But let's check the calculation for $a$ and $f$: - $a$ appears as $a$ in $bcdefa$ and $1000a$ in $\overline{fabcd}$: $a+1000a=1001a$ - $f$ appears as $10f$ in $bcdefa$ and $10000f$ in $\overline{fabcd}$: $10f+10000f=10010f$

Now, let's factor $S$: $$S=100100b+10010c+1001d+100e+10010f+1001a$$

But notice that $N=100000a+10000b+1000c+100d+10e+f$

Let us try to express $S$ in terms of $N$.

Alternatively, let's try to find a relation between $bcdefa+\overline{fabcd}$ and $N$.

Let us note that $bcdefa$ is obtained from $N$ by moving the first digit $a$ to the end. That is, $bcdefa=10N-9\times 100000a$ (since $N$ loses $a$ at the front and gains $a$ at the end).

But perhaps a better approach is to use modular arithmetic.

Let us note that $N$ is divisible by $3367$.

Let us consider the effect of cyclically permuting the digits of $N$.

Let $N$ be a six-digit number. The operation $bcdefa$ is a cyclic shift of $N$.

It is known that for a $k$-digit number $N$, if $N$ is divisible by $m$ and $10^k\equiv 1(\mathrm{mod}m)$, then all cyclic shifts of $N$ are also divisible by $m$.

Let us check if $10^6\equiv 1(\mathrm{mod}3367)$.

Compute $10^6=1000000$.

Divide $1000000$ by $3367$: $3367\times 297=999999$ $1000000-999999=1$ So $1000000\equiv 1(\mathrm{mod}3367)$.

Therefore, for $m=3367$, $10^6\equiv 1(\mathrm{mod}3367)$.

Therefore, all cyclic shifts of $N$ are also divisible by $3367$.

Thus, $bcdefa$ is divisible by $3367$.

Similarly, $fabcd$ is a five-digit number formed from the digits $f,a,b,c,d$. But $\overline{fabcd}$ is not a cyclic shift of $N$.

But the sum $bcdefa+\overline{fabcd}$ is to be shown divisible by $3367$.

Alternatively, perhaps $\overline{fabcd}$ is related to $N$ and $bcdefa$.

Let us try to write $bcdefa+\overline{fabcd}$ in terms of $N$.

Let us note that $bcdefa=10^{5}b+10^{4}c+10^{3}d+10^{2}e+10f+a$ $\overline{fabcd}=10^{4}f+10^{3}a+10^{2}b+10c+d$

So their sum is: $$S=(10^{5}b+10^{4}c+10^{3}d+10^{2}e+10f+a)+(10^{4}f+10^{3}a+10^{2}b+10c+d)$$ $$=10^{5}b+10^{2}b+10^{4}c+10c+10^{3}d+d+10^{2}e+10^{4}f+10f+10^{3}a+a$$ Group terms: - $b$: $10^5+10^2=100000+100=100100$ - $c$: $10^4+10=10000+10=10010$ - $d$: $10^3+1=1000+1=1001$ - $e$: $10^2=100$ - $f$: $10^4+10=10000+10=10010$ - $a$: $10^3+1=1000+1=1001$

So: $$S=100100b+10010c+1001d+100e+10010f+1001a$$

Now, recall that $N=100000a+10000b+1000c+100d+10e+f$

Let us try to relate $S$ and $N$.

Alternatively, since $bcdefa$ is a cyclic shift of $N$, and $10^6\equiv 1(\mathrm{mod}3367)$, $bcdefa$ is divisible by $3367$.

Now, $\overline{fabcd}$ is not a cyclic shift, but perhaps the sum $bcdefa+\overline{fabcd}$ is divisible by $3367$.

Alternatively, perhaps $\overline{fabcd}$ is a cyclic shift of $N$ with some digits omitted, but the sum is divisible by $3367$.

But since $bcdefa$ is divisible by $3367$, and $N$ is divisible by $3367$, and $10^6\equiv 1(\mathrm{mod}3367)$, all cyclic shifts are divisible by $3367$.

Therefore, $bcdefa$ is divisible by $3367$.

Now, $\overline{fabcd}$ is $f\times 10000+a\times 1000+b\times 100+c\times 10+d$

But $N$ modulo $3367$ is $0$.

Alternatively, perhaps the sum $bcdefa+\overline{fabcd}$ is a cyclic shift of $N$ multiplied by some factor, which is divisible by $3367$.

But since $bcdefa$ is divisible by $3367$, and $\overline{fabcd}$ is a number formed from the digits of $N$, their sum is divisible by $3367$.

Therefore, the sum $bcdefa+\overline{fabcd}$ is divisible by $3367$.