# Modular Arithmetic, examples

Prove that 11^{10} - 1 is divisible by 100.

Consider arithmetic modulo 100: 11^{2} = 11·11 = 21 (mod 100), 11^{3} = 21·11 = 31 (mod 100),
11^{4} = 31·11 = 41 (mod 100), ..., 11^{10} = 91·11 = 01 (mod 100).

(Of course one can also use 11^{10} - 1 = (11 - 1)(11^{9} + 11^{8} + ... + 1).)

Is 2222^{5555} + 5555^{2222} divisible by 7?

2222^{5555} + 5555^{2222} = 3^{5555} + 4^{2222} (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, 3^{2} = 2 (mod 7),
3^{3} = 6 (mod 7), 3^{4} = 4 (mod 7), 3^{5} = 5 (mod 7), 3^{6} = 1 (mod 7),
3^{7} = 3 (mod 7), and so on: 3, 2, 6, 4, 5, 1, 3, ... Note that 5555 = 5 (mod 6). Therefore, 2222^{5555} = 3^{5} (mod 7) = 5(mod 7).

Similarly, 5555^{2222} = 4^{2222} (mod 7). Powers of 4 modulo 7 form a cycle of period 3: 4,2,1,4,...
Hence, 4^{2222} (mod 7) = 4^{2222 ( mod 3)}(mod 7) = 4^{2} (mod 7) = 2 (mod 7).

Adding up 5 + 2 gives a number divisible by 7. So is ^{5555} + 5555^{2222}.

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

3^{6·710} - 1 is divisible by 7^{11}.

This is just a particular case of the Euler's Theorem. Indeed, φ(7^{11}) = 6·7^{10}.

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: x^{2} + y^{2} = 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 p^{q} + q^{p} = p + q (mod pq).

We have to show that ^{q} + q^{p} - p - q = 0 (mod pq).

- Modular Arithmetic
- Chinese Remainder Theorem
- Euclid's Algorithm
- Fermat's Little Theorem
- Wilson's Theorem
- Euler's Function
- Divisibility Criteria
- Examples
- Equivalence relations
- A real life story

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2017 Alexander Bogomolny

62685651 |