Maths Olympiad Prep

Library / /96 of 105

Number theory Difficulty 7.0 National Olympiad, round 2 Prove it JBMO

Problem:
A positive integer is called a repunit, if it is written only by ones. The repunit with nn digits will be denoted by 111n\underbrace{11 \ldots 1}_{n}. Prove that:

a) the repunit 111n\underbrace{11 \ldots 1}_{n} is divisible by 37 if and only if nn is divisible by 3 ;

b) there exists a positive integer kk such that the repunit 111n\underbrace{11 \ldots 1}_{n} is divisible by 41 if and only if nn is divisible by kk.

Solution

Solution:

a) Let n=3m+rn = 3m + r, where mm and rr are non-negative integers and r<3r < 3.
Denote by 000p\underbrace{00 \ldots 0}_{p} a recording with pp zeroes and abcabcabcp\underbrace{abcabc \ldots abc}_{p} a recording with pp times abcabc. We have:
111n=1113m+r=1113m000r+111r=111100100100m1+111r. \underbrace{11 \ldots 1}_{n} = \underbrace{11 \ldots 1}_{3m + r} = \underbrace{11 \ldots 1}_{3m} \cdot \underbrace{00 \ldots 0}_{r} + \underbrace{11 \ldots 1}_{r} = 111 \cdot \underbrace{100100 \ldots 100}_{m-1} + \underbrace{11 \ldots 1}_{r}.
Since 111=373111 = 37 \cdot 3, the numbers 111n\underbrace{11 \ldots 1}_{n} and 111r\underbrace{11 \ldots 1}_{r} are equal modulo 37. On the other hand, the numbers 1 and 11 are not divisible by 37. We conclude that 111n\underbrace{11 \ldots 1}_{n} is divisible by 37 if and only if r=0r = 0, i.e., if and only if nn is divisible by 3.

b) Using the idea from a), we look for a repunit which is divisible by 41. Obviously, 1 and 11 are not divisible by 41, while the residues of 111 and 1111 are 29 and 4, respectively. We have 11111=4127111111 = 41 \cdot 271. Since 11111 is a repunit with 5 digits, it follows in the same way as in a) that 111n\underbrace{11 \ldots 1}_{n} is divisible by 41 if and only if nn is divisible by 5.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.