Advanced book on Mathematics Olympiad

274 5 Number Theory

And now the problems.

797.Given a piece of paper, we can cut it into 8 or 12 pieces. Any of these pieces can be
cut into 8 or 12, and so on. Show that we can obtain any number of pieces greater
than 60. Can we obtain exactly 60 pieces?

798.Letaandbbe positive integers. For a nonnegative integernlets(n)be the number
of nonnegative integer solutions to the equationax+by =n. Prove that the
generating function of the sequence(s(n))nis

f(x)=

1

( 1 −xa)( 1 −xb)

799.Letn>6 be a positive integer. Prove that the equation

x+y=n

admits a solution withxandycoprime positive integers both greater than 1.

800.Prove that thed-dimensional cube can be dissected intond-dimensional cubes for
all sufficiently large values ofn.

5.3.2 The Equation of Pythagoras................................

The Diophantine equation

x^2 +y^2 =z^2 ,

has as solutions triples of positive integers that are the side lengths of a right triangle,
whence the name. Let us solve it.
Ifxandzhave a common factor, this factor dividesyas well. Let us assume first
thatxandzare coprime. We can also assume thatxandzhave the same parity (both are
odd); otherwise, exchangexandy.
In this situation, write the equation as

y^2 =(z+x)(z−x).

The factorsz+xandz−xare both divisible by 2. Moreover, 2 is their greatest common
divisor, since it is the greatest common divisor of their sum 2zand their difference 2x.
We deduce thatyis even, and there exist coprime integersuandvsuch thaty= 2 uv,
z+x= 2 u^2 andz−x= 2 v^2. We obtainx=u^2 −v^2 andz=u^2 +v^2. Incorporating the
common factor ofx,y, andz, we find that the solutions to the equation are parametrized
by triples of integers(u, v, k)asx =k(u^2 −v^2 ),y= 2 kuv, andz=k(u^2 +v^2 )or
x = 2 kuv,y =k(u^2 −v^2 ), andz=k(u^2 +v^2 ). The positive solutions are called
Pythagorean triples.