There exists or not exists a natural number

  • Context: High School 
  • Thread starter Thread starter VietDao29
  • Start date Start date
  • Tags Tags
    Natural
Click For Summary

Discussion Overview

The discussion revolves around the existence of a natural number composed solely of the digits 0 and 1 that is divisible by 4122006. Participants explore this problem from various angles, including mathematical reasoning and potential proofs, while considering the implications of definitions and number bases.

Discussion Character

  • Exploratory
  • Mathematical reasoning
  • Debate/contested

Main Points Raised

  • Some participants propose that there exists such a number, suggesting that while it may be very large, it is theoretically possible.
  • One participant notes that 4122006 has prime factors including 2, 3, 7, and 98143, which implies that any number made up of 0's and 1's must also be divisible by 42.
  • Another participant argues that the requirement for the number to be made of digits 0 and 1 implies it must contain at least one of each digit, leading to a discussion about the definition of natural numbers and whether 0 should be included.
  • Some participants challenge the assumption that "digit" implies base 10, suggesting that other bases could be considered, and referencing the term "bit" for base 2.
  • A later reply introduces the pigeonhole principle as a method to approach the problem, suggesting that if a sequence of numbers made up of 1's does not yield a divisible number, then two numbers must share a remainder when divided by 4122006.
  • Another participant mentions using Dirichlet's box principle and provides a sequence of numbers to consider in the context of the problem.
  • One participant presents a specific construction of a number using a combination of 1's and 0's that would be divisible by 4122006, although the validity of this construction is not universally accepted.

Areas of Agreement / Disagreement

Participants express differing views on the definitions of natural numbers and the implications of the problem's requirements. While some lean towards the existence of such a number, others raise questions about the assumptions made, leading to an unresolved discussion with multiple competing perspectives.

Contextual Notes

Participants note limitations in definitions, assumptions about number bases, and the complexity of the problem, which may affect the conclusions drawn. The discussion remains open-ended regarding the existence of the number in question.

VietDao29
Homework Helper
Messages
1,424
Reaction score
3
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? :rolleyes:
 
Last edited:
Mathematics news on Phys.org
VietDao29 said:
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? :rolleyes:

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
 
I consider 0 a natural number, so this is easy. :smile:
 
Hurkyl said:
I consider 0 a natural number, so this is easy. :smile:

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
 
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?
 
Hurkyl said:
I consider 0 a natural number, so this is easy. :smile:
Hmm, yeah, I forgot to add the fact that the number should not be 0. :smile: 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").
:)
 
VietDao29 said:
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
 
AKG said:
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 [tex]10_{4122006}[/tex]
 
Last edited:
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 [tex]e_1...e_6[/tex] with the properties that the pairwise difference is at least 7, and that [tex]10^{e_i}[/tex] always has the same remainder when divided by 412206.

Then
[tex]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}[/tex]
is a suitable number.
 
  • #10
Yah, shmoe, and NateTG got it correct. :smile:
--------------------
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).
 
Last edited:

Similar threads

High School Cool fact about number of digits in n!
  • · Replies 3 ·
Replies
3
Views
2K
MHB Finding Even Natural Numbers w/ No Repetition: 0-5 & 6
  • · Replies 1 ·
Replies
1
Views
1K
Graduate About a natural extension of Collatz conjecture
  • · Replies 3 ·
Replies
3
Views
1K
Undergrad What is the role of geometry and dimensional operations?
  • · Replies 3 ·
Replies
3
Views
2K
MHB Recreational Number Theory, Unsolved Problem
  • · Replies 1 ·
Replies
1
Views
2K
High School Confused about ciphers in the book 'Arithmetic for the Practical Man'
  • · Replies 13 ·
Replies
13
Views
3K
Undergrad Comparing ##a^b## and ##b^a##
  • · Replies 19 ·
Replies
19
Views
2K
High School How to pick some numbers out of 13 integers, by a 4 digits code
  • · Replies 4 ·
Replies
4
Views
2K
High School Is Each Stage of Pascal's Triangle Special?
  • · Replies 11 ·
Replies
11
Views
2K
Largest Number Game - Start at 1!
  • · Replies 43 ·
2
Replies
43
Views
6K