惊人的数学美------2幂次剩余变换图

mathematica

n是一个大于2的自然数，以Zn\0（n的完全剩余系去掉0）为顶点集V定义有向图G(V,E)，其中边集E的定义如下：对V中的任意两点 u和 v，e(u, v)∈E当且仅当v=u^2(mod n).  这里的有向边e(u, v)规定为u→v.
顺着箭头的方向，路线总是“2次非剩余→2次剩余→4次剩余→8次剩余→…→2^k次剩余”，故可称图G(V, E)为Zn的2幂次剩余变换图。以下将图G(V, E)简记为Gn.
Gn的mathematica代码:

1. n = Input["请输入1个大于2的整数)"]; GraphPlot[Table[i -> Mod[i^2, n], {i, 1, n - 1}]]

复制代码

下面是G65537，G257，G300

我玩mathematica时偶然发现，仅当n=3, 5, 17, 257, 65537时Gn才是连通的，对于其它的n，图总是不连通的。

所以我猜想:   当且仅当n为费马素数时，Gn 是连通的。

记Gn的最大连通子图数为g(n)，我们看到g(257)=g(65537)=1, g(300)=12. 我的猜想就是g(n)=1当仅且当n为费马素数。更一般地，我想知道g(n)是否有简明的数论表达式。

形象一点说，就是 海面上有n-1个小岛（抽象成点），依次标记为1、2、3、4、5、...、n-1，若 j=i^2(mod n), 就架一座岛 i 至岛 j 的桥（抽象成图的边）。如果一个人可以从一个岛通过桥到达其它任意一座岛，我们猜想 n 一定是费马素数.

mathematica

这个似乎是图论和数论的结合!真的很有意思,不知道哪位高手能够解决一下?

mathematica

n = 12; Table[i -> Mod[i^2, n], {i, 1, n - 1}]
{1 -> 1, 2 -> 4, 3 -> 9, 4 -> 4, 5 -> 1, 6 -> 0, 7 -> 1, 8 -> 4,
9 -> 9, 10 -> 4, 11 -> 1}


n = 17; Table[i -> Mod[i^2, n], {i, 1, n - 1}]
{1 -> 1, 2 -> 4, 3 -> 9, 4 -> 16, 5 -> 8, 6 -> 2, 7 -> 15, 8 -> 13,
9 -> 13, 10 -> 15, 11 -> 2, 12 -> 8, 13 -> 16, 14 -> 9, 15 -> 4,
16 -> 1}

mathematica

如果要孤立的话,一定是一个素数!

mathematica

惊人的数学美
请下载附件,免费的附件!

hujunhua

按有向图证明。Gn是一个有向二叉图，除了作为“叶结点”（借用一下二叉树中的术语）的非二次非剩余，其它的每个顶点都是二进一出。任何顶点都不可能有二出，因为一个数不可能是两个不同的二次剩余。
顺着箭头的方向，路线总是陷入一个循环圈，所以从循环圈不可能有出来的箭头。故一个连通子图不可能含有两个圈，否则连接两个圈的路线上必有一点是一进二出，这不可能。
记m=EulerPhi(n)        (注：n的简化剩余系长度）
…………(太晚了，删掉又可惜，留待有空来续，欢迎接龙）

wayne

6# hujunhua
老大总是午夜过后出现，像幽灵一样，。。。。

wayne

6# hujunhua
我倒是关注显示层面的东西。
不知道Mathematica究竟是如何把图整的那么美观的
这个美化的算法一定也很不简单的吧

mathematica

按有向图证明。Gn是一个有向二叉图，除了作为“叶结点”（借用一下二叉树中的术语）的非二次非剩余，其它的每个顶点都是二进一出。任何顶点都不可能有二出，因为一个数不可能是两个不同的二次剩余。
顺着箭头的方向 ...
hujunhua 发表于 2011-3-15 02:50

并非是完全剩余系,因为不包含零,其实我也知道可以用图论的术语进行叙述,
但是我觉得用通俗的语言更能为别人明白.

hujunhua

“老大总是午夜过后出现，像幽灵一样，。。。。”

今年开年以来都比较忙，木办法。

“并非是完全剩余系,因为不包含零,其实我也知道可以用图论的术语进行叙述, 但是我觉得用通俗的语言更能为别人明白. ”

已经改过来了。你的通俗的语言基本上保留了，不能光是通俗的吧。