Maths Olympiad Prep

Library / /25 of 63

Number theory Difficulty 6.5 National olympiad Prove it Japan

Find all the factors kk of 102013110^{2013} - 1, which satisfy 1k1001 \le k \le 100.

Solution

1, 3, 9, 27, 37, 67
Let us use the following notations in the subsequent argument to obtain the solution to this problem:
* For a pair of positive integers (a,b)(a, b), denote by gcd(a,b)\gcd(a, b) the greatest common divisor of aa and bb.
* For integers a,ba, b and pp, we write ab(modp)a \equiv b \pmod p to mean that aba - b is a multiple of pp.
We also quote, without proof, the following well-known facts:
* When an1(modp)a^n \equiv 1 \pmod p holds for positive integers a,n,pa, n, p, the following statement holds for a positive integer mm:
am1(modp)    agcd(m,n)1(modp). a^m \equiv 1 \pmod p \iff a^{\gcd(m,n)} \equiv 1 \pmod p.
* If pp is a prime, and an integer aa is not a multiple of pp, then
ap11(modp) a^{p-1} \equiv 1 \pmod p
holds (Fermat's Little Theorem).
Starting the search for the positive factors of 102013110^{2013} - 1 less than or equal to 100, let us first determine the prime numbers pp less than 100, which are factors of 102013110^{2013} - 1. From what we stated above it follows that we have
10201310(modp)    1020131(modp)    10d1(modp),10^{2013} - 1 \equiv 0 \pmod p \iff 10^{2013} \equiv 1 \pmod p \iff 10^d \equiv 1 \pmod p,
where d=gcd(2013,p1)d = \gcd(2013, p-1). Then, we see that dd is a factor of 2013=311612013 = 3 \cdot 11 \cdot 61 and must satisfy dp1<99d \le p-1 < 99. Therefore, we conclude that d{1,3,11,33,61}d \in \{1, 3, 11, 33, 61\} must be satisfied. Let us go through the search for pp case by case depending on the possible value of dd.
(1) When d=1d=1: in this case, we see that p=3p=3 is the only prime which satisfies 1011(modp)10^1 \equiv 1 \pmod p, and it satisfies gcd(2013,p1)=1\gcd(2013, p-1) = 1 as well.
(2) When d=3d=3: in this case, we have 1031=333710^3 - 1 = 3^3 \cdot 37. So, p=3,37p=3, 37 are the only primes satisfying 1031(modp)10^3 \equiv 1 \pmod p. Of these two primes, 37 is the only one satisfying gcd(2013,p1)=3\gcd(2013, p-1) = 3.
(3) When d=11d=11: in this case, p=23,89p=23, 89 are the only primes less than 100 satisfying the condition gcd(2013,p1)=11\gcd(2013, p-1) = 11. For each of these two primes pp, let us check whether it satisfies the condition 10111(modp)10^{11} \equiv 1 \pmod p. Let p=23p=23, then since we have
1051021021088104(mod23), 10^5 \equiv 10^2 \cdot 10^2 \cdot 10 \equiv 8 \cdot 8 \cdot 10 \equiv -4 \pmod{23},
from which it follows that
101110510510(4)(4)101(mod23). 10^{11} \equiv 10^5 \cdot 10^5 \cdot 10 \equiv (-4) \cdot (-4) \cdot 10 \equiv -1 \pmod{23}.
Therefore, 1011110^{11} \equiv 1 is not satisfied.
If p=89p=89, then from
1051021021011111036(mod89) 10^5 \equiv 10^2 \cdot 10^2 \cdot 10 \equiv 11 \cdot 11 \cdot 10 \equiv -36 \pmod{89}
it follows that
101110510510(36)(36)1055(mod89). 10^{11} \equiv 10^5 \cdot 10^5 \cdot 10 \equiv (-36) \cdot (-36) \cdot 10 \equiv 55 \pmod{89}.
Therefore, 10111(mod89)10^{11} \equiv 1 \pmod{89} is not satisfied.
Consequently, there are no prime factors less than 100 for 102013110^{2013} - 1 for the case d=11d=11.
(4) When d=33d=33: in this case, we see that 67 is the only prime less than 100 satisfying the condition gcd(2013,p1)=33\gcd(2013, p-1) = 33. Let us check whether 10331(mod67)10^{33} \equiv 1 \pmod{67}. By repeating to take squares, we get
10233,10417,10821,101639,103247(mod67), 10^2 \equiv 33, \quad 10^4 \equiv 17, \quad 10^8 \equiv 21, \quad 10^{16} \equiv 39, \quad 10^{32} \equiv 47 \pmod{67},
and by multiplying further by 10, we obtain 10331(mod67)10^{33} \equiv 1 \pmod{67}. Thus, we get p=67p=67 is the prime factor of 102103110^{2103}-1 corresponding to the case d=33d=33.
(5) When d=61d=61: in this case, we see that there is no prime pp less than 100 satisfying the condition gcd(2013,p1)=61\text{gcd}(2013, p-1) = 61.
Thus we conclude that only prime factors of 102013110^{2013}-1 less than 100 are 3, 37, 67, and since any positive factor of 102013110^{2013}-1 less than or equal to 100 cannot have any other prime factors, we see that only possible positive factors of 102013110^{2013}-1 must come from
1, 3, 9, 27, 37, 67, 81.
We already checked that 3, 37, 67 all divide 102013110^{2013}-1 and 1 is obviously a factor. So, it is enough to check whether any of 9, 27, 81 divides 102013110^{2013}-1. Since we have
1020131=(101)(102012+102011++101+1) 10^{2013}-1 = (10-1)(10^{2012} + 10^{2011} + \cdots + 10^1 + 1)
and
102012+102011++101+112012+12011++11+120136(mod9),10^{2012} + 10^{2011} + \cdots + 10^1 + 1 \equiv 1^{2012} + 1^{2011} + \cdots + 1^1 + 1 \equiv 2013 \equiv 6 \pmod{9},
we get 102013154(mod81)10^{2013}-1 \equiv 54 \pmod{81}. From this we conclude that both 9 and 27 are factors of 102013110^{2013}-1, while 81 is not, and we get 1, 3, 9, 27, 37, 67 for the answer to the problem.

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.