Maths Olympiad Prep

Library / /11 of 18

Number theory Difficulty 7.0 National olympiad Prove it Argentina

Magalí's calculator has a special button ⋆ that works as follows. Every time she presses ⋆, the calculator multiplies the number on the screen by itself, then adds 6, and finally shows the result on the screen. For example, if the number on the screen is 1111 and Magalí presses ⋆, the number that will appear on the screen is 11×11+6=12711 \times 11 + 6 = 127. Magalí chooses a prime number, writes it on the calculator, and presses the ⋆ button many times. The ⋆ button gets blocked when a number that is not prime appears on the screen. What is the greatest number of times that she can press the ⋆ button?

Solution

The answer is 3. First, notice that the last digit of Magalí's initial number, name it n1n_1, determines the last digit of the following numbers. This is explained in the following table, where we name n2=n12+6n_2 = n_1^2 + 6, n3=n22+6n_3 = n_2^2 + 6, n4=n32+6n_4 = n_3^2 + 6 and n5=n42+6n_5 = n_4^2 + 6:

n1n_1n2n_2n3n_3n4n_4n5n_5
175blocked ⋆blocked ⋆
20blocked ⋆blocked ⋆blocked ⋆
35blocked ⋆blocked ⋆blocked ⋆
5175blocked ⋆
75blocked ⋆blocked ⋆blocked ⋆
975blocked ⋆blocked ⋆

For example, if n1n_1 had 4 as its last digit, then n2=n12+6n_2 = n_1^2 + 6 would have the same last digit as 4×4+6=224 \times 4 + 6 = 22, which is 2. We omitted the numbers with their last digit being even but different from 2 because they cannot be prime. Now, observe on the table that no matter which prime number Magalí chooses initially, in at most three steps she reaches a number with last digit 0 or 5, and so a multiple of 5. Since this number is greater than 5, it is not a prime number. Therefore, she can never press the ⋆ button more than three times. It is possible that Magalí presses ⋆ three times. Indeed, if she starts with n1=5n_1 = 5, the following numbers are n2=52+6=31n_2 = 5^2 + 6 = 31, n3=312+6=967n_3 = 31^2 + 6 = 967 and n4=9672+6n_4 = 967^2 + 6. Since 5, 31 and 967 are prime numbers and 9672+6967^2 + 6 is a multiple of 5, this proves the desired result.

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.