iq testing series 2

· · 学习·文化课

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 互换得到的二元组。