Re: [代數] 同餘性質/中國剩餘定理
※ 引述《zn310 (動流的氣空)》之銘言：
: 請教一個問題
: 已知 10^a≡1 (mod m)
: 10^b≡1 (mod n) 其中m、n均不為2、5的倍數 且 (m,n)=1
: 求解 10^x≡1 (mod mn)
: 答： x=[a,b]
: 請問要怎麼解？
: 感謝大家幫忙。
這題可能要加點條件?
舉例來說
m=9 n=11 a=4 b=6
照答案x=12 但實際上x=2
如果a,b是最小的正整數 滿足
10^a≡1 (mod m)
10^b≡1 (mod n)
10^x≡1 (mod mn) -> 存在A 使得 10^x=Amn+1
-> Amn+1≡1 (mod m)
-> 10^x≡1 (mod m)
-> x是a的倍數
同理 x是b的倍數
則 x=[a,b] (應該是x=a b 的公倍數吧 從題意沒看出需要侷限在最小公倍數)
一點淺見 有錯勿怪
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 1.175.221.116
推
11/12 13:43, , 1F
11/12 13:43, 1F
→
11/12 13:45, , 2F
11/12 13:45, 2F
如果a,b是最小的正整數 滿足
10^a≡1 (mod m)
10^b≡1 (mod n)
則10^1 10^2 10^3 .... 10^(a-1) 除以m 餘數不為1
所以 x>a-1
令x=a+t t不為負整數
10^x=10^a * 10^t ≡1 * 10^t≡1 (mod m) -> 10^t≡1 (mod m)
-> t=0或a的倍數
-> x為a的倍數
※ 編輯: wuwman 來自: 1.175.221.116 (11/12 16:13)
推
11/12 21:58, , 3F
11/12 21:58, 3F
→
11/12 22:01, , 4F
11/12 22:01, 4F
→
11/12 22:03, , 5F
11/12 22:03, 5F
→
11/12 22:04, , 6F
11/12 22:04, 6F
→
11/12 22:04, , 7F
11/12 22:04, 7F
跟你的想法差不多
0<t<a
跟 "a是最小正整數數 滿足
10^a≡1 (mod m)" 矛盾
a<t
存在n
使得
t=a*n+(t-a*n) 此時 0<t-a*n<a
10^t=(10^an)*(10^(t-an))≡1 (mod m) -> (10^(t-an))≡1 (mod m) 且0<t-an<a
->跟"a是最小....."矛盾
※ 編輯: wuwman 來自: 1.175.221.116 (11/13 01:23)
推
11/13 21:56, , 8F
11/13 21:56, 8F
→
11/10 10:58, , 9F
11/10 10:58, 9F
→
01/02 15:07,
7年前
, 10F
01/02 15:07, 10F
討論串 (同標題文章)