Maths Olympiad Prep

Library / /484 of 520

Number theory Difficulty 7.2 National olympiad, round 2 Prove it

Lemma 6 We have
N(1)=Q(1)=4,P(1)=2,P(2)=1Q(n)=4P(n),n>1\begin{array}{c} N(1)=Q(1)=4, \quad P(1)=2, \quad P(2)=1 \\ Q(n)=4 P(n), \quad n>1 \end{array}

and
N(n)=d2nQ(nd2),n1N(n)=\sum_{d^{2} \mid n} Q\left(\frac{n}{d^{2}}\right), \quad n \geqslant 1

Solution

Prove that when n=1n=1, all solutions of the indeterminate equation (20) are
{±1,0},{0,±1};\{ \pm 1,0\}, \quad\{0, \pm 1\} ;

When n=2n=2, all solutions are
{±1,±1}.\{ \pm 1, \pm 1\} .

This leads to equation (23). The primitive solutions x,yx, y of the indeterminate equation (20) must satisfy
(x,y)=(n,xy)=1(x, y)=(n, x y)=1

Therefore, when n>1n>1, it must be that
x1,y1|x| \geqslant 1, \quad|y| \geqslant 1

and x,y|x|,|y| are non-negative primitive solutions of (20). Thus, when n>1n>1, the non-negative primitive solutions x1,y1x_{1}, y_{1} of the indeterminate equation (20) must be positive, and ±x1,±y1\pm x_{1}, \pm y_{1} give four different primitive solutions of (20). This proves equation (24). Finally, to prove equation (25). Suppose x,yx, y are solutions of (20), (x,y)=d(x, y)=d. Then, it must be that d2nd^{2} \mid n, and u=x/d,v=y/du=x / d, v=y / d are
u2+v2=n/d2u^{2}+v^{2}=n / d^{2}

primitive solutions, and different solutions {x,y}\{x, y\} correspond to different solutions {u,v}\{u, v\}. Conversely, let d1d \geqslant 1, d2nd^{2} \mid n. If u,vu, v are a set of primitive solutions of (27), then x=du,y=dvx=d u, y=d v are solutions of (20), and different solutions {u,v}\{u, v\} correspond to different solutions {x,y}\{x, y\}. This proves equation (25). Q.E.D.

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.