Maths Olympiad Prep

Library / /126 of 520

Number theory Difficulty 6.5 National olympiad Find the answer

A positive integer is called oneic if it consists of only 11's. For example, the smallest three oneic numbers are 11, 1111, and 111111. Find the number of 11's in the smallest oneic number that is divisible by 6363.

A number or a short expression. Spacing and $ signs are ignored.

Solution

To solve this problem, we need to find the smallest oneic number (a number consisting only of the digit 1) that is divisible by 63. Since 63 can be factored into 63=7×963 = 7 \times 9, the oneic number must be divisible by both 7 and 9.

1. Divisibility by 9:
A number is divisible by 9 if the sum of its digits is divisible by 9. Since a oneic number consists only of the digit 1, the sum of its digits is equal to the number of digits. Therefore, the number of 1's must be a multiple of 9.

2. Divisibility by 7:
To check for divisibility by 7, we need to consider the properties of oneic numbers modulo 7. Let's denote a oneic number with nn digits as NnN_n. For example, N1=1N_1 = 1, N2=11N_2 = 11, N3=111N_3 = 111, and so on. We can express NnN_n as:
Nn=10n19 N_n = \frac{10^n - 1}{9}
We need NnN_n to be divisible by 7. This means:
10n190(mod7) \frac{10^n - 1}{9} \equiv 0 \pmod{7}
Simplifying, we get:
10n10(mod63) 10^n - 1 \equiv 0 \pmod{63}
This implies:
10n1(mod63) 10^n \equiv 1 \pmod{63}

3. **Finding the smallest nn**:
We need to find the smallest nn such that 10n1(mod63)10^n \equiv 1 \pmod{63}. We can use the order of 10 modulo 63 to find this nn. The order of 10 modulo 63 is the smallest positive integer dd such that 10d1(mod63)10^d \equiv 1 \pmod{63}.

By testing successive powers of 10 modulo 63, we find:
10110(mod63) 10^1 \equiv 10 \pmod{63}
10210037(mod63) 10^2 \equiv 100 \equiv 37 \pmod{63}
10337055(mod63) 10^3 \equiv 370 \equiv 55 \pmod{63}
10455046(mod63) 10^4 \equiv 550 \equiv 46 \pmod{63}
10546019(mod63) 10^5 \equiv 460 \equiv 19 \pmod{63}
1061901(mod63) 10^6 \equiv 190 \equiv 1 \pmod{63}
Therefore, the order of 10 modulo 63 is 6. This means the smallest nn such that 10n1(mod63)10^n \equiv 1 \pmod{63} is 6.

4. Combining the conditions:
Since nn must be a multiple of both 9 (for divisibility by 9) and 6 (for divisibility by 7), the smallest such nn is the least common multiple (LCM) of 9 and 6:
LCM(9,6)=18 \text{LCM}(9, 6) = 18

Therefore, the smallest oneic number that is divisible by 63 has 18 ones.

The final answer is 18\boxed{18}.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.