Natural $a,b,c$ are pairwise prime. There is infinite table with one integer number in every cell. Sum of numbers in every $a \times a$, every $b \times b$, every $c \times c$ squares is even. Is it true, that every number in table must be even?
Problem
Source: St Petersburg Olympiad 2014, Grade 9, P7
Tags: number theory
27.10.2017 20:21
Yes, every number in the table must be even. Since $\gcd (a,b,c)=1$, there exist integers $x_1,x_2,x_3$ that $ax_1+bx_2+cx_3=1$. Note that all of $x_1,x_2,x_3$ can't be all non-negative. WLOG $x_2$ is a negative one. By Chicken McNugget, for sufficiently large $Z\in \mathbb{Z}^+$, says $Z>C$, there exist positive integers $M,N$ that $Z=aM+cN$. Let $n_1,n_2,n_3$ be positive integers such that $n_2+x_2=0$, $n_1+x_1,n_3+x_3>0$ and $$a(2n_1+x_1)+b(2n_2+x_2)+c(2n_3+x_3)>ac+C, a\mid bn_2+cn_3,b\mid an_1+cn_3-ac,c\mid an_1+bn_2$$(not hard to show that this is possible when $a,b,c$ are pairwise distinct primes.) Since $a(2n_1+x_1)+b(2n_2+x_2)+c(2n_3+x_3)-ac>C$, there exist positive integers $M,N$ that $$a(2n_1+x_1)+b(2n_2+x_2)+c(2n_3+x_3)-ac=aM+cN.$$ We'll call a rectangle "good" iff it can be cover by some squares of size $a\times a$ or $b\times b$ or $c\times c$. Note that $a\times ac$ is good, also $c\times ac$. Hence $(aM+cN)\times ac$ is good too. Also, $ac\times ac$ and $(aM+cN)\times (aM+cN)$ are good (since $2an_1+2cn_3+(ax_1+cx_3-ac)\equiv 0\pmod{b}$.) So, combining $4$ pieces gives us $$(ac+aM+cN)\times (ac+aM+cN)=\Big( a(2n_1+x_1)+b(2n_2+x_2)+c(2n_3+x_3)\Big) \times \Big( a(2n_1+x_1)+b(2n_2+x_2)+c(2n_3+x_3)\Big)$$is good. Note that we can partition $$\Big( a(2n_1+x_1)+b(2n_2+x_2)+c(2n_3+x_3)\Big) \times \Big( a(2n_1+x_1)+b(2n_2+x_2)+c(2n_3+x_3)\Big)$$into $4$ rectangles of size $( an_1+bn_2+cn_3 ) \times \Big( a(n_1+x_1)+b(n_2+x_2)+c(n_3+x_3)\Big)$ and one middle $1\times 1$. This means to prove that the $1\times 1$ contain even number, we've to show that $$( an_1+bn_2+cn_3) \times \Big( a(n_1+x_1)+b(n_2+x_2)+c(n_3+x_3)\Big)$$is good. Since $a(n_1+x_1)+b(n_2+x_2)+c(n_3+x_3) =a(n_1+x_1)+c(n_3+x_3)$, we partition the rectangle into some $a\times ( an_1+bn_2+cn_3)$ and $c\times ( an_1+bn_2+cn_3)$. But since $a\mid an_1+bn_2+cn_3$ and $c\mid an_1+bn_2+cn_3$, we can further partition those rectangles into $a\times a$ and $c\times c$, respectively, which means they are good, done.