Paper 4, Section I, E

Numbers and Sets
Part IA, 2014

Use Euclid's algorithm to determine dd, the greatest common divisor of 203 and 147 , and to express it in the form 203x+147y203 x+147 y for integers x,yx, y. Hence find all solutions in integers x,yx, y of the equation 203x+147y=d203 x+147 y=d.

How many integers nn are there with 1n20141 \leqslant n \leqslant 2014 and 21n25(mod29)?21 n \equiv 25(\bmod 29) ?