找回密码
 欢迎注册
查看: 42185|回复: 15

[提问] 惊人的数学美------2幂次剩余变换图

[复制链接]
发表于 2011-3-14 15:32:25 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
本帖最后由 hujunhua 于 2011-3-15 11:33 编辑 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 001.jpg 002.jpg 003.jpg 我玩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 一定是费马素数.

评分

参与人数 1威望 +2 收起 理由
zgg___ + 2 恩,好看。

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2011-3-14 15:34:20 | 显示全部楼层
这个似乎是图论和数论的结合!真的很有意思,不知道哪位高手能够解决一下?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2011-3-14 15:35:19 | 显示全部楼层
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}
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2011-3-14 20:21:29 | 显示全部楼层
如果要孤立的话,一定是一个素数!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2011-3-14 20:27:51 | 显示全部楼层
惊人的数学美 请下载附件,免费的附件!

fermat.rar

384.69 KB, 下载次数: 31, 下载积分: 金币 -1 枚, 经验 1 点, 下载 1 次

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-3-15 02:50:45 | 显示全部楼层
按有向图证明。Gn是一个有向二叉图,除了作为“叶结点”(借用一下二叉树中的术语)的非二次非剩余,其它的每个顶点都是二进一出。任何顶点都不可能有二出,因为一个数不可能是两个不同的二次剩余。 顺着箭头的方向,路线总是陷入一个循环圈,所以从循环圈不可能有出来的箭头。故一个连通子图不可能含有两个圈,否则连接两个圈的路线上必有一点是一进二出,这不可能。 记m=EulerPhi(n) (注:n的简化剩余系长度) …………(太晚了,删掉又可惜,留待有空来续,欢迎接龙)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-3-15 07:32:34 | 显示全部楼层
6# hujunhua 老大总是午夜过后出现,像幽灵一样,。。。。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-3-15 07:38:21 | 显示全部楼层
6# hujunhua 我倒是关注显示层面的东西。 不知道Mathematica究竟是如何把图整的那么美观的 这个美化的算法一定也很不简单的吧
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2011-3-15 08:25:18 | 显示全部楼层
按有向图证明。Gn是一个有向二叉图,除了作为“叶结点”(借用一下二叉树中的术语)的非二次非剩余,其它的每个顶点都是二进一出。任何顶点都不可能有二出,因为一个数不可能是两个不同的二次剩余。 顺着箭头的方向 ... hujunhua 发表于 2011-3-15 02:50
并非是完全剩余系,因为不包含零,其实我也知道可以用图论的术语进行叙述, 但是我觉得用通俗的语言更能为别人明白.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-3-15 11:38:45 | 显示全部楼层
“老大总是午夜过后出现,像幽灵一样,。。。。” 今年开年以来都比较忙,木办法。 “并非是完全剩余系,因为不包含零,其实我也知道可以用图论的术语进行叙述, 但是我觉得用通俗的语言更能为别人明白. ” 已经改过来了。你的通俗的语言基本上保留了,不能光是通俗的吧。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-11-22 21:59 , Processed in 0.029459 second(s), 20 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表