作者HmmHmm (凝结的时间)
看板Math
标题Re: [中学]高中数学竞赛题
时间Fri Mar 5 23:04:28 2021
※ 引述《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://webptt.com/cn.aspx?n=bbs/Math/M.1614956671.A.AED.html
1F：推 chemmachine : 推推 美妙 03/06 10:41