# Prime number proof for tiling a rectangle

The following theorem has many proofs, several of which are highlighted in this document.

Whenever a large rectangle is tiled by rectangles, each of which has at least one integer side - the large rectangle has at least one integer side, too.

The document has a proof using prime numbers and scaling:

Prime numbers (Raphael Robinson, Univ. of California, Berkeley) We claim that for each prime $p$, either the height or width of $R$ is within $1/p$ of an integer. It follows that one of these is an integer. To prove the claim, scale the entire tiling up by a factor of $p$ in each direction, and consider the tiling obtained by replacing all tile-corners $(x, y)$ in the scaled-up tiling by $([x], [y])$. This yields an integer-sided rectangle tiled by integer-sided rectangles, each of which has one side a multiple of $p$. Therefore, the area of the large integer-sided rectangle is a multiple of $p$, whence one of its sides must be a multiple of $p$. Moreover, the dimensions of this rectangle differ from the dimensions of the scaled-up rectangle by less than $1$. It follows that R has a side that differs from an integer by less than $1/p$ .

I couldn't figure out why it is necessary to have the condition that $p$ be prime.

• What is "lip of an integer"? – Hagen von Eitzen Dec 31 '14 at 16:05
• It was supposed to be $1/p$. I didn't proofread the OCR very well. – picakhu Dec 31 '14 at 19:12
• As an aside, can I just say that this question is a great one to really get people thinking and applying the knowledge they may have from sporadic parts of mathematics without knowing whether it will work or not. It's a question that you can play with and probably succeed in answering with enough effort. – Dan Rust Jan 1 '15 at 4:59
• What is meant by $([x],[y])$? – Erel Segal-Halevi Jun 3 '16 at 11:30

## 1 Answer

Therefore, the area of the large integer-sided rectangle is a multiple of $p$, whence one of its sides must be a multiple of $p$.

If $p$ were composite, this conclusion would fail.