Competition problem — Number theory

Library / /44 of 101

Number theory Difficulty 6.0 AIME, harder Prove it Estonia

a. Does there exist a positive integer $n$ such that the eight last digits of the number $n^2 + 1$ are the same as in the number $2n$ , but the ninth digit from the end of these two numbers are different?

b. Does there exist a positive integer $n$ such that the nine last digits of the number $n^2 + 1$ are the same as in the number $2n$ , but the tenth digit from the end of these two numbers are different?

Solution

The condition that the last $k$ digits of two numbers are the same is fulfilled if and only if the difference of these two numbers ends with exactly $k$ zeroes. Note that $n^2 + 1 - 2n = (n-1)^2$ .

a. Let $n = 100010001$ , then the number $n-1$ ends with 4 zeroes and the fifth digit from the end is 1. Hence the number $(n-1)^2$ ends with 8 zeroes and the ninth digit from the end is 1. Hence this $n$ fits.

b. If a number ends with exactly $k$ zeroes, then the square of this number ends with exactly $2k$ zeroes. Hence $(n-1)^2$ cannot end with exactly 9 zeroes, since 9 is odd, and so there are no such integers $n$ that would fulfill the condition.

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 and solution reproduced as published; topic and difficulty added by this site.