# Modular Arithmetic, examples

Prove that 1110 - 1 is divisible by 100.

Consider arithmetic modulo 100: 112 = 11·11 = 21 (mod 100), 113 = 21·11 = 31 (mod 100), 114 = 31·11 = 41 (mod 100), ..., 1110 = 91·11 = 01 (mod 100).

(Of course one can also use 1110 - 1 = (11 - 1)(119 + 118 + ... + 1).)

Is 22225555 + 55552222 divisible by 7?

22225555 + 55552222 = 35555 + 42222 (mod 7). There are only 7 residue classes modulo 7. Therefore, the series of powers of a given number (modulo 7) is bound to be cyclic (of period 6). For example, 32 = 2 (mod 7), 33 = 6 (mod 7), 34 = 4 (mod 7), 35 = 5 (mod 7), 36 = 1 (mod 7), 37 = 3 (mod 7), and so on: 3, 2, 6, 4, 5, 1, 3, ... Note that 5555 = 5 (mod 6). Therefore, 22225555 = 35 (mod 7) = 5(mod 7).

Similarly, 55552222 = 42222 (mod 7). Powers of 4 modulo 7 form a cycle of period 3: 4,2,1,4,... Hence, 42222 (mod 7) = 42222 ( mod 3)(mod 7) = 42 (mod 7) = 2 (mod 7).

Adding up 5 + 2 gives a number divisible by 7. So is 22225555 + 55552222.

For any n, (2n)2 = 0 (mod 4) and (2n + 1)2 = 1 (mod 4). Therefore, for no integer m, may m2 + 2 be a square of another integer; for modulo 4 m2 + 2 is either 2 or 3. By the same token, none of the following numbers may possibly be a complete square: m4 + 2002, m10 + 762, (17n + 13)1212 + 50, etc.

36·710 - 1 is divisible by 711.

This is just a particular case of the Euler's Theorem. Indeed, φ(711) = 6·710.

No number whose digits add up to 15 may be a complete square.

We know that n = s+(n) (mod 9), where s+(n) has been defined as the sum of digits of n. A quick glance at the main diagonal of the multiplication modulo 9 table shows that complete squares may only have s+ equal to one of 0,1,4, or 7. s+(15), on the other hand, is 6.

The same is of course true for s+ equal 222, 1806, 1000000000001, etc.

Solve Diophantine equation: x2 + y2 = 4z - 1.

The equation being Diophantine (after the famous Greek Mathematicican Diophantos of Alexandria) means that we are looking for integer solutions.

Well, there are none. Indeed, from (2x)2 = 0 (mod 4) and (2x + 1)2 = 1 (mod 4) we conclude that any integer square may only be 0 or 1 modulo 4. The sum of two such intergers may only be 0, 1, or 2. On the other hand, 4z - 1 modulo 4 is -1 (or, which is the same, 3).

Given are 7 pieces of paper. Select a random number and cut each into seven pieces. Prove that whatever manner you continue this process, you will never get 1997 individual pieces.

Indeed, every time you cut a piece into 7 parts, the total number of pieces grows by 6. Therefore, the total number is invariant modulo 6. However, 7 = 1 whereas 1997 = 2.

Let p and q be prime. Show that pq + qp = p + q (mod pq).

We have to show that A = pq + qp - p - q = 0 (mod pq). This, in turn, will follow from A = 0 (mod p) and A = 0 (mod q). Both are direct consequences of the Fermat's Thereom.