[代數] 同餘題目求解

看板Math作者時間7年前 (2018/10/04 02:23), 7年前編輯推噓2(2推 0噓 21→)
留言23則, 2人參與, 7年前最新討論串1/1
版上大大們好 (不知道分類有沒有問題... 不曉得該放在哪一區，如有錯誤會即刻更改!) 最近在學同餘, 因為只有基本的概念QQ 所以煩請版上大大解說的時候 稍微多一點點解釋mV___Vm 第一個題目是這樣的 請從a)m=1024 b)=12121 裡選出符合的數字滿足下列的條件 ˙一個自然數 1<a<m, 並 方程式 a · x ≡ 1 mod m 成立, x屬於自然數並為唯一解， 另一個自然數　b<m, 並 方程式 b · y ≡ 1 mod m 成立, y屬於自然數並沒有解。 我覺得答案應該為a) 因為1<a<m 所以當初設a*x為1023, 所以a,x的解便只有(1023,1)(341,3) 但這樣就不符合唯一解的要求了QQ 像這類的題目該怎麼找題庫來做練習呢? 該搜尋同餘方程式嗎? 第二個題目是 請給出一個數字，m為自然數並且m>10，滿足下列方程式 a · x ≡ 1 mod m 而對於每一個自然數a，a<m，並使x都有一個整數解。 （並請帶解釋，為何你給的數字有此屬性） 這個就完全無頭緒了，該用Zi+1=(AZi+r) mod m 下去做嗎? 但是為甚麼QQQ 老實說Zi+1=(AZi+r) mod m 這個算式我也不是很懂QQQ 先謝過各位大大們了!!! -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 84.59.59.195 ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1538591015.A.C30.html
→
10/04 02:37, 7年前 , 1F
分類嗎？代數。第一題意思似乎是：m=1024的時候找一
10/04 02:37, 1F
→
10/04 02:40, 7年前 , 2F
個a和一個b，讓ax≡1(mod m)在1<x<m中有唯一解，讓
10/04 02:40, 2F
→
10/04 02:41, 7年前 , 3F
讓by≡1(mod m)無整數解。換成m=12121也做一次。
10/04 02:41, 3F
→
10/04 02:42, 7年前 , 4F
第二題你要不要從m=11,12,13,...一個一個試試看，
10/04 02:42, 4F
→
10/04 02:42, 7年前 , 5F
或許會有意外的驚喜？
10/04 02:42, 5F
感謝! 已修改分類!所以一樣是Zi+1=(AZi+R) mod m此公式嗎? 想問一下這個算式是在求甚麼^^"
推
10/04 07:20, 7年前 , 6F
參考歐拉定理(費馬小定理) 所有跟m互質的數a 都存在
10/04 07:20, 6F
→
10/04 07:20, 7年前 , 7F
b 使得ab=1(mod m) 其中b=a^(f(m)-1) f 是歐拉函數
10/04 07:20, 7F
→
10/04 07:20, 7年前 , 8F
如果b 是解 b+m也是解 所以你可以找到一個1<b<m 的
10/04 07:20, 8F
→
10/04 07:20, 7年前 , 9F
解 這個解是唯一的 如果a 不互質 就肯定沒解 第
10/04 07:20, 9F
→
10/04 07:20, 7年前 , 10F
二題一樣的東西
10/04 07:20, 10F
→
10/04 07:21, 7年前 , 11F
挑一個m 為質數 每個比他小的a都互質
10/04 07:21, 11F
好哦 所以第二個問題會有滿多組解的嗎???? 像是(11.10)(13.11)(17.13)........ 但其實意義為只要ma兩個互質?! 不知道這樣理解對不對... ※ 編輯: ddv8uc (178.14.10.114), 10/04/2018 19:07:59
→
10/04 21:19, 7年前 , 12F
所以說別執著在那個自己看不懂的東西上。
10/04 21:19, 12F
→
10/04 21:21, 7年前 , 13F
找一些小的m來說明吧：
10/04 21:21, 13F
→
10/04 21:22, 7年前 , 14F
第一題是這樣的，如果m=6，那2x≡1, 3x≡1, 4x≡1,
10/04 21:22, 14F
→
10/04 21:23, 7年前 , 15F
5x≡1四個方程式之中，有沒有哪個有唯一解？有沒有
10/04 21:23, 15F
→
10/04 21:24, 7年前 , 16F
無解的呢？答：2x≡1, 3x≡1, 4x≡1都無解，只有
10/04 21:24, 16F
→
10/04 21:24, 7年前 , 17F
5x≡1有唯一解。
10/04 21:24, 17F
→
10/04 21:26, 7年前 , 18F
第二題，以m=5當例子，2*3≡3*2≡4*4≡1，也就是說
10/04 21:26, 18F
→
10/04 21:27, 7年前 , 19F
2x≡1, 3x≡1, 4x≡1都有解。那m=5就有滿足此條件，
10/04 21:27, 19F
→
10/04 21:28, 7年前 , 20F
不過題目想找的是比10大的m。m=4,6,9,10,12,14,15,
10/04 21:28, 20F
→
10/04 21:28, 7年前 , 21F
...之類的就都一定不行，有猜到規律了嗎？
10/04 21:28, 21F
→
10/04 21:40, 7年前 , 22F
而且你沒改到文章外面。
10/04 21:40, 22F
※ 編輯: ddv8uc (178.14.10.114), 10/05/2018 03:43:40 意思是 如果m和a兩數的最大公因數為1就會有解嗎? 我剛剛試著第二題代M為17, 可以從1~16得出X為整數並且同餘1的解 謝謝你的講解 雖然我還是覺得很模糊..這樣第二題我是該將所有ax的結果都寫上去嗎 我會再問老師這個概念QQ ※ 編輯: ddv8uc (178.14.10.114), 10/05/2018 04:49:55
推
10/05 04:57, 7年前 , 23F
重點就是互質沒錯。17是質數。
10/05 04:57, 23F
‣ 更多 ddv8uc 的文章
文章代碼(AID): #1RjGadmm (Math)