iq testing series 2
luogu_gza
·
2026-11-18 11:23:06
·
学习·文化课
2 较之 1 难度稍微上升了些许。
这次我给题目随便取了一些名字,略微增加了一些趣味性,希望大家做得开心!
根本就没有这样的式子,我只是怕了
求所有正整数对 (a,b) ,使得 a^2+b^2\mid a^3+b^3 ,要求用参数表示全部解,并说明参数需要满足的条件。
::::info[solution]
令 g=\gcd(a,b),a=gx,b=gy ,有 x^2+y^2\mid g(x^3+y^3) 。
记 S=x^2+y^2,T=x^3+y^3 ,由于 T-xS=y^2(y-x) ,有 \gcd(S,T)=\gcd\bigl(S,y^2(y-x)\bigr) ,又 \gcd(x,y)=1 \Rightarrow \gcd(S,y)=1 ,则 \gcd(S,T)=\gcd(S,y-x)=\gcd((y-x)(y+x)+2x^2,y-x)=\gcd(2x^2,y-x)=\gcd(2,y-x) 。
令 \gcd(2,y-x)=\varepsilon ,有当 x,y 均为奇数时 \varepsilon=2 ,否则 \varepsilon=1 。
我们回到 x^2+y^2\mid g(x^3+y^3) \Leftrightarrow S|gT \Leftrightarrow \frac S{\varepsilon} | g ,由此可得 \exist t \in \N^{*},g=t\frac{x^2+y^2}{\varepsilon} 。
因此所有的解可以被表述为 (a,b)=\left(\frac{t x(x^2+y^2)}{\varepsilon},\frac{t y(x^2+y^2)}{\varepsilon}\right) ,其中 t 任意,x,y 是互素的正整数,\varepsilon=\gcd(2,y-x) 。读者可自行验证其充分性。
上上下下
求所有满足 k\ge2 且 2^n+1=n^k 的正整数对 (n,k) 。
::::info[solution]
首先 n 必须为 >1 的奇数,这是显然的。
这个问题看上去很难入手,我们不妨仿照 ez problem 5 取一下 q=\operatorname{minp}(n) ,有 2^n\equiv-1\pmod q ,熟读 super ez problem series 的同学应该很快能反应过来定义 d=\operatorname{ord}_q(2) ,有 d|2n,d|q-1 ,同时 \gcd(n,q-1)=1 ,又有 2^n\equiv-1\pmod q \Rightarrow d \neq 1 ,因此 d=2 。因此 q\mid2^2-1=3 ,只能有 q=3 。
我们强行在这个题里面得到了一些结果,接下来不妨从 3 入手分析一下两侧!
记 t=v_3(n)\ge1 ,我们使用 LTE 有 v_3(2^n+1)=v_3(2+1)+v_3(n)=1+t ,而右侧满足 v_3(n^k)=kt ,比较两侧我们有 (k-1)t=1 ,因此 k=2,t=1 ,原方程变成了 2^n+1=n^2 。
显然在 n \geq 5 时有 2^n>n^2 ,枚举 n=1,2,3,4 可得只有一组解 (n,k)=(3,2) 。
::::
绕了一圈,siuuuuuuu!
求所有有序质数三元组 (p,q,r) ,使得 p\mid3^q+1,q\mid3^r+1,r\mid3^p+1 。
::::info[solution]
显然 p,q,r \neq 3 。
不妨设 p\leq q,p\leq r ,假设 p,q,r 都是奇质数,由 3^q \equiv -1 \pmod p ,有 \operatorname{ord}_p(3)|2q,\operatorname{ord}_p(3) \nmid q ,q 是奇质数所以 \operatorname{ord}_p(3)=2 或 \operatorname{ord}_p(3)=2q 。
若 d=2 则 p|3^2-1=8 与 p 为奇质数矛盾,若 d=2q 则 2q|p-1 与 p \leq q 矛盾,因此 \min(p,q,r)=2 即 p=2 ,由此可得 r|10 。若 r=2 则 q|10 ,即 q=2 或 q=5 ;若 r=5 则 q|244 得 q=2 或 q=61 。
由此可得所有解为 (2,2,2)|(2,2,5),(2,5,2),(5,2,2)|(2,61,5),(61,5,2),(5,2,61) ,我用竖线隔开了本质不同的解。
::::
这应当是简单的
给定整数 n\ge2 ,求
G(n)=\gcd\left(\binom n1,\binom n2,\ldots,\binom n{n-1}\right).
要求根据 n 的质因数分解给出答案。
::::info[solution]
设 p|n,a=v_p(n) ,我们先证引理 v_p\left(\binom nk\right)=a-v_p(k) 。
对任意 1\le i<p^a ,设 i=p^t u ,其中 p\nmid u ,则 t<a 。把 n 写作 p^a m 后,n-i=p^t\left(p^{a-t}m-u\right) ,因此有 v_p(n-i)=t=v_p(i) 。
由此我们计算得到 v_p\left(\binom{n-1}{k-1}\right)=0 ,再由 k\binom nk=n\binom{n-1}{k-1} 可得 v_p(k)+v_p\left(\binom nk\right)=a ,即为引理。
接下来我们分类讨论,若 n 为质数幂 p^a 则有 v_p\left(\binom nk\right)=a-v_p(k)\ge1 ,因此 p\mid G(n) ,又有 v_p\left(\binom n{p^{a-1}}\right)=1 ,则 G(n)\mid p ,因此 G(n)=p 。若 n 不是质数幂,取其一质因子 p ,同样设 a=v_p(n) ,则 v_p\left(\binom n{p^a}\right)=a-v_p(p^a)=0 ,因此 p \nmid G(n) ,这对 n 的每个质因子都成立,同时 G(n)|n ,因此 G(n)=1 。
当然如果用 Lucas 定理的话这个题是显然的,这里展示了一下古法(
无可奈何花落去,
求所有正整数对 (a,b) ,使得 ab\mid a^2+b^2+1 。
::::info[solution]
不妨令 k=\frac{a^2+b^2+1}{ab} ,因为 a^2+b^2\ge2ab ,所以 k>2 。k 又是整数,因此 k\ge3 。
不妨设 a \leq b ,若 a=b ,则 a^2\mid2a^2+1 迫使 a=b=1 ,此时 k=3 。若 a=1 ,则 b\mid b^2+2 ,即 b\mid2 ,所以 b=1 或 2 ,也都有 k=3 。下面设 2\le a<b 。原等式可写成 b^2-kab+(a^2+1)=0 ,这可以视作是一个关于 b 的二次方程,定义 c=ka-b ,由韦达定理,c 是这个二次方程的另一个根且有 bc=a^2+1 。又 b \geq a+1 ,所以 c\le\frac{a^2+1}{a+1}
=a-1+\frac2{a+1}<a ,因此 (c,a) 也是原问题的一组解。
由于不满足 2\le a<b 的解都满足 k=3 ,因此我们可以发现一个惊人的结论:所有的解都满足 k=3 。
所以所有的解都这样递归,(a,b) \to (3a-b,a) ,我们逆转这一过程变成 (u,v) \to(v,3v-u) ,即可生成所有的解。
答案:定义 u_0=u_1=1,u_{m+2}=3u_{m+1}-u_m\quad(m\ge0) ,所有解为 (a,b)=(u_m,u_{m+1})(m\ge0) 与 a,b 互换得到的二元组。