What is the smallest positive integer that only comprises of the digits 0 and 1, and is a multiple of 42?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
I believe that to find the minimum in the general case, we essentially have to do trial and error to get the answer.
The standard pigeonhole argument tells us that such a value must exist. However, it is not immediately clear how one can effectively find this minimum value, especially when dividing by composite numbers.
Note: For primes p ≥ 7 , the number 1 1 1 … 1 with (p-1) 1's work. However, since p − 1 is composite, we can nicely factor it into the product of two "binary" numbers, so this isn't the minimum. E.g. with p = 7 , we know that 7 ∣ 1 1 1 1 1 1 . As it turns out, the minimum is 1 0 1 0 1 0 .
Then answer should be 1 0 + 1 0 4 = 10010
Although I did not understand completely why the answer turned out to be 101010, I took a hint from the title. I just converted 42 into binary and got the answer right! Please can anyone explain why it actually happened? Meanwhile, I will make a few attempts to understand it myself.😇
It is not happening for other numbers.I tried 3 7 , 3 0 , 3 6 .
I think it is just a coincidence.
Log in to reply
It is indeed a coincidence. Now find the "proper" solution.
Nor is the property existing in other bases. Like I checked for base 3,4,....,9. Kind of a great coincidence!
Problem Loading...
Note Loading...
Set Loading...
The answer, x , must be divisible by 3, 2, and 7. Since it is divisible by 2, the last digit must be 0. Since it is divisible by 3, the sum of digits (i.e. the number of 1's) must be a multiple of 3. To minimize the answer, let the sum of digits be 3. Next, notice that
1 0 ≡ 3 ( m o d 7 ) 1 0 2 ≡ 2 ( m o d 7 ) 1 0 3 ≡ 6 ( m o d 7 ) 1 0 4 ≡ 4 ( m o d 7 ) 1 0 5 ≡ 5 ( m o d 7 )
Let us assume that the number of digits is at most 6. Then, the only way to make x ≡ 0 ( m o d 7 ) is by setting x ≡ 3 + 6 + 5 ≡ 1 4 ≡ 0 ( m o d 7 ) . Therefore, x has '1' at the tens, thousands, and hundred thousands places.
∴ x = 1 0 1 0 1 0