There exists or not exists a natural number

[VietDao29]

This was one of the problems I encountered when I was in grade 6th. It was quite interesting I think. So I'm posting it here so that you guys can give it a try.
----------------
There exists or not exists a natural number that is just made up by the digit 0, and 1, and that number is divisible by 4122006.
Is there any?

 

[davee123]

This was one of the problems I encountered when I was in grade 6th. It was quite interesting I think. So I'm posting it here so that you guys can give it a try.
----------------
There exists or not exists a natural number that is just made up by the digit 0, and 1, and that number is divisible by 4122006.
Is there any?

I haven't thought of a good proof as to *why*, but it appears that there should exist such a number, although it's likely to be ridiculously high. More than a 110 quadrillion, anyway.

4122006 has prime factors 2, 3, 7, and 98143. Pretty ugly. But it does mean that each number must also be divisible by 42. Going through numbers that consist purely of 0's and 1's AND are divisible by 42 yields LOTS of results. And it appears (at least initially) to not be easily patterned. Other consecutive prime numbers appear as factors-- 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, and 53. I see no reason to doubt that *eventually* all prime factors will be included, hence including 98143, although I haven't looked any higher than 110,000,110,101,000,000.

Other seemingly arbitrary primes such as 4244318333, 988319947, and 165572221 also show up, without apparent pattern, so there seems like there's no limit to including large-sized primes.

From other examinations it would appear as though for any positive integer D, there exists another positive integer N, whose digits are made up of solely 1's and 0's that is evenly divisible by D.

So, I'm going to go with "yes, it exists" although I'd love to hear a 6th-grade -level explanation as to why!

DaveE

 

[Hurkyl]

I consider 0 a natural number, so this is easy.

 

[davee123]

I consider 0 a natural number, so this is easy.

Heh, that was my first thought, so I went back and re-read the exact wording:

a natural number that is just made up by the digit 0, and 1

I took that to mean "must be made up of digits 0 AND 1", so it would have to have at least two decimal places, and contain at least 1 zero and 1 one. Further, since he specified "digit" I assumed that it was required that it be in base 10 rather than in base 2 (which would be similarly simple).

Although admittedly, that makes the specification "natural number" somewhat useless, since it should more specifically state "positive integer". But, since it was specified as a natural number, perhaps he meant "or" instead of "and"? In which case 0 would be totally viable!

DaveE

 

[AKG]

I don't see how "digit" implies base 10. What word is used for other bases? I think its obviously base 10, because the number X = 4122006 is in at least base 7, plus it doesn't say its not in base 10, so the question would just be stupid if the answer didn't need to be in base 10.

We see that a multiple of X cannot end in a 1, and it can only end in a 0 if it is some multiple of 5X. So we've "reduced" the question to whether there exists a number with 0's and 1's which is a multiple of 5X = 20610030. Next, we see that we would need to multiply this by some number k such that 3k = 111 (mod 1000). So k = 37 (mod 1000). So we're looking at (1000m + 37)(20610030) = 762571110 + 20610030000m. Anyone have any insight as to where to go from here? Or perhaps an entirely different approach is best?

 

[VietDao29]

I consider 0 a natural number, so this is easy.

Hmm, yeah, I forgot to add the fact that the number should not be 0. Sorry, my bad.
And it's in base 10 as usual, but however, I think you can do it in any bases since the process is still the same.
You may want to use Dirichlet's box principle in this problem.
Hint, you should consider the following sequence of numbers:
1, 11, 111, 1111, 1111, 111111, ..., 111...111 (4122006 digits "1").
:)

 

[shmoe]

You may want to use Dirichlet's box principle in this problem.
Hint, you should consider the following sequence of numbers:
1, 11, 111, 1111, 1111, 111111, ..., 111...111 (4122006 digits "1").
:)

I don't know that an average grade 6 student would know this?

They almost certainly won't know this: 10^98142=1 mod (2061003) as 2 and 6 divide 98142. Consider (10^98142+10^(2*98142)+...+10^(2061003*98142))*10

 

[Jimmy Snyder]

I don't see how "digit" implies base 10. What word is used for other bases?

Bit is used for base 2, but bit is short for binary digit. This article implies that you are correct:
http://en.wikipedia.org/wiki/Numerical_digit
If bases other than base 10 are allowed, then an answer to the problem is $$10_{4122006}$$

 

[NateTG]

The 'key' step for this is to realize that he remainder of a sum is the sum of the remainders:

By the pigeonhole principle, we know that there are 6 numbers $$e_1...e_6$$ with the properties that the pairwise difference is at least 7, and that $$10^{e_i}$$ always has the same remainder when divided by 412206.

Then
$$1111001 \times 10^{e_1} + 1011001 \times 10^{e_2} + 1000001 \times 10^{e_3} + 1000001 \times 10^{e_4} + 1 \times 10^{e_5} + 1 \times 10^{e_6}$$
is a suitable number.

 

[VietDao29]

Yah, shmoe, and NateTG got it correct.
--------------------
Here's another approach. The one that I was taught.
Consider the sequence:
1, 11, 111, 1111, 11111, ..., 1111...1111 (4122006 digits "1").
If in that sequence, there exists a number that is divisible by 4122006, then it's done.
But if there does not exist such number then by the pigeonhole principle, there must be at least 2 numbers that have the same remainder when divided by 4122006.
Then just by subtracting the smaller number from the greater number, we'll have the desired number (i.e it's divisible by 4122006, and is made of only "0", and "1"). It will have the form: 11...1100...000.
So, in conclusion, there exists such number that's made up fom "0", and "1", and is divisible 4122006.
:)
--------------------
This can also be generated into a more general problem:
There exists or not exists a natural number that is just made up by the digit 0, and 1, and that number is divisible by x (x is a narural number, not 0).