2021年5月25日 星期二

訓練數學感 293 ─ 解餘數

http://4rdp.blogspot.com/2021/05/293.html

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

難度 ✩✩✩

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

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

標籤： ,

12 則留言:

  1. 羅新義2021年9月12日 下午3:12

    作者已經移除這則留言。

    回覆刪除
  2. 羅新義2021年9月12日 下午3:36

    42

    回覆刪除
  3. 羅新義2021年9月12日 下午4:23

    第二小值 21

    回覆刪除
  4. 羅新義2021年9月12日 晚上8:37

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

    回覆刪除
    回覆
    1. Bridan2021年9月12日 晚上9:13

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

      刪除
  5. 羅新義2021年9月17日 上午11:59

    最小值 7

    回覆刪除
  6. 羅新義2021年9月17日 晚上9:23

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

    以二進位制觀點來解

    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

    回覆刪除
  7. Bridan2021年9月17日 晚上11:53

    謝謝您的說明，二進制值，我還沒這樣想過，您說的內容有些許錯誤，我更正一下
    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

    回覆刪除

訂閱： 張貼留言 (Atom)