大家做做这个

STEM版,合并数学,物理,化学,科学,工程,机械。不包括生物、医学相关,和计算机相关内容。

版主: verdeliteTheMatrix

头像
(ヅ)楼主
论坛支柱
论坛支柱
帖子互动: 544
帖子: 11677
注册时间: 2022年 8月 21日 14:20

Re: 大家做做这个

帖子 (ヅ)楼主 »

YWY 写了: 2023年 1月 24日 01:44 这就是“2是primitive root mod 2N-1”的定义,就是说2至少要phi(2N-1)次幂才等于1 mod 2N-1。注意2的phi(2N-1)次幂肯定等于1 mod 2N-1(欧拉定理),这是你一楼洗牌题证明的关键。
你是对的,一回家脑袋就糊涂了!
头像
(ヅ)楼主
论坛支柱
论坛支柱
帖子互动: 544
帖子: 11677
注册时间: 2022年 8月 21日 14:20

Re: 大家做做这个

帖子 (ヅ)楼主 »

YWY 写了: 2023年 1月 24日 00:54 没有直接关系但又间接关系。“2是primitive root mod 2N-1”是说需要至少phi(2N-1)次(欧拉数)才能还原。注意phi(2N-1)小于等于2N-2。所以,“需要最少洗2N-2次才能还原”的充要条件是“phi(2N-1) = 2N-2而且2是primitive root mod 2N-1”。但phi(2N-1) = 2N-2当且仅当2N-1等于一个奇素数。所以“需要最少洗2N-2次才能还原”的充要条件是“2N-1是奇素数而且2是primitive root mod 2N-1”。这样,“N = (p+1)/2 where p is an odd prime”是必要条件,“2是primitive root mod 2N-1”也是必要条件。还有,通过考虑二次剩余,“2是primitive root mod p”的必要条件是“p = 3 or 5 mod 8”。所以“需要最少洗2N-2次才能还原”的必要条件是“N = (p+1)/2 where p is an odd prime and p = 3 or 5 mod 8”。
想明白了,很赞的分析

"2是primitive root mod p”的必要条件是“p = 3 or 5 mod 8"只能是必要条件,充分条件不能满足,有一反例p = 43
头像
YWY(夜未央)
论坛支柱
论坛支柱
2023-24年度十大优秀网友
帖子互动: 1267
帖子: 13853
注册时间: 2022年 7月 22日 17:25

Re: 大家做做这个

帖子 YWY(夜未央) »

(ヅ) 写了: 2023年 1月 24日 14:45 想明白了,很赞的分析

"2是primitive root mod p”的必要条件是“p = 3 or 5 mod 8"只能是必要条件,充分条件不能满足,有一反例p = 43
一楼的题很棒,证明方法也很赞,很开阔人的思路。
持仓抄底锁利,你钱你定
看牛观猪喊熊,自娱自乐
股市变幻莫测,不作不死
赌途曲折无常,吃枣药丸
FoxMe(令狐)
论坛精英
论坛精英
帖子互动: 144
帖子: 5334
注册时间: 2022年 7月 26日 16:46

Re: 大家做做这个

帖子 FoxMe(令狐) »

FGH 写了: 2023年 1月 23日 12:55 根据wiki的提示,
https://en.wikipedia.org/wiki/Faro_shuffle#cite_note-7
搞明白该怎么做。考虑另一种洗牌:
1 2 3 4 5 6 7 8
5 1 6 2 7 3 8 4
这种的2N张牌和楼主的2N+2张牌是一一对应。

然后只需要观察到一个现象:洗一次牌后,n号牌到达2n mod (2N+1)的位置。
这种洗牌方法的次数最多是phi(2N+1) <= 2N。

排列组合的题,不给点提示很难做,可能是为什么要群论的原因。
FoxMe(令狐)
论坛精英
论坛精英
帖子互动: 144
帖子: 5334
注册时间: 2022年 7月 26日 16:46

Re: 大家做做这个

帖子 FoxMe(令狐) »

(ヅ) 写了: 2023年 1月 24日 14:45 想明白了,很赞的分析

"2是primitive root mod p”的必要条件是“p = 3 or 5 mod 8"只能是必要条件,充分条件不能满足,有一反例p = 43
看来充分必要条件不好推,有人做了一张表:

http://oeis.org/A001122/b001122.txt
x1 图片
头像
(ヅ)楼主
论坛支柱
论坛支柱
帖子互动: 544
帖子: 11677
注册时间: 2022年 8月 21日 14:20

Re: 大家做做这个

帖子 (ヅ)楼主 »

研究了一下,一个充分条件是

如果N-1是Sophie Germain 质数,即N-1和2N-1同为质数,那么2是prm 2N - 1.

这个办法会漏掉不少,在3-100里面,通过这个条件能找到满足2是prm 2N-1的2N-1有11, 59, 83。

实际上满足2是prm2N-1的有3,5,11,13,19,29,37,53,59,61,67,83
回复

回到 “STEM”