Prove that given any five integers, there will be three for which the sum of the squares of those integers is divisible by 3.

Any square integer must be congruent to either 0 or 1 mod 3. So for each of the 5 squares, we put it into hole 0 if it is congruent to 0 and into hole 1 if it is congruent to 1. Then take three squares from the hole with at least 3 squares and add them together. You will get either: $0+0+0\equiv 0$ or $1+1+1\equiv0$ mod 3.


The remainder of every integer in dividing by $3$ is either $0$,$1$,or $2$.

Thus the remainder of a square in dividing by $3$ is either $0$ or $1$.

Now we have $5$ perfect squares that means a set of $5$ remainders each of which is either a $0$ or a $1$.

The Pigeon hole principle says there are at least three of the same kind in the set of remainders. Well, we either have $1+1+1$ or $0+0+0$ in our sum of the squares and in either case the sum is divisible by $3$


Any integer is of one of the following forms:

  • $3k + 0$ (these are the multiples of 3)
  • $3k + 1$
  • $3k + 2$

where $k$ is an integer.

If we square these, we get

  • $9k^2$
  • $9k^2 + 6k + 1$
  • $9k^2 + 12k + 4$

If we then look at the remainders of these when divided by $3$, because $9$, $6$, and $12$ are all divisible by $3$, we see that

  • $9k^2 \equiv 0 \pmod 3$
  • $9k^2 + 6k + 1 \equiv 1 \pmod 3$
  • $9k^2 + 12k + 4 \equiv 1 \pmod 3$

So any squared integer is equivalent to $0$ or $1$, modulo $3$.

These will be our two pigeon holes.

Applying the pigeonhole principle to the squares of our 5 integers, we see that either at least 3 have remainder $0$, or at least 3 have remainder $1$. Let's call these 3 integers $x_1$, $x_2$, and $x_3$.

In the former case, $x_i^2 \equiv 0 \pmod 3$ and so the sum of these $x_1^2 + x_2^2 + x_3^2 \equiv 0 + 0 + 0 \pmod 3 \equiv 0 \pmod 3$

In the latter case, $x_i^2 \equiv 1 \pmod 3$ and so the sum of these $x_1^2 + x_2^2 + x_3^2 \equiv 1 + 1 + 1 \pmod 3 \equiv 0 \pmod 3$

QED

Tags:

Discrete Mathematics

Pigeonhole Principle

Related

Proving $\int_0^\pi \frac{\log(1+x\cos (y))}{\cos y}dy=\pi \arcsin x$ Prove that $T_n = 3n^2 -60n + 301$ is positive for every $n$ Easy to understand examples of category theoretic theorems that are useful Evaluate $\int{ \ln(\sqrt{x})dx}$ using integration by parts I wake up in a random class and hear 6 biology-related words. How certain should I be that I'm in Biology class? Proving that $\sum_{n=1}^\infty \frac{\sin\left(n\frac{\pi}{3}\right)}{(2n+1)^2}=\frac{G}{\sqrt 3} -\frac{\pi^2}{24}$ Compressing the primes using simple addition? Having trouble showing a function is continuous: $x/(1+|x|)$ Derive $P \to \neg \neg P$ in a structure with not and implies How do we know our definitions don't lead to contradictions Show that $\int\limits_0^{\frac{\pi}2}4\cos^2(x)\log^2(\cos x)~\mathrm dx=-\pi\log 2+\pi\log^2 2-\frac{\pi}2+\frac{\pi^3}{12}$ How many 5 digit numbers are there, whose i digit is divisible by i?

Recent Posts