For positive integer a≥2, denote Na as the number of positive integer k with the following property: the sum of squares of digits of k in base a representation equals k. Prove that: a.) Na is odd; b.) For every positive integer M, there exist a positive integer a≥2 such that Na≥M.
Problem
Source: China TST 2000, problem 3
Tags: number theory unsolved, number theory
24.05.2005 07:18
We have that: k=∑btat=∑b2t we also have: btat>(a−1)2+b2t for t>1, so we get that a good k has at most 2 digits in base a. So we have: case 1: b2a+b1=b22+b21 Now for a pair b2,b1, we verify that a−b2,b1 also works, and also when b2=a/2 we get: (2b1−1)2=a2+1 wich gives a=0, contradiction. so there is an even number of solutions in this case. case 2: b1=b21 wich gives k=1 So Na is odd. Now finally we show case 1 has as many solutions as we would like for some a. Pick an even a such that a2+1 has at least t prime factors all of them =1 mod 4. Then, a2+1 can be expressed as a sum of two squares in at least 2t ways. Since b2=a/2+−√a2−4b21+4b/2, iff a2+1=c2+d2 with c odd, put 2b1−1=c and b2=a/2+−d/2 So we get Na>2t+1, because every c and d give different values for b1 and b2
26.08.2019 04:07
Here's a different way to do (b). (b) First of all, notice that if a=(x2+1)z+x for any z,x∈N, then x(xz+1)⋅a+(xz+1) satisfies the property in the question. In otherwords, we have that [x(xz+1)]2+(xz+1)2=x(xz+1)⋅a+(xz+1) is satisfied. This implies that if we let f(a) for a∈N be the number of integers k such that a>k2+1 and k2+1|a−k, then Na≥f(a). Finally, by the Chinese Remainder Theorem, if we select some positive integer n such that n≡2k (mod 22k+1) for each 1≤k≤M and n>22M+1, we are done. ◻