Maths Olympiad Prep

Library / /420 of 520

Number theory Difficulty 6.7 National olympiad Prove it

20. Let nN,n2n \in \mathbf{N}^{*}, n \geqslant 2. Prove: there exists mNm \in \mathbf{N}^{*}, such that
3n(m3+17)3^{n} \|\left(m^{3}+17\right)

Solution

20. When n=2n=2, taking m=1m=1 suffices. Suppose the proposition holds for n(2)n(\geqslant 2), i.e., there exists mNm \in \mathbf{N}^{*} such that m3+17=3n(3q+r)m^{3}+17=3^{n}(3 q+r), where r{1,2}r \in\{1,2\} and qNq \in \mathbf{N}. In this case, 3m3 \nmid m, hence m2=1(mod3)m^{2}=1(\bmod 3), and thus
3nm23n(mod3n+1)3^{n} \cdot m^{2} \equiv 3^{n}\left(\bmod 3^{n+1}\right)

For any sNs \in \mathbf{N}^{*}, we have
(m+3n1s)3+17=m3+17+3nm2s+32n1ms2+33n3s33n(3q+r)+3ns3n(r+s)(mod3n+1)\begin{aligned} \left(m+3^{n-1} \cdot s\right)^{3}+17 & =m^{3}+17+3^{n} \cdot m^{2} \cdot s+3^{2 n-1} \cdot m \cdot s^{2}+3^{3 n-3} \cdot s^{3} \\ & \equiv 3^{n}(3 q+r)+3^{n} \cdot s \equiv 3^{n}(r+s)\left(\bmod 3^{n+1}\right) \end{aligned}

Thus, taking x1=m+3n1(3r),x2=m+3n1(6r)=x1+3nx_{1}=m+3^{n-1}(3-r), x_{2}=m+3^{n-1}(6-r)=x_{1}+3^{n}, we have 3n+1(x13+17)3^{n+1} \mid\left(x_{1}^{3}+17\right) and 3n+1(x23+17)3^{n+1} \mid\left(x_{2}^{3}+17\right).

Furthermore, if 3n+2(x13+17)3^{n+2} \mid\left(x_{1}^{3}+17\right) and 3n+2(x23+17)3^{n+2} \mid\left(x_{2}^{3}+17\right), then
0x23+17=(x1+3n)3+17=x13+17+3n+1x12+32n+1x1+33nx13+17+3n+13n+1(mod3n+2)\begin{aligned} 0 & \equiv x_{2}^{3}+17=\left(x_{1}+3^{n}\right)^{3}+17=x_{1}^{3}+17+3^{n+1} x_{1}^{2}+3^{2 n+1} x_{1}+3^{3 n} \\ & \equiv x_{1}^{3}+17+3^{n+1} \equiv 3^{n+1}\left(\bmod 3^{n+2}\right) \end{aligned}

This is a contradiction (here we use x121(mod3))\left.x_{1}^{2} \equiv 1(\bmod 3)\right).
Therefore, the proposition holds for n+1n+1 as well.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.