Maximum number of colours we can use to colour all the integers so that for any integers i,j, i and j have the same colour if |i-j|=38 or |i-j|=27?

Question

I tried solving this by plugging in a few smaller values for the differences, and it turns out that whenever the differences are coprime numbers, 1 colour is required. However, I couldn't construct the proof formally.

I referred to someone's solution, and all it said was "The proof can be done using Bezout's theorem." I didn't really understand how Bezout's theorem is used here, except the fact that the solution has a relation with the gcd's of the differences. Could someone please provide me a formal proof, as well as some explanation of how Bezout's theorem comes into this?

Answer 1

Bezout's theorem says that because $\gcd(38, 27)=1$, there are integers $x,y$ such that $38x + 27y = 1$. (In particular, we have $38 \cdot 5 + 27 \cdot (-7) = 1$.)

We can use this to show that any two adjacent integers must have the same color. For each $n$:

• $n$ has the same color as $n + 38, n + 2 \cdot 38, n + 3 \cdot 38, n + 4 \cdot 38, n + 5 \cdot 38$.
• $n + 5 \cdot 38$ has the same color as $n + 5 \cdot 38 - 27$ through $n + 5 \cdot 38 - 7\cdot 27$.
• Therefore $n$ has the same color as $n + 5\cdot 38 - 7 \cdot 27$, which simplifies to $n+1$.

Actually using Bezout's theorem is only necessary if we want to generalize $38$ and $27$ to any two relatively prime integers $a,b$. (The proof is the same, except in terms of the $x$ and $y$ such that $ax+by=1$.)