Inquiries-Week 9: Mod Multiplication

Thanks to Sam Graf for introducing me to this and suggesting some toys.

Introduction

Multiplication tables can be fun. Line up your numbers, multiply, and find patterns. Like with 5x5, we can fill it out and highlight symmetry, divisibility, squares, and so much more. In this inquiry, we're going to play with a different version of these tables.

Starting with Six

Take that 5x5 multiplication table and divide each number by 6, and write down the remainder. Another way to say this is mod 6.

What do you notice?

What patterns emerge in the table?

What numbers produce zeros?

What numbers don't produce zeros?

Make a table for the numbers that don't produce zeros, and apply mod 6 as before. This is called a Cayley table

For each number in the table, look at its powers mod 6 and note any observations:

Here is 5:

Activity

Now, let's take what we did with six and repeat it with other numbers. Let's call each number we pick m.

For each m:

• Make a table that goes from 0 to (m-1)
  • Note that zero was added in for completeness, but not required.
• Then a Cayley table of the numbers that don't generate zeros
• Then look at the powers.

Here is a tool (full page on desktop is best). It is too big to embed here, so save it and read on.

Here is six using that tool:

Here is nine. The size or number of rows in the Cayley table is Euler's totient. For nine it is six, written as φ(9)=6.

For different values of m

• Which numbers make you stop and look?
• Which ones feel more structured?
• Which ones are alike? different?
• Which numbers don't change when you hide zeros?
• Which numbers lose a lot of numbers when you hide zeros?
• How many different numbers are there for each row or column in the Cayley table?

Conjecture

Form conjectures about the tables.

• Do certain numbers result in certain patterns? certain Cayley tables?
• What is the maximum number of different values a row can have in the Cayley table?
• What numbers in the Cayley table produce all of the numbers in the table with their powers mod m?
• Are there certain numbers that you can always expect to see in a Cayley table?

Activity Structure

This is a 60–90 minute activity exploring the multiplicative structure of integers mod m.

Exploration Phase 1 (10–15 minutes)

Building the first tables

Have learners build the mod 6 multiplication table by hand. The hand-work matters — patterns surface faster when learners feel the symmetry and notice the zeros or lack thereof.

• Ask: "Which rows or columns have zeros? Which don't?"
• Once they strike out the rows/columns with zeros, the leftover 2×2 Cayley table for {1, 5} is small enough to stare at and ask, "What is this thing?"
• Look at the powers - does 1,5,1,5,1,5 continue to repeat? Why?

Exploration Phase 2 (15–20 minutes)

Comparing several values of m

Some useful values to start with:

• A prime: m = 5 or 7
• A prime power: m = 8 or 9
• A product of distinct primes: m = 10 or 15

Here is the tool — full page on desktop is best.

Groups or learners can take values and then trade.

Conjecture Formation (10–15 minutes)

Give time to write down observations before discussing. Offer examples if learners stall.

Example Conjectures:

Example: "When m is prime, no rows or columns get hidden after the zero row and column."

Example: "The numbers left after hiding zeros are exactly the numbers that share no factors with m."

Example: "Every row of the Cayley table has the same set of numbers, just rearranged."

Example: "Sometimes one number's powers generate all the numbers in the table."

Example: "Every Cayley table has 1 and m-1."

Example: "Every Cayley table is a Latin Square."

Supporting Questions:

• "What do the m values with no zeros have in common?"
• "How could you predict how many numbers survive hiding zeros, without building the table?"
• "Why does every row in the Cayley table seem to have each number exactly once?"
• "For which m does some number's powers produce all the others?"

Discussion and Discovery (15–20 minutes)

• Share conjectures across groups.
• Introduce terminology as it becomes useful:
  • The surviving numbers are called units mod m.
  • The count of units is Euler's totient, φ(m).
  • A Cayley table whose row/column entries are a permutation of the same set is a Latin square.

Going deeper (optional)

The content below is what you might find in a textbook, and possibly too heavy for light inquiry.

Do the powers always cycle? 

• Pick a number from the Cayley table — call it n — and list n, n², n³, … mod m.
• There are only finitely many remainders possible, so the sequence eventually repeats.
• For any number in the Cayley table, it always cycles back to 1.
• The smallest power that hits 1 is called the order of n.

How long is the cycle? 

• Compare cycle lengths across numbers in the Cayley table.
• They always divide φ(m) — the number of rows in the Cayley table.
  • This is Lagrange's theorem.

When does one number's powers produce all the others? 

• When the cycle length equals φ(m), that single number's powers fill the entire Cayley table.
• It's called a generator or primitive root.
• These exist exactly when m = 1, 2, 4, pᵏ, or 2pᵏ for odd prime p — so mod 8, 12, 15 have none.
• A group where this happens is called a cyclic group.

Optional: Proof scaffolding

Powers of a Cayley table number (unit) cycle back to 1

• Consider mod 7, its Cayley table, and powers of 2 mod 7:

• The list goes 2, 4, 1, 2, 4, 1, … It cycles back to 1 every 3 steps.

Is this true for all numbers in the Cayley table?

1. There are only finitely many possible remainders.
   1. Mod 7, the possible remainders are 0, 1, 2, 3, 4, 5, 6 — seven values total.
   2. Every power 2¹, 2², 2³, … has to land on one of these seven.
2. Eventually, two powers share the same remainder.
   1. This is the pigeonhole principle.
   2. Ex: 2 holes and 3 pigeons means two pigeons have to share a hole.

3. Every Cayley table number n has an inverse — a number that, when multiplied by n and then taken mod m, equals 1.
   1. Example: 2's inverse mod 7 is 4, since (2 × 4)(mod 7) ≡ 1.
   2. Note that by its construction, there are no zeros in the row. 
   3. All numbers in a row are different. Why?
      1. If two entries matched — say (n × a)(mod m) ≡ (n × b)(mod m) with a > b — then (n × (a − b))(mod m) ≡ 0.
      2. But a − b is between 1 and m − 1, and the row has no zeros there.
   4. So n's row has m − 1 different, nonzero values filling m − 1 spots. They must cover every nonzero residue from 1 to m − 1 — including 1.
   5. The number b with n × b ≡ 1 (mod m) is n's inverse.
4. For any number n in the Cayley table mod m:
   1. The list n, n², n³, … has only m possible values, so two must repeat: nⁱ ≡ nʲ for some i < j.
   2. Multiplying both sides by n's inverse i times cancels the left down to 1.
   3. What's left: 1 ≡ n^(j − i) (mod m).

Note: Try 2 mod 6, where 2 isn't in the Cayley table. The powers go 2, 4, 2, 4, … The cycle never reaches 1, because 2 has no inverse mod 6. There's nothing to cancel with.

Tools and Supplies

• Grid paper for hand-built tables.
• A spreadsheet tool works well for this
• Calculator or spreadsheet for larger m.
• Units mod m tool (full page on desktop).
• Colored pencils or highlighters for marking symmetry, zeros, and cycles.

Vocabulary

• Modulo / Mod: The remainder when one number is divided by another. Example: 4 mod 3 = 1.
• Unit (mod m): A number with a multiplicative inverse mod m; equivalently, a number coprime to m.
• Cayley table: A table showing the result of a binary operation on every pair of elements in a set.
• Latin square: A square table where every row and column contains each symbol exactly once.
• Euler's totient (φ(m)): The count of integers from 1 to m that are coprime to m.
• Order of an element: The smallest positive k such that aᵏ ≡ 1 (mod m).
• Generator / Primitive root: A unit whose powers produce every unit mod m.
• Cyclic group: A group generated by a single element.
• Group: A set with an operation that has closure, associativity, identity, and invertibility.
• Lagrange's theorem: The order of any element divides the size of the group.
• Conjecture: A statement believed true but not yet proven.
• Counterexample: A specific instance that disproves a conjecture.
• Monoid: A system that has closure, associativity, and identity.
• Ring: A set with two operations (like + and ×), where + forms a commutative group, × forms a monoid, and × distributes over +. So,  a × (b + c) = (a × b) + (a × c).

Extensions and What Ifs and Resources

• Play with the concept in more dimensions: Toy for 3D is here.
• William Stein, Elementary Number Theory: Primes, Congruences, and Secrets
• Compute φ(m) for m up to 30 and look for patterns in the Cayley table sizes.
• Addition vs. multiplication - what does addition look like mod m?
• Public-key cryptography applications
• Carmichael function λ(m)
• Gauss defined primitive roots in Disquisitiones Arithmeticae (1801).
• Chords on a circle.
  • Put n evenly spaced points on a circle and connect them with rules.
  • Skip-k chords visit every point exactly when k is a unit mod n.
    • Multiplier-k chord rules send each point to a different image exactly when k is a unit mod n.
  • Both rules live in the same ring (ℤ/nℤ, +, ×) — step rules use the additive side, multiplier rules use the multiplicative side.
  • See Beautiful Chords.