Advanced book on Mathematics Olympiad

258 5 Number Theory

747.Prove that the expression

gcd(m, n)

n

(

n

m

)

is an integer for all pairs of integersn≥m≥1.

748.Letkandnbe integers with 0≤k≤n^2 /4. Assume thatkhas no prime divisor

greater thann. Prove thatn!is divisible byk.

5.2.3 Modular Arithmetic.......................................

A positive integernpartitions the set of integersZintonequivalence classes by the
remainders obtained on dividing byn. The remainders are called residues modulon.
We denote byZn={ 0 , 1 ,...,n− 1 }the set of equivalence classes, indexed by their
residues. Two numbersaandbare said to be congruent modulon, which is written
a≡b(modn), if they give the same remainder when divided byn, that is, ifa−bis
divisible byn.
The ring structure ofZinduces a ring structure onZn. The latter ring is more
interesting, since it has zero divisors whenevernis composite, and it has other invertible
elements besides±1. To make this precise, for any divisordofnthe product ofdand
n/dis zero. On the other hand, the fundamental theorem of arithmetic, which states
that whenevermandnare coprime there exist integersaandbsuch thatam−bn=1,
implies that any number coprime tonhas a multiplicative inverse modulon. For a prime
p, every nonzero element inZphas an inverse modulop. This means thatZpis a field.
We also point out that the set of invertible elements inZnis closed under multiplication;
it is an Abelian group.
A well-known property that will be used in some of the problems below is that modulo
9, a number is congruent to the sum of its digits. This is because the difference of the
number and the sum of its digits is equal to 9 times the tens digit plus 99 times the
hundreds digit plus 999 times the thousands digit, and so on. Here is an elementary
application of this fact.

Example.The number 2^29 has 9 distinct digits. Without using a calculator, tell which

digit is missing.

Solution.As we have just observed, a number is congruent to the sum of its digits modulo

9. Note that 0+ 1 + 2 +···+ 9 =45, which is divisible by 9. On the other hand,

229 ≡ 22 (− 1 )^9 ≡− 4 (mod 9).

So 2^29 is off by 4 from a multiple of 9. The missing digit is 4. 

We continue with a property of the harmonic series discovered by C. Pinzka.