Problem # 4

In multiplication tables, the last row is always a reverse of the first row.

Since N - 1 is always a coprime with N, then according to Problem #5, the last row must be a permutation of the first one. It's a very specific permutation. The number a_m in column m staisfies a_m = m·(N - 1) (mod N). But we have m·(N - 1) = -m = N - m (mod N) which exactly means that the last row is the reverse of the first.

Problem # 5

In multiplication tables modulo N, rows corresponding to numbers coprime with N contain permutations of the first row.

Let m be coprime to N. Let a and b be two different remainders of division by N. Then ma = mb (mod N) would imply m(a - b) = 0 (mod N) which, in turn, leads to (a - b) = 0 (mod N). Assuming b < a, we have a positive number less than N divisible by N. Contradiction. Hence a = b.

Problem # 6

For prime (N + 1), multiplication tables offer multiple and simultaneous solutions to the rook problem: on an N×N board position N rooks so that none may capture another. To solve, select a digit, replace all its occurrences with a rook, remove all other digits.

All remainders of division by a prime N + 1 are naturally coprime to N + 1. By Problem # 5, all rows and, analogously, all columns are permutations of the first row. That means that no number may appear twice in a column, nor in a row.

Problem # 7

Under the same conditions, 1 always appears in the upper left and lower right corners and nowhere else on the main diagonal.

We claim that the equation [a]_p² = 1, where p is prime has exactly two solutions [a] = 1 and [a] = p - 1. This follows from a known formula: a² - 1 = (a - 1)(a + 1) and the fact that all remainders of division by prime are coprime to it.

This fact is used to prove the Wilson's Theorem.

Problem # 12

If the table has an odd number of rows, then every remainder occurs on the main diagonal.

Let n be the modulus and an odd integer. Every remainder appears exactly once in each row of the addition table and so appears exactly n times. Since the table is symmetric about the main diagonal, each remainder appears as many times above the diagonal as below it; hence it appears an even number of times off the diagonal. Since the remainder appears the odd number n times altogether, it must appear on the main diagonal. Thus every remainder appears on the main diagonal, and so appears exactly once there.

Of course, as a problem in group theory, this problem is almost trivial. In a finite group of odd order, every element has odd order. So, if x is an element in such a group, then x^d = 1, the identity of the group, with d odd. Thus (x^{(d + 1)/2})² = x^{d + 1} = x, and so x is the square of an element of the group. This means that x appears in the main diagonal of the multiplication table of the group.

• 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
• Pick's Theorem
  • Pick's Theorem, A Proof
  • Farey Series
  • Pick's Theorem Applies to the Farey Series
  • Stern-Brocot Tree
• Fermat's Little Theorem
• Wilson's Theorem
• Euler's Function
• Divisibility Criteria
  • Further examles of divisibility criteria
• Examples
• Equivalence relations
• A real life story

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

Copyright © 1996-2018 Alexander Bogomolny