[代數]

[mic2754 (都是假的)]

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://www.ptt.cc/bbs/Math/M.1592247679.A.068.html
→ Ricestone   : 1.不用算1~10次方，因為11是質數，子群order只會是
→ Ricestone   : 1或11，只要判斷8次方是不是1就好
→ Ricestone   : 而8次方的mod應該不難算吧，底隨時變小就好
→ Ricestone   : 第一行是指(8次方的)1~10次方，應該知道我的意思
推 MisatoMitumi: 1155=3*5*7*11, 所以x^2=1 (mod1155)若且唯若
→ MisatoMitumi: x^2=1 (mod 3, 5, 7, 11) 剩的就中國剩餘定理和排列
→ MisatoMitumi: 組合
→ mic2754     : 感謝兩位回答，第一題我懂了，第二題還是不大明白，
→ mic2754     : 它套用中國剩餘定理不是只能解出x^2嗎？x還是不知道
→ mic2754     : 有多少組x吧？
→ Ricestone   : x= 1 or -1 mod p
→ Ricestone   : p=3,5,7,11  每組會解出一個x
有稍微get到一些，但還是沒有很懂，能麻煩再解釋一下嗎？感謝
※ 編輯: mic2754 (1.160.36.187 臺灣), 06/16/2020 09:30:25
→ Ricestone   : (1,1,1,1),(1,1,1,-1),...,(-1,-1,-1,-1)各只會解出
→ Ricestone   : 一個x
了解，所以答案是2^4=16種囉～
謝謝r大解釋
※ 編輯: mic2754 (1.160.36.187 臺灣), 06/16/2020 09:43:31
推 Vulpix      : 89是質數，Z_89*=Z_88。算完第一個3^8就知道3是gen.
→ Vulpix      : 所以3^2=9也是。至於6……就再檢查吧。
推 Vulpix      : 反正要檢查的四個數字的質因數只有2和3，所以先算
→ Vulpix      : 3^8=-25,2^8=-11就方便很多了。