Re: [代數] 同餘性質/中國剩餘定理

[wuwman (無啥豪)]

※ 引述《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
推 zn310       :喔  我懂了 萬分感謝!! 再請教為甚麼10^x≡1 (mod m)
→ zn310       :就保證x是a的倍數？ 是不是先假設x=a+t去證明？
如果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)
推 zn310       :10^t≡1 (mod m)-> t=0或a的倍數，我這裡不明白^^"
→ zn310       :除了10^a+1=10^a*10≡1*10≡1(mod m)矛盾
→ zn310       :因為a是滿足10^a≡1 (mod m)的最小正整數
→ zn310       :且a>1 這個方法慢慢推之外，有沒有比較好的方法？
→ zn310       :真的很感謝您願意回答我的問題^^
跟你的想法差不多
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)
推 zn310       :很完整   謝謝您!! ^^
→ sneak       : 10^t≡1 (mod https://muxiv.com
→ sneak       : 就保證x是a的倍數？  http://yofuk.com