作者mic2754 (都是假的)
看板Math
标题[代数]
时间Tue Jun 16 03:01:17 2020
http://i.imgur.com/bvyBVCe.jpg
如图两题
想法:
第一题是生成generator常见的操作。因为根据费马小定理，每个选项11次方後再mod89都会是1，所以我的理解是去验证各选项的1到10次方是否为1，若有为1的情况则表示该选项不是generator，这想法应该是没错的，但是如果要这样一个一个检查计算太繁琐了 ，一开始就要先把数字做8次方，真的太难算了，所以上来请问有没有什麽好方法。
第二题就真的几乎没什麽想法了……我只知道+-1绝对是其中两解，1155不是质数所以1应该是存在其他平方根，但是我不太清楚具体上有几组，除非穷举，但是这太不实际了，所以一样放上来请教。
麻烦各位高手了，谢谢。
-----
Sent from JPTT on my Samsung SM-G885Y.
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 49.214.149.67 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1592247679.A.068.html
1F：→ Ricestone : 1.不用算1~10次方，因为11是质数，子群order只会是 06/16 03:15
2F：→ Ricestone : 1或11，只要判断8次方是不是1就好 06/16 03:15
3F：→ Ricestone : 而8次方的mod应该不难算吧，底随时变小就好 06/16 03:20
4F：→ Ricestone : 第一行是指(8次方的)1~10次方，应该知道我的意思 06/16 03:26
5F：推 MisatoMitumi: 1155=3*5*7*11, 所以x^2=1 (mod1155)若且唯若 06/16 04:02
6F：→ MisatoMitumi: x^2=1 (mod 3, 5, 7, 11) 剩的就中国剩余定理和排列 06/16 04:03
7F：→ MisatoMitumi: 组合 06/16 04:03
8F：→ mic2754 : 感谢两位回答，第一题我懂了，第二题还是不大明白， 06/16 09:02
9F：→ mic2754 : 它套用中国剩余定理不是只能解出x^2吗？x还是不知道 06/16 09:02
10F：→ mic2754 : 有多少组x吧？ 06/16 09:02
11F：→ Ricestone : x= 1 or -1 mod p 06/16 09:07
12F：→ Ricestone : p=3,5,7,11 每组会解出一个x 06/16 09:08
有稍微get到一些，但还是没有很懂，能麻烦再解释一下吗？感谢
※ 编辑: mic2754 (1.160.36.187 台湾), 06/16/2020 09:30:25
13F：→ Ricestone : (1,1,1,1),(1,1,1,-1),...,(-1,-1,-1,-1)各只会解出 06/16 09:35
14F：→ Ricestone : 一个x 06/16 09:35
了解，所以答案是2^4=16种罗～
谢谢r大解释
※ 编辑: mic2754 (1.160.36.187 台湾), 06/16/2020 09:43:31
15F：推 Vulpix : 89是质数，Z_89*=Z_88。算完第一个3^8就知道3是gen. 06/16 10:30
16F：→ Vulpix : 所以3^2=9也是。至於6……就再检查吧。 06/16 10:31
17F：推 Vulpix : 反正要检查的四个数字的质因数只有2和3，所以先算 06/16 10:35
18F：→ Vulpix : 3^8=-25,2^8=-11就方便很多了。 06/16 10:35