推 chemmachine : 推推 美妙 03/06 10:41
※ 引述《adamchi (adamchi)》之銘言:
: 1.設n是使得149^n-2^n可以被3^3*5^5*7^7整除的最小正整數.
: 試問n的正因數的個數為何?
: 答:270
先考慮 7^7 可以整除
149^n-2^n = (149-2)(149^{n-1}+ 149^{n-2}*2 +....+2^{n-1})
7^2 可以整除 149-2 = 147, 但是 7^3 不行
因此 7 整除後面那個括號
149^{n-1}+ 149^{n-2}*2 +....+2^{n-1} = n*2^{n-1} (mod 7)
因此 n= 7m
149^n-2^n = 149^{7m}-2^{7m}
= (149^7 - 2^7)*(149^7^{m-1}+ ....+2^7^{m-1})
= (149-2)(149^6 + ...+2^6)*(149^7^{m-1}+ ....+2^7^{m-1})
7^2 整除 147 但 7^3 不行
mod 49 可知 7 整除第二個括號但是 7^2 不行
所以三個括號可以被 7 整除,所以跟上面一樣的方法可以推出 7| m
ok, 接著你就繼續做下去反正數學競賽時間很長.....
呃 還是聰明一點好了
回到原點 假設 n = 7^a*m, (m, 7) = 1
由上面的觀察你可以假設 對每個 n, 7^{b+2}整除 (149^7^b-2^7^b)
但是 7^{b+3} 不行
149^n - 2^n = (149^7^a-2^7^a)((149^7^a)^(m-1) +.....+ (2^7^a)^(m-1)}
mod 7 就知道後面那個括號不能被 7 整除
這樣我們就得到 a = 5
這套方法對 3 跟 5 作一遍你應該就會得到答案了
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 218.173.2.190 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1614956671.A.AED.html