[代數] 同餘題目求解

[ddv8uc ()]

版上大大們好
(不知道分類有沒有問題... 不曉得該放在哪一區，如有錯誤會即刻更改!)


最近在學同餘,
因為只有基本的概念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
→ Vulpix      : 分類嗎？代數。第一題意思似乎是：m=1024的時候找一
→ Vulpix      : 個a和一個b，讓ax≡1(mod m)在1<x<m中有唯一解，讓
→ Vulpix      : 讓by≡1(mod m)無整數解。換成m=12121也做一次。
→ Vulpix      : 第二題你要不要從m=11,12,13,...一個一個試試看，
→ Vulpix      : 或許會有意外的驚喜？
感謝! 已修改分類!所以一樣是Zi+1=(AZi+R) mod m此公式嗎?
想問一下這個算式是在求甚麼^^"
推 RicciCurvatu: 參考歐拉定理(費馬小定理) 所有跟m互質的數a 都存在
→ RicciCurvatu: b 使得ab=1(mod m) 其中b=a^(f(m)-1) f 是歐拉函數
→ RicciCurvatu: 如果b 是解 b+m也是解 所以你可以找到一個1<b<m 的
→ RicciCurvatu: 解    這個解是唯一的 如果a 不互質 就肯定沒解 第
→ RicciCurvatu: 二題一樣的東西
→ RicciCurvatu: 挑一個m 為質數 每個比他小的a都互質
好哦 所以第二個問題會有滿多組解的嗎????
像是(11.10)(13.11)(17.13)........
但其實意義為只要ma兩個互質?!
不知道這樣理解對不對...
※ 編輯: ddv8uc (178.14.10.114), 10/04/2018 19:07:59
→ Vulpix      : 所以說別執著在那個自己看不懂的東西上。
→ Vulpix      : 找一些小的m來說明吧：
→ Vulpix      : 第一題是這樣的，如果m=6，那2x≡1, 3x≡1, 4x≡1,
→ Vulpix      : 5x≡1四個方程式之中，有沒有哪個有唯一解？有沒有
→ Vulpix      : 無解的呢？答：2x≡1, 3x≡1, 4x≡1都無解，只有
→ Vulpix      : 5x≡1有唯一解。
→ Vulpix      : 第二題，以m=5當例子，2*3≡3*2≡4*4≡1，也就是說
→ Vulpix      : 2x≡1, 3x≡1, 4x≡1都有解。那m=5就有滿足此條件，
→ Vulpix      : 不過題目想找的是比10大的m。m=4,6,9,10,12,14,15,
→ Vulpix      : ...之類的就都一定不行，有猜到規律了嗎？
→ Vulpix      : 而且你沒改到文章外面。
※ 編輯: 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
推 Vulpix      : 重點就是互質沒錯。17是質數。