I know that 7 * 5^2 + 9 * 3^2 = 16^2, which suggests that 7 5x5 squares plus 9 3x3 squares can possibly tile a 16x16 square. Is there a relatively simple way to figure out if either: a) no, they won't, or b) yes, and here's how? Ideally, I'd like to learn the process, not just the answer, as I will probably have other combinations to consider.

3x3 and 5x5 squares tile all m x n rectangles such that m and n are sufficiently large, and satisfy * either 3 divides m or 5 divides n , and * either 5 divides m or 3 divides n . (In this particular instance, "sufficiently large" means "at least 8".) See Example 3.9 from my paper "Asymptotically Optimal Box Packing Theorems" in The Electronic Journal of Combinatorics: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v15i1r78 A portion of that paper is devoted to expounding on results of the late F.W. Barnes, which do not seem to be as well-known, or as well- understood as they should be. Based on Barnes' work, this type of question is reduced to a simple calculation. It is too much to describe all the details behind it, but hopefully this summary will pique your interest: The set of all m x n rectangles that can be tiled by 3x3 squares is the set of (m, n) satisfying * (either) 3 divides m (or 0 divides n ), and * (either 0 divides m or) 3 divides n . The parenthesized conditions evaluate to "false", but they are there to put the conditions in the proper form. We'll encode these conditions by calling them "restrictions" [3, 0] and [0, 3] . Likewise, the set of all m x n rectangles that can be tiled by 5x5 squares is the set of all (m, n) satisfying the set of restrictions {[5, 0], [0, 5]} . To get the set of all m x n rectangles that can be tiled by 3x3 squares and 5x5 squares together, we wedge together the two sets of restrictions: {[3, 0], [0, 3]} v {[5, 0], [0, 5]} = {[3, 0] v [5, 0], [3, 0] v [0, 5], [0, 3] v [5, 0], [0, 3] v [0, 5]} = {[1, 0], [3, 5], [5, 3], [0, 1]} where the wedge takes the component-wise GCD of the restrictions. Any "restriction" with a 1 evaluates to "true", so can be discarded. Thus we are left with the two restrictions [3, 5] and [5, 3] that I gave above. Satisfying these restrictions is not sufficient to be tileable, but it is sufficient if m and n are large enough (hence the "asymptotically" in my title). For the case where your tiles are two rectangles (using translations only) you may be interested to see the "two bricks theorem" in Packing Boxes with Bricks by Richard J. Bower and T. S. Michael, Math Magazine, (February 2006) v. 79, no. 1, pp. 14-30. ( http://www.jstor.org/stable/27642898 ) Michael Reid