Japan Mathematical Olympiad

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)$, denote by $\gcd (a,b)$ the greatest common divisor of $a$ and $b$. For integers $a,b$ and $p$, we write $a\equiv b(\mathrm{mod}p)$ to mean that $a-b$ is a multiple of $p$. We also quote, without proof, the following well-known facts: When $a^n\equiv 1(\mathrm{mod}p)$ holds for positive integers $a,n,p$, the following statement holds for a positive integer $m$: $$a^m\equiv 1(\mathrm{mod}p)⟺a^{\gcd (m,n)}\equiv 1(\mathrm{mod}p).$$ If $p$ is a prime, and an integer $a$ is not a multiple of $p$, then $$a^{p-1}\equiv 1(\mathrm{mod}p)$$ holds (Fermat's Little Theorem). Starting the search for the positive factors of $10^{2013}-1$ less than or equal to 100, let us first determine the prime numbers $p$ less than 100, which are factors of $10^{2013}-1$. From what we stated above it follows that we have $$10^{2013}-1\equiv 0(\mathrm{mod}p)⟺10^{2013}\equiv 1(\mathrm{mod}p)⟺10^d\equiv 1(\mathrm{mod}p),$$ where $d=\gcd (2013,p-1)$. Then, we see that $d$ is a factor of $2013=3\cdot 11\cdot 61$ and must satisfy $d\le p-1<99$. Therefore, we conclude that $d\in \{1,3,11,33,61\}$ must be satisfied. Let us go through the search for $p$ case by case depending on the possible value of $d$. (1) When $d=1$: in this case, we see that $p=3$ is the only prime which satisfies $10^1\equiv 1(\mathrm{mod}p)$, and it satisfies $\gcd (2013,p-1)=1$ as well. (2) When $d=3$: in this case, we have $10^3-1=3^3\cdot 37$. So, $p=3,37$ are the only primes satisfying $10^3\equiv 1(\mathrm{mod}p)$. Of these two primes, 37 is the only one satisfying $\gcd (2013,p-1)=3$. (3) When $d=11$: in this case, $p=23,89$ are the only primes less than 100 satisfying the condition $\gcd (2013,p-1)=11$. For each of these two primes $p$, let us check whether it satisfies the condition $10^{11}\equiv 1(\mathrm{mod}p)$. Let $p=23$, then since we have $$10^5\equiv 10^2\cdot 10^2\cdot 10\equiv 8\cdot 8\cdot 10\equiv -4(\mathrm{mod}23),$$ from which it follows that $$10^{11}\equiv 10^5\cdot 10^5\cdot 10\equiv (-4)\cdot (-4)\cdot 10\equiv -1(\mathrm{mod}23).$$ Therefore, $10^{11}\equiv 1$ is not satisfied. If $p=89$, then from $$10^5\equiv 10^2\cdot 10^2\cdot 10\equiv 11\cdot 11\cdot 10\equiv -36(\mathrm{mod}89)$$ it follows that $$10^{11}\equiv 10^5\cdot 10^5\cdot 10\equiv (-36)\cdot (-36)\cdot 10\equiv 55(\mathrm{mod}89).$$ Therefore, $10^{11}\equiv 1(\mathrm{mod}89)$ is not satisfied. Consequently, there are no prime factors less than 100 for $10^{2013}-1$ for the case $d=11$. (4) When $d=33$: in this case, we see that 67 is the only prime less than 100 satisfying the condition $\gcd (2013,p-1)=33$. Let us check whether $10^{33}\equiv 1(\mathrm{mod}67)$. By repeating to take squares, we get $$10^2\equiv 33,10^4\equiv 17,10^8\equiv 21,10^{16}\equiv 39,10^{32}\equiv 47(\mathrm{mod}67),$$ and by multiplying further by 10, we obtain $10^{33}\equiv 1(\mathrm{mod}67)$. Thus, we get $p=67$ is the prime factor of $10^{2103}-1$ corresponding to the case $d=33$. (5) When $d=61$: in this case, we see that there is no prime $p$ less than 100 satisfying the condition $\text{gcd}(2013,p-1)=61$. Thus we conclude that only prime factors of $10^{2013}-1$ less than 100 are 3, 37, 67, and since any positive factor of $10^{2013}-1$ less than or equal to 100 cannot have any other prime factors, we see that only possible positive factors of $10^{2013}-1$ must come from 1, 3, 9, 27, 37, 67, 81. We already checked that 3, 37, 67 all divide $10^{2013}-1$ and 1 is obviously a factor. So, it is enough to check whether any of 9, 27, 81 divides $10^{2013}-1$. Since we have $$10^{2013}-1=(10-1)(10^{2012}+10^{2011}+\cdots +10^1+1)$$ and $$10^{2012}+10^{2011}+\cdots +10^1+1\equiv 1^{2012}+1^{2011}+\cdots +1^1+1\equiv 2013\equiv 6(\mathrm{mod}9),$$ we get $10^{2013}-1\equiv 54(\mathrm{mod}81)$. From this we conclude that both 9 and 27 are factors of $10^{2013}-1$, while 81 is not, and we get 1, 3, 9, 27, 37, 67 for the answer to the problem.