2021年5月25日 星期二

訓練數學感 293 ─ 解餘數

http://4rdp.blogspot.com/2021/05/293.html?m=0

已知 8-1 可被 49 整除,n∈N,試求 n 最小值

難度

這題又是 Andy 洗澡時想到的,會想到這個問題,是因為資工可能處理密碼類問題,另外它屬離散數學。

Andy 給了個提示費馬小定理,很適合解餘數問題,而我從這題想到求第二小值。

12 則留言:

  1. 作者已經移除這則留言。

    回覆刪除
  2. 8n -1 可被 49 整除, 利用同餘理論, 可化為 8^n ≡ 1(mod 49)
    49 不為質數, 不能用費馬小定理, 必須用歐拉定理
    n值是所有小於或等於 49 的正整數中與 49 互質的數的個數, 故為42

    回覆刪除
    回覆
    1. 我同意您的觀點,應該使用歐拉定理,不管運用費馬小定理還是歐拉定理,不保證該數質是最小符合整除的數值,所以 n=42,只表示 8^42-1 可被 49 整除,但不表示它是最小符合條件的。

      刪除
  3. 錯, 不是用程式解, 複習一些數論, 同餘理論的資料知道解法

    以二進位制觀點來解

    1. 8 用二進制表示為1000, 8^n 二進制表示 1 之後有 n+2 個0, 8^n -1 二進制表示 有 n+2 個1
    7 用二進制表示為111,

    2. 用二進制表示為111的7 要能整除 用二進制表示 有 n+2 個1 的8^n -1
    n 最少須為1, 也就是 111
    8^n -1 還必須被7再整除一次, 1+2個1必須再加 6 個1, 也就是111111111, n+2=9 因此 n=7

    回覆刪除
  4. 謝謝您的說明,二進制值,我還沒這樣想過,您說的內容有些許錯誤,我更正一下
    n=1, 8^n=0b1000, 8^n-1=0b111
    n=2, 8^n=0b1000000 8^n-1=0b111111 n 每增加一個,8^n-1 二進制就會增加三個 1

    n=7, 8^n=0b1000000000000000000000, 8^n-1=0b111111111111111111111

    49 = 0b110001
    (8^7-1)/49 = 42799 = 0b1010011100101111

    回覆刪除