Maths Olympiad Prep

Library / /106 of 299

Number theory Difficulty 6.2 National Olympiad Prove it Iran

b1<b2<b_1 < b_2 < \dots is the sequence of all natural numbers that can be written as the sum of squares of two natural numbers. Prove that for infinitely many natural numbers nn, bn+1bn=2015b_{n+1} - b_n = 2015.

Solution

We prove that for any odd integer m>0m > 0, there are infinitely many positive integers nn, such that bn+1bn=mb_{n+1} - b_n = m. For sake of this reason we will use the following lemma.

Lemma 1. Let aa be a positive integer which is not a perfect square. There exist infinitely many primes p3(mod4)p \equiv 3 \pmod{4} such that aa is quadratic non-residue modulo them.

Proof. Let p1p2psp_1p_2\cdots p_s be the square free part of integer aa, where pip_i's are distinct primes. Now choose the quadratic non-residue r1r_1 modulo p1p_1 and set r2,,rsr_2, \dots, r_s as quadratic residues modulo p2,,psp_2, \dots, p_s, respectively. Now by Chinese Remainder Theorem and Dirichlet's Theorem one can find infinitely many primes pp satisfying
pri(modpi)for i=1,2,,s p \equiv r_i \pmod{p_i} \quad \text{for } i = 1, 2, \dots, s
Note that if one of the primes named p1p_1 is equal to 22, then omit the first congruence and just add the criterion p3(mod8)p \equiv 3 \pmod{8} and we are done. \square

Now set m=2M+1m = 2M + 1 and consider the sequence k2+M2,k2+M2+1,,k2+M2+2M+1k^2 + M^2, k^2 + M^2 + 1, \dots, k^2 + M^2 + 2M + 1. In this sequence the first and the last term are represented as sum of two squares. We will prove that there are infinitely many integers kk such that only these two terms could be representable as sum of two squares. According to the lemma, there exist primes p1,p2,,p2M3(mod4)p_1, p_2, \dots, p_{2M} \equiv 3 \pmod{4} such that for each jj, M2+jM^2 + j is quadratic non-residue modulo pjp_j. Now we establish the following lemma.

Lemma 2. Let rr be a quadratic residue modulo prime PP and (x,P)=1(x, P) = 1. Then there is integer xx such that 0<x<2P0 < x < 2P, x2r(modP)x^2 \equiv r \pmod{P} and x2≢r(modP2)x^2 \not\equiv r \pmod{P^2}.

Proof. Let us note that (x+P)2x2=P2+2xP≢0(modP2)(x + P)^2 - x^2 = P^2 + 2xP \not\equiv 0 \pmod{P^2}. Then one of xx and x+Px + P satisfies the desired conditions. \square

Now by this lemma there exist positive integers n1,n2,,n2Mn_1, n_2, \dots, n_{2M} such that 0<nj<2pj0 < n_j < 2p_j (1j2M1 \le j \le 2M) and we have
nj2(M2+j)(modpj),x2≢(M2+j)(modpj2) n_j^2 \equiv -(M^2 + j) \pmod{p_j}, \quad x^2 \not\equiv -(M^2 + j) \pmod{p_j^2}
Next, let knj(modpj2)k \equiv n_j \pmod{p_j^2} for 1j2M1 \le j \le 2M. Then, the numbers k2+M2+jk^2 + M^2 + j are all divisible by pjp_j and not pj2p_j^2. Now, since pj3(mod4)p_j \equiv 3 \pmod{4}, k2+M2+jk^2 + M^2 + j cannot be written as sum of two squares. So we are done.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.