Modular Arithmetic, examples

Prove that 11¹⁰ - 1 is divisible by 100.

Consider arithmetic modulo 100: 11² = 11·11 = 21 (mod 100), 11³ = 21·11 = 31 (mod 100), 11⁴ = 31·11 = 41 (mod 100), ..., 11¹⁰ = 91·11 = 01 (mod 100).

(Of course one can also use 11¹⁰ - 1 = (11 - 1)(11⁹ + 11⁸ + ... + 1).)

Is 2222⁵⁵⁵⁵ + 5555²²²² divisible by 7?

2222⁵⁵⁵⁵ + 5555²²²² = 3⁵⁵⁵⁵ + 4²²²² (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 (mod 7), 3³ = 6 (mod 7), 3⁴ = 4 (mod 7), 3⁵ = 5 (mod 7), 3⁶ = 1 (mod 7), 3⁷ = 3 (mod 7), and so on: 3,2,6,4,5,1,3,... Note that 5555 = 5 (mod 6). Therefore, 2222⁵⁵⁵⁵ = 3⁵ (mod 7) = 5(mod 7).

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

Adding up 5 + 2 gives a number divisible by 7. So is 2222⁵⁵⁵⁵ + 5555²²²².

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

3^6·710 - 1 is divisible by 7¹¹.

This is just a particular case of the Euler's Theorem. Indeed, (7¹¹) = 6·7¹⁰.

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² + y² = 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)² = 0 (mod 4) and (2x + 1)² = 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 A = p^q + q^p - 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.

• Modular Arithmetic
  • Differences and Similarities
  • Solutions to some problems
• Chinese Remainder Theorem
• Euclid's Algorithm
  • Euclid's Game
  • Binary Euclid's Algorithm
  • gcd and the Fundamental Theorem of Arithmetic
  • Extension of Euclid's Algorithm
  • Stern-Brocot Tree
    • Fine features
    • Binary Encoding
    • Binary Encoding, a Second Interpretation
    • Continued Fractions on the Stern-Brocot Tree
    • Fractions on a Binary Tree
  • Farey series
    • Farey series, a story
• Fermat's Little Theorem
• Wilson's Theorem
• Euler's Function
• Divisibility Criteria
  • Further examles of divisibility criteria
• Examples
• Equivalence relations
• A real life story

Copyright © 1996-2008 Alexander Bogomolny