114 6. Integers, Divisors, and Primes
We can write this as
(x−1)(x−2)≡0 (mod 53).One of the factors on the left-hand side must be congruent to 0 modulo 53,
whence eitherx≡1 (mod 53) orx≡2 (mod 53).
Here we found a way to write the left-hand side as a product just by
looking at it. What happens if we have an equation with larger numbers,
sayx^2 + 134517x+ 105536≡0 (mod 234527)? We doubt that anybody can
guess a decomposition. In this case, we can try to follow the high-school
procedure for solving quadratic equations. This works, but one step of it
is quite difficult: taking square roots. This can be done efficiently, but the
algorithm is too complicated to be included here.
6.8.5Solve the congruence system2 x+3y≡ 1 (mod 11),
x+4y≡ 4 (mod 11).6.8.6Solve the “congruence equations”(a) x^2 − 2 x≡0 (mod 11), (b) x^2 ≡4 (mod 23).6.9 Number Theory and Combinatorics..............
Many of the combinatorial tools that we have introduced are very useful in
number theory as well. Induction is used all over the place. We show some
elegant arguments based on thePigeonhole Principleand oninclusion–
exclusion.
We are givennnatural numbers:a 1 ,a 2 ,...,an. Show that we
can choose a (nonempty) subset of these numbers whose sum is
divisible byn.(It is possible that this subset contains allnnumbers.)
Solution. Consider the followingnnumbers:b 1 =a 1 ,
b 2 =a 1 +a 2 ,
b 3 =a 1 +a 2 +a 3 ,
..
.
bn=a 1 +a 2 +a 3 +···+an.