Number theoryDifficulty 7.0National Olympiad, round 2Prove itJBMO
Problem: A positive integer is called a repunit, if it is written only by ones. The repunit with n digits will be denoted by n11…1. Prove that:
a) the repunit n11…1 is divisible by 37 if and only if n is divisible by 3 ;
b) there exists a positive integer k such that the repunit n11…1 is divisible by 41 if and only if n is divisible by k.
Solution
Solution:
a) Let n=3m+r, where m and r are non-negative integers and r<3. Denote by p00…0 a recording with p zeroes and pabcabc…abc a recording with p times abc. We have: n11…1=3m+r11…1=3m11…1⋅r00…0+r11…1=111⋅m−1100100…100+r11…1. Since 111=37⋅3, the numbers n11…1 and r11…1 are equal modulo 37. On the other hand, the numbers 1 and 11 are not divisible by 37. We conclude that n11…1 is divisible by 37 if and only if r=0, i.e., if and only if n 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=41⋅271. Since 11111 is a repunit with 5 digits, it follows in the same way as in a) that n11…1 is divisible by 41 if and only if n 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.