Number theory - prove if divisible by 2009

In summary, the conversation discusses how to prove the existence of an integer that only contains 0s and 1s in its decimal notation and is divisible by 2009. The suggested solution involves using the Dirichlet's box principle and considering numbers of the form 1, 11, 111, 1111, etc. Eventually, two numbers in this sequence will be equal modulo 2009, and the difference between them will be the desired integer.
  • #1
DianaSagita
11
0

Homework Statement



Prove if there exists an integer whose decimal notation contains only 0s and 1s, and which is divisible by 2009.


Homework Equations



Dirichlet's box principle :confused:

The Attempt at a Solution



I'm new to number theory, and I'm aware that I do not have the proper reasoning for this, but tried:
10^n + a[n-1]*10^(n-1) + ... + a[0] = k* (2*10^3 + 9), where a={0,1}

tried to find k with the max power of 10^(n-1), but it seems my approach is wrong... :( please help
Thanks in advance!
 
Physics news on Phys.org
  • #2
Consider numbers of the form 1, 11, 111, 1111, ... According to the box principle at some point two members of this sequence will be equal modulo 2009. In that case subtract the smaller from the larger and you should get your integer.
 
  • #3
Thank you, rasmhop! I understand now how to get it, your reply was helpful, cheers!
 

FAQ: Number theory - prove if divisible by 2009

How can I prove if a number is divisible by 2009?

To prove if a number is divisible by 2009, you can use the divisibility rule of 2009. This rule states that if the sum of the digits of a number is divisible by 2009, then the number itself is also divisible by 2009.

Can I use prime factorization to prove divisibility by 2009?

Yes, you can use prime factorization to prove divisibility by 2009. 2009 can be written as 7^2 * 41, so if a number's prime factorization includes 7^2 and 41, then it is divisible by 2009.

How do I prove that a large number is divisible by 2009?

To prove that a large number is divisible by 2009, you can use the repeated division method. Divide the number by 2009 until you get a whole number. If the final result is a whole number, then the original number is divisible by 2009.

Can I use modular arithmetic to prove divisibility by 2009?

Yes, you can use modular arithmetic to prove divisibility by 2009. The remainder when a number is divided by 2009 can tell you if the number is divisible by 2009 or not. If the remainder is 0, then the number is divisible by 2009.

Is there a shortcut to prove if a number is divisible by 2009?

Yes, there is a shortcut to prove if a number is divisible by 2009. You can check if the last four digits of the number are divisible by 2009. If they are, then the whole number is also divisible by 2009.

Similar threads

Show that decimal number expansion is finite
Replies
7
Views
1K
Proving the Existence of a Number with n Divisors
Replies
18
Views
2K
Proof of an inequality with natural numbers
Replies
3
Views
1K
Proof: Divisibility of Integers by 4
Replies
5
Views
1K
Prove True/False that n^3-n is Always Divisible By 6
Replies
4
Views
2K
Number theory problem divisible
Replies
2
Views
2K
Prime factors of odd composites
Replies
6
Views
1K
Number Theory: Unclear Explanation of Divisibility Question
Replies
1
Views
1K
I On base-b expansion of nonnegative reals
Replies
7
Views
544
Verify that ## N-M ## is divisible by ## 9 ##
Replies
7
Views
2K

Hot Threads

Recent Insights

Back
Top