[Python] 借助图形化界面探索模m运算的规律

背景

模运算这件事，看起来简单，但背后藏着不少有趣的规律。如果能把这些规律用图形化的方式展示出来，理解起来就会直观得多。受《A Friendly Introduction to Number Theory》第9章（Congruences, Powers, and Fermat’s Little Theorem）的启发，这里借助图形化界面来探索模 $m$ 运算的规律。本文只关心 $m$ 是质数的情况，并提供一套Python代码，用来观察 $a^n \pmod{p}$ 的分布规律，目前这套代码支持20以内的所有质数。

正文

当然，光看公式和定理，有时候会觉得隔着一层纱。所以，打算用Python写一个图形化工具，把模运算的结果直接“画”出来，这样看起来就清楚多了。工具的开发思路是：用网格来展示所有可能的 $a$ 和 $n$ 组合，然后在每个格子里显示对应的 $a^n \bmod{p}$ 计算结果。和常见的纯数学推导不同，这种方式能直观地看到一些隐藏的模式，比如对称性、周期性，甚至是费马小定理的身影。

代码

借助豆包和trae，写了一个Python脚本，代码如下。这份代码在之前的文章（[Python] 费马小定理）中也分享过，不过这次做了一些调整和优化。

import pygame
# ===================== 1. 初始化配置 =====================
pygame.init()
# 可选的质数 p 列表
PRIMES = [2, 3, 5, 7, 11, 13, 17, 19]
# 初始选中的 p（默认 None，未选择）
selected_p = None
# 基础窗口设置（自适应大小，最小600x600）
MIN_WIDTH, MIN_HEIGHT = 650, 650
screen = pygame.display.set_mode((MIN_WIDTH, MIN_HEIGHT), pygame.RESIZABLE)
pygame.display.set_caption("a^n mod p visualization tool")
# 颜色配置
WHITE = (255, 255, 255)
BLACK = (0, 0, 0)
GRAY = (200, 200, 200)
BLUE = (60, 130, 220)    # 按钮颜色
LIGHT_BLUE = (140, 190, 240)
RED = (220, 60, 60)     # 标题颜色
GREEN = (50, 180, 50)   # 结果文字颜色
DARK_BLUE = (30, 80, 180) # a/n标签颜色
def get_fonts(cell_size):
    """根据单元格大小动态调整字体"""
    base_size = max(10, int(cell_size * 0.55))
    font_grid = pygame.font.SysFont("Arial", base_size)
    font_an = pygame.font.SysFont("Arial", base_size)
    return font_grid, font_an
font_btn = pygame.font.SysFont("Arial", 24)
font_label = pygame.font.SysFont("Arial", 26)
def calc_pow(a, n, p):
    """calc a**n mod p"""
    if n == 0:
        return 1
    temp = calc_pow(a, n // 2, p)
    if n % 2 == 0:
        return (temp * temp) % p
    return (temp * temp * a) % p
# ===================== 2. 按钮绘制与点击判断 =====================
def draw_buttons():
    """绘制顶部的p选择按钮"""
    btn_width, btn_height = 60, 40
    start_x = 20
    start_y = 20
    spacing = 10
    for i, p in enumerate(PRIMES):
        btn_x = start_x + i * (btn_width + spacing)
        btn_rect = pygame.Rect(btn_x, start_y, btn_width, btn_height)
        # 选中的按钮变色
        color = LIGHT_BLUE if p == selected_p else BLUE
        pygame.draw.rect(screen, color, btn_rect, border_radius=5)
        # 按钮文字
        text = font_btn.render(f"p={p}", True, WHITE)
        text_rect = text.get_rect(center=btn_rect.center)
        screen.blit(text, text_rect)
def get_clicked_p(mouse_pos):
    """判断点击了哪个p按钮，返回对应的p值"""
    btn_width, btn_height = 60, 40
    start_x = 20
    start_y = 20
    spacing = 10
    for i, p in enumerate(PRIMES):
        btn_x = start_x + i * (btn_width + spacing)
        btn_rect = pygame.Rect(btn_x, start_y, btn_width, btn_height)
        if btn_rect.collidepoint(mouse_pos):
            return p
    return None
def resize_window(p):
    """根据选择的p自动调整窗口大小"""
    cell_size = min(70, (MIN_WIDTH - 120) // p)
    _, font_an = get_fonts(cell_size)
    max_num_str = str(p)
    max_label_width = font_an.size(max_num_str)[0]
    label_space = max_label_width + 10
    needed_width = cell_size * p + label_space + 60
    needed_height = 120 + cell_size * p + label_space + 60
    needed_width = max(needed_width, MIN_WIDTH)
    needed_height = max(needed_height, MIN_HEIGHT)
    return pygame.display.set_mode((needed_width, needed_height), pygame.RESIZABLE)
# ===================== 3. 网格绘制（显式标注a和n的值） =====================
def draw_grid(p):
    """绘制a-n网格，显式展示a、n和a^n mod p的值"""
    if p is None:
        tip = font_label.render("Please select p value", True, RED)
        screen.blit(tip, (screen.get_width()//2 - tip.get_width()//2, 100))
        return
    cell_size = min(70, (screen.get_width() - 120) // p)
    font_grid, font_an = get_fonts(cell_size)
    max_num_str = str(p)
    max_label_width = font_an.size(max_num_str)[0]
    label_space = max_label_width + 10
    total_grid_width = cell_size * p + label_space
    grid_start_x = (screen.get_width() - total_grid_width) // 2 + label_space
    grid_start_y = 120 + label_space
    grid_start_x = (screen.get_width() - total_grid_width) // 2 + label_space
    grid_start_y = 120 + label_space
    # -------- 1. 绘制坐标轴标题 --------
    n_title = font_label.render("n →", True, DARK_BLUE)
    n_title_x = grid_start_x + (cell_size * p) // 2
    n_title_y = 85
    screen.blit(n_title, (n_title_x - n_title.get_width()//2, n_title_y))
    a_title = font_label.render("a ↓", True, DARK_BLUE)
    a_title_x = (screen.get_width() - total_grid_width) // 2 - 25
    a_title_y = grid_start_y + (cell_size * p) // 2
    screen.blit(a_title, (a_title_x, a_title_y - a_title.get_height()//2))
    # -------- 2. 绘制顶部：显式展示所有 n 的值（横坐标） --------
    for i in range(p):
        n = i + 1
        x = grid_start_x + i * cell_size + cell_size//2
        y = grid_start_y - label_space//2
        n_text = font_an.render(str(n), True, DARK_BLUE)
        n_rect = n_text.get_rect(center=(x, y))
        screen.blit(n_text, n_rect)
    # -------- 3. 绘制左侧：显式展示所有 a 的值（纵坐标） --------
    for a in range(p):
        x = grid_start_x - label_space//2
        y = grid_start_y + a * cell_size + cell_size//2
        a_text = font_an.render(str(a), True, DARK_BLUE)
        a_rect = a_text.get_rect(center=(x, y))
        screen.blit(a_text, a_rect)
    # -------- 4. 绘制网格主体 + 计算结果 --------
    for i in range(p):
        n = i + 1
        for a in range(p):
            x = grid_start_x + i * cell_size
            y = grid_start_y + a * cell_size
            cell_rect = pygame.Rect(x, y, cell_size, cell_size)
            pygame.draw.rect(screen, BLACK, cell_rect, 1)
            val = calc_pow(a, n, p)
            val_text = font_grid.render(str(val), True, GREEN)
            val_rect = val_text.get_rect(center=cell_rect.center)
            screen.blit(val_text, val_rect)
# ===================== 4. 主循环 =====================
running = True
while running:
    screen.fill(WHITE)
    # 绘制按钮
    draw_buttons()
    # 绘制网格（含显式a/n标注）
    draw_grid(selected_p)
    # 事件处理
    for event in pygame.event.get():
        # 关闭窗口
        if event.type == pygame.QUIT:
            running = False
        # 鼠标点击事件
        if event.type == pygame.MOUSEBUTTONDOWN:
            mouse_pos = pygame.mouse.get_pos()
            # 获取点击的p值
            clicked_p = get_clicked_p(mouse_pos)
            if clicked_p is not None:
                selected_p = clicked_p
                screen = resize_window(selected_p)
    # 刷新界面
    pygame.display.flip()
pygame.quit()

将以上代码保存为 show_mod_pow.py，然后用命令 python3 show_mod_pow.py 就可以运行。启动后的效果如下：

选择不同的 $p$ 值，就能看到 $a^n \bmod{p}$ 的计算结果。以 $p=5$ 为例，效果如下：

探索

有了这个可视化工具，就可以开始“玩”了。以 $p=2,3,5,7$ 的情况为例，探索出了一些有趣的规律。为了方便查看，把 $p=2,3,5,7$ 的四张图合并到了一起。

规律一: $a^2$ 分布对称

第一个规律是：$a^2$ 的分布是对称的。具体来说，对满足 $0 < a < p$ 的 $a$ 而言，$a^2 \equiv (p-a)^2 \pmod{p}$。

这个规律不难证明。展开 $a^2 - (p-a)^2$，得到 $-p^2 + 2pa$，显然能被 $p$ 整除。所以 $a^2 \equiv (p-a)^2 \pmod{p}$ 成立，而且这里 $a$ 可以是任意整数。

规律二: $a^{2k}$ 分布对称

第二个规律是：$a^{2k}$ 的分布也是对称的。对满足 $0 < a < p$ 的 $a$ 而言，$a^{2k} \equiv (p-a)^{2k} \pmod{p}$（$k$ 是任意正整数）。

这个规律可以在规律一的基础上证明。把 $k$ 个 $a^2 \equiv (p-a)^2 \pmod{p}$ 的等式乘在一起，就能得到 $a^{2k} \equiv (p-a)^{2k} \pmod{p}$。

规律三: $a^{2k-1}$ + $(p-a)^{2k-1} \equiv 0 \pmod{p}$

第三个规律是：对满足 $0 < a < p$ 的 $a$ 而言，$a^{2k-1} + (p-a)^{2k-1} \equiv 0 \pmod{p}$（$k$ 是任意正整数）。

这个规律可以用二项式定理来证明。令 $K=2k-1$，展开 $a^K + (p-a)^K$，由于 $K$ 是奇数，$a^K$ 和 $(-a)^K$ 会互相抵消，剩下的每一项都包含因子 $p$，所以整个和能被 $p$ 整除。证毕。

规律四: 费马小定理

第四个规律就是大名鼎鼎的费马小定理：对满足 $0 < a < p$ 的 $a$ 而言，$a^{p-1} \equiv 1 \pmod{p}$。

规律五: $a^p \equiv a \pmod{p}$

第五个规律是：对满足 $0 \le a < p$ 的 $a$ 而言，$a^p \equiv a \pmod{p}$。

这个规律的证明很简单：如果 $a=0$，显然成立；如果 $0 < a < p$，由费马小定理 $a^{p-1} \equiv 1 \pmod{p}$，两边乘以 $a$，即得 $a^{p} \equiv a \pmod{p}$。

规律六: 最后一行是 $1$ 和 $p-1$ 交替出现

第六个规律是：最后一行（即 $a=p-1$ 的那一行）是 $1$ 和 $p-1$ 交替出现。即，对任意自然数 $k$，$(p-1)^{2k+1} \equiv -1 \pmod{p}$，$(p-1)^{2k} \equiv 1 \pmod{p}$。

证明思路：先验证 $k=0$ 时成立，然后利用 $(p-1) \equiv -1 \pmod{p}$ 这个基础，将 $p-1$ 或 $-1$ 反复乘到等式两边，就可以得到 $(p-1)^2$、$(p-1)^3$ 等结果，本质上就是数学归纳法。

参考资料

• A Friendly Introduction to Number Theory 中的第 $9$ 章 (Congruences, Powers, and Fermat’s Little Theorem)
• 关于费马小定理的更多介绍，可以参考另一篇文章：[Python] 费马小定理