01a-integers-and-division.ipynb

Kernel: Python 3

# This notebook has two versions:
#   Python (this file) -- runs in browser via JupyterLite, no install needed
#   SageMath (../sage/) -- richer algebra system, needs local install or Codespaces
#
# Both versions cover the same material. Choose whichever works for you.

import sys, os
sys.path.insert(0, os.path.join('..', '..', '..', 'shared'))

from cryptolab import Mod

Integers and Division

Module 01a | Modular Arithmetic and Groups

The division algorithm hides a powerful structure that underlies all of modern cryptography.

Question: You need to send the number 42 to your friend, but your channel can only transmit values 0 through 6. How do you encode it? And how does your friend recover the original?

By the end of this notebook, you'll see that the answer, remainders, is the seed of an entire number system.

Objectives

By the end of this notebook you will be able to:

1. State the division algorithm and explain what makes it useful

2. Use divmod() and Mod() in Python for exact modular arithmetic

3. Recognize remainder patterns as the foundation of modular arithmetic

Prerequisites

This is the first notebook in Module 01. You need:

• Basic familiarity with Python syntax

• A working SageMath installation (or access to CoCalc/SageMathCell)

No prior knowledge of abstract algebra is assumed.

The Division Algorithm

Every integer division produces a quotient and remainder: $$a = q \cdot b + r, \quad 0 \le r < b$$

This isn't just arithmetic, it's a theorem: for any integers $a$ and $b > 0$, there exist unique $q$ and $r$. Let's see it in action.

# The division algorithm in action
a, b = 37, 7
q, r = divmod(a, b)
print(f'{a} = {q} * {b} + {r}')
print(f'Quotient: {q}, Remainder: {r}')

What if we only cared about the remainder? Watch what happens when we compute remainders of different numbers mod 7:

# These numbers are all "the same" mod 7
for a in [2, 9, 16, 23, 30, 37]:
    q, r = divmod(a, 7)
    print(f'{a} mod 7 = {r}')
print('\nAll give remainder 2. In modular arithmetic, these are "equivalent."')

Remainder Patterns

Checkpoint: Before running the next cell, predict: if you compute k mod 7 for k = 0, 1, 2, ..., 20, how many distinct values will you see?

# Remainder patterns: what happens as k grows?
for k in range(21):
    print(f'{k:2d} mod 7 = {k % 7}', end='    ')
    if (k + 1) % 7 == 0:
        print()  # newline every 7 values

The remainders cycle through {0, 1, 2, 3, 4, 5, 6}, exactly 7 distinct values, repeating forever. This isn't a coincidence: the division algorithm guarantees $0 \le r < 7$, so there are exactly 7 possible remainders. These 7 "bins" are the building blocks of $\mathbb{Z}/7\mathbb{Z}$.

Mod() from cryptolab: More Than Just %

Python's % operator returns an ordinary integer. Mod() from cryptolab creates something richer, an element that lives in the world of remainders.

# Python % gives an integer
print(type(37 % 7), ':', 37 % 7)

# SageMath Mod() gives a ring element
x = Mod(37, 7)
print(type(x), ':', x)

# The ring element "knows" its modulus
print(f'Parent ring: {x.parent()}')

# Arithmetic stays inside the remainder world
a = Mod(37, 7)  # = 2 in Z/7Z
b = Mod(51, 7)  # = 2 in Z/7Z (since 51 = 7*7 + 2)
print(f'a = {a}, b = {b}')
print(f'a + b = {a + b}')  # 2 + 2 = 4 in Z/7Z
print(f'a * b = {a * b}')  # 2 * 2 = 4 in Z/7Z
print(f'a + Mod(5, 7) = {a + Mod(5, 7)}')  # 2 + 5 = 0 in Z/7Z (wraps!)

Common mistake: "Mod(37, 7) is just a fancy way to write 37 % 7 = 2." No! Mod(37, 7) creates a number that lives in $\mathbb{Z}/7\mathbb{Z}$. When you add two such numbers, the result automatically stays in $\mathbb{Z}/7\mathbb{Z}$. This distinction, between "computing a remainder" and "working inside a number system", becomes critical in the next notebook.

Exercises

Exercise 1 (Worked)

Compute divmod(1234, 17). Verify that $q \times 17 + r = 1234$. Then create Mod(1234, 17) and confirm the remainder matches.

# Exercise 1: Worked solution
q, r = divmod(1234, 17)
print(f'1234 = {q} * 17 + {r}')
print(f'Verification: {q * 17 + r} == 1234? {q * 17 + r == 1234}')
print(f'Mod(1234, 17) = {Mod(1234, 17)}')
print(f'Remainder matches? {r == Mod(1234, 17)}')

Exercise 2 (Guided)

Build a remainder table: for each modulus $n \in \{5, 6, 7\}$, print k mod n for $k = 0, 1, \ldots, 20$.

Question: For which $n$ does every remainder from 0 to $n-1$ appear equally often among $k = 0, \ldots, 20$? Why doesn't it always work out evenly?

# Exercise 2: Fill in the print statement
for n in [5, 6, 7]:
    print(f'--- mod {n} ---')
    remainders = [k % n for k in range(21)]
    print(remainders)
    # TODO: count how many times each remainder appears
    # Hint: use remainders.count(r) for each r in range(n)

Exercise 3 (Independent)

Without running code first, predict:

• If $a \bmod 7 = 3$ and $b \bmod 7 = 5$, what is $(a + b) \bmod 7$?

• What is $(a \times b) \bmod 7$?

Verify with SageMath. Then test: does this "compute the remainders separately, then combine" trick work for any modulus? Try $n = 12$ with some examples.

# Exercise 3: Your code here

Summary

Concept	Key idea
Division algorithm	$a = qb + r$ with $0 \le r < b$, and the pair $(q, r)$ is unique
Remainder cycling	Remainders mod $n$ cycle through exactly $n$ values: $\{0, 1, \ldots, n-1\}$
Mod(a, n)	Creates an element that lives in $\mathbb{Z}/n\mathbb{Z}$, not just a leftover integer
Wrap-around arithmetic	Arithmetic on Mod elements automatically stays inside the remainder system

The division algorithm looks like basic arithmetic, but the "remainder world" it creates is the foundation of everything that follows.

Crypto teaser: Every number in RSA lives in this remainder world. The modulus $n$ is the product of two secret primes, and the security of RSA depends on the difficulty of factoring $n$ back into those primes.

Next: Modular Arithmetic, we turn remainders into a complete number system.