Maths Olympiad Prep

Library / /1 of 3

Number theory Difficulty 5.5 AIME, harder Prove it North Macedonia

Find all natural numbers nn for which each natural number having n1n-1 digits '1' and one digit '7' in its decimal representation is prime.

Solution

A number BB having n1n-1 digits '1' and one digit '7' in decimal representation is of the form B=An+610kB = A_n + 6 \cdot 10^k where AnA_n is a number having nn digits '1', and 0k<n0 \le k < n. Notice that if 3n3|n then the sum of the digits of BB is 3n+63n+6. Notice that
A1=1, A2=4, A3=6, A4=5, A5=2, A6=0(mod7) A_1 = 1,\ A_2 = 4,\ A_3 = 6,\ A_4 = 5,\ A_5 = 2,\ A_6 = 0 \pmod{7}
100=1; 101=3; 102=2; 103=6; 104=4; 105=5; 106=1(mod7) 10^0 = 1;\ 10^1 = 3;\ 10^2 = 2;\ 10^3 = 6;\ 10^4 = 4;\ 10^5 = 5;\ 10^6 = 1 \pmod{7}
Let n>6n > 6. Then n=6t+rn = 6t + r where t0t \ge 0, 1r61 \le r \le 6. Then
An=A6t+r=A6t+Ar106tA6t+ArAr(mod7) A_n = A_{6t+r} = A_{6t} + A_r \cdot 10^{6t} \equiv A_{6t} + A_r \equiv A_r \pmod{7}
If 6n6|n then 3n3|n, so therefore we saw that BB is not prime in any case. Suppose 66 does not divide nn. Then we saw that AnAr(mod7)A_n \equiv A_r \pmod{7} and additionally ArA_r is not congruent to 00 modulo 77. Put Art(mod7)A_r \equiv t \pmod{7}. For this tt, from the above it follows that we can choose kk, 0k50 \le k \le 5, such that 610k=10kt(mod7)6 \cdot 10^k = -10^k \equiv -t \pmod{7}. So this BB is divisible by 77. For n=6n=6 we saw that the numbers are composite. We need to check all cases n5n \le 5. For n=5n=5
A5+6102=22=0(mod7) A_5 + 6 \cdot 10^2 = 2 - 2 = 0 \pmod{7}
For n=4n=4, 1711=29591711 = 29 \cdot 59. In the case n=3n=3 we already saw that all numbers are composite. For n=2n=2 and n=1n=1 all numbers are prime.

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.