Tìm số nguyên dương x nhỏ nhất sao cho 2^n là ước của 3^x - 1

Duc_Manh_Pham · October 22, 2023, 2:37pm

Chào mọi người ạ.
Em xin gợi ý về cách giải bài này ạ. Chúc mọi người 1 ngày vui vẻ !

Cho số nguyên dương n, tìm số nguyên dương x nhỏ nhất sao cho 2^n là ước của 3^x - 1.

Điều kiện đầu vào:
n <= 10^18

Điều kiện đầu ra:
In ra kết quả số nguyên x, nếu x <= 10^9 + 7.

Nếu x > 10^9 + 7, thì in ra số dư của x cho 10^9 + 7.

tntxtnt · October 23, 2023, 12:02am

chạy trâu với mấy số n nhỏ là thấy quy luật à

p = 1
for n in range(1, 15):
    p *= 2
    x = 1
    while (3**x - 1) % p != 0: x += 1
    print("2^{{{}}} &\mid 3^{{{}}} - 1 \\\\".format(n, x))

n=1: 3^1 - 1 = 2 chia hết cho 2^1 = 2
hay ghi lại là :V

\begin{aligned} 2^{1} &\mid 3^{1} - 1 \\ 2^{2} &\mid 3^{2} - 1 \\ 2^{3} &\mid 3^{2} - 1 \\ 2^{4} &\mid 3^{4} - 1 \\ 2^{5} &\mid 3^{8} - 1 \\ 2^{6} &\mid 3^{16} - 1 \\ 2^{7} &\mid 3^{32} - 1 \\ 2^{8} &\mid 3^{64} - 1 \\ 2^{9} &\mid 3^{128} - 1 \\ 2^{10} &\mid 3^{256} - 1 \\ 2^{11} &\mid 3^{512} - 1 \\ 2^{12} &\mid 3^{1024} - 1 \\ 2^{13} &\mid 3^{2048} - 1 \\ 2^{14} &\mid 3^{4096} - 1 \\ \end{aligned}

thấy quy luật chưa :V :V

chứng minh thì cũng tương đối “dễ”:
giả sử 3^x - 1 chia hết cho 2^n và x là nhỏ nhất, bây giờ cần tìm y > 0 nhỏ nhất sao cho 3^{x+y} - 1 chia hết cho 2^{n+1}. Ta có: 3^{x+y} - 1 = 3^x3^y - 1 = 3^x3^y - 3^y + 3^y - 1 = 3^y(3^x - 1) + 3^y - 1. Vì 3^y ko chia hết cho 2 nên muốn tổng này chia hết cho 2^n thì 3^y - 1 phải chia hết cho 2^n, cần y nhỏ nhất mà theo giả thuyết thì x là số nhỏ nhất để 3^x - 1 chia hết cho 2^n, vậy y = x. Khi này 3^y(3^x - 1) + 3^y - 1 = 3^x(3^x - 1) + 3^x - 1 = (3^x - 1)(3^x + 1), vì 3^x là số lẻ nên 3^x + 1 là số chẵn, vậy (3^x - 1)(3^x + 1) = 3^{2x} - 1 sẽ chia hết cho 2^n * 2 = 2^{n+1}.

quy luật này có vấp ở chỗ 2^3 ko xài 3^4 - 1 mà xài 3^2 - 1 như 2^2 vì chứng minh trên chưa tính tới trường hợp 3^x - 1 chia hết cho cả 2^{n+1} sẵn rồi :V Để chứng minh 2^3 là trường hợp duy nhất cũng dễ: giả sử 3^x - 1 chia hết cho 2^n nhưng ko chia hết cho 2^{n+1}, và 3^{2x} - 1 chia hết cho tận 2^{n+2}. Tách 3^{2x} - 1 ra thành (3^x - 1)(3^x + 1), thì vì 3^x - 1 chỉ chia hết cho 2^n nên để (3^x - 1)(3^x + 1) chia hết cho 2^{n+2} thì 3^x + 1 phải chia hết cho 4. Vì 3 \equiv -1 \mod 4 nên để 3^x + 1 chia hết cho 4 thì 3^x phải đồng dư -1 mod 4, hay (-1)^x \equiv -1 \mod 4, hay x là số lẻ. Nhưng theo quy luật double ở trên: x thành 2x, 2x thành 4x, v.v… thì ta có công thức tổng quát của x là x = 2^k với k \ge 0, vậy chỉ có 1 x lẻ duy nhất là x = 2^0 = 1, hay chính là trường hợp 3^1 - 1 chia hết cho 2^1 nhưng ko chia hết cho 2^2, và 3^2 - 1 nhảy cóc 1 bước, chia hết cho tận 2^3.

vậy công thức tổng quát là \boxed{ \begin{cases} x = n &\text{if } n \le 2 \\ x = 2^{n-2} &\text{if } n > 2 \end{cases} }

rogp10 · October 23, 2023, 1:03pm

Đặt f(x) là số thừa số 2 của 3^x - 1
Ta có 3^{2k+1} - 1^{2k+1} = (3 - 1)(3^{2k} + 3^{2k-1} + ... + 3^1 + 1) = 2 \cdot \text{số lẻ} nên f(2k+1) = 1.
Xét x có dạng 4k+2: 3^{2k+1} + 1 \equiv 3+1 = 4 \pmod 8 nên f(4k+2) = 1+2 = 3 (HĐTĐN)
Với x = 2^m \cdot w (w lẻ, m \geq 1), 3^{2k} + 1 \equiv 2 \pmod 8 nên f(2x) = f(x) + 1 (HĐTĐN), hay f(x) = 3 + m - 1 = 2 + m

Vậy đáp số là \begin{cases} x = n &\text {nếu }n \in \{1, 2\}\\ x = 2^{n-2} & \text {nếu }n > 2 \end{cases}

Duc_Manh_Pham · October 23, 2023, 3:20am

Cảm ơn mọi người nhiều ạ !