Prove that for every positive integer k, we can find such a positive integer n

[murshid_islam]

i want to prove that for every positive integer k, we can find such a positive integer n, such that k divides n and n is only composed of the digits 0 and 3. i don't have any idea how to approach this problem. any help will be appreciated.

thanks in advance.

 

[jing]

Try the numbers below 10 to begin with.

 

[uart]

Try the numbers below 10 to begin with.

Well, as it turns out it can be verified for all the numbers 1..9, but what does that prove?

1*3 = 3
2*15 = 30
3*10 = 30
4*75 = 300
5*6 = 30
6*5 = 30
7*429 = 3003
8*375 = 3000
9*37 = 333

 

[uart]

--Ignore--

 

[murshid_islam]

Try the numbers below 10 to begin with.

but how does that help in proving it for every positive integer k?

 

[jing]

Have you seen any patterns or processes that might be useful?

If not extend up to 20 or 30

 

[murshid_islam]

maybe I'm incredibly stupid but i still don't see any pattern.

 

[AlephZero]

Start with the case when k is a prime number (and not equal to 2 3 or 5).

Think about the remainders when 3, 30, 300, 3000 ... are divided by k.

 

[murshid_islam]

Have you seen any patterns or processes that might be useful?

If not extend up to 20 or 30

i tried upto 20. but still i can't see any pattern.
10*3 = 30
11*3 = 33
12*25 = 300
13*231 = 3003
14*2145 = 30030
15*2 = 30
16*1875 = 30000
17*19590 = 333030
18*185 = 3330
19*1737 = 33003
20*15 = 300

can anybody please tell me how to prove it for every positive integer k?

 

[jing]

How did you get these results?
Have you checked them out with what alephzero said?

 

[murshid_islam]

How did you get these results?
Have you checked them out with what alephzero said?

yeah i did. but i am still in the dark.

 

[AlephZero]

Actually my comment about k being a prime turned out to be irrelevant, after a bit more thought.

Consider the sequence 3, 30, 300 ... 3*10^n ... mod k.

There are a finite number of different values of the sequence.

So working through the terms in order, after searching a finite number of terms either we find a term = 0, or we find two different terms with the same nonzero value, r say.

If we find a zero term, we have a value of n. In the other case,

there exist integers a, b such that a < b and 3*10^a = 3*10^b = r mod k

Clearly q = 10^(b-a) = 1 mod k

Now construct a number n such that n = 0 mod k, using a and q. Hint: one such number contains k 3's.

 

[jing]

Sorry AlephZero, don't think this works for all k, but the method is worth pursuing

k = 22

3*10^1 = 8 mod 22
3*10^3 = 8 mod 22

q=10^(3-1) = 10^2 = 12 mod 22

3 = 7*0 +3 <<<<<<
30 = 7*4 + 2
300 = 7*42 + 6
3000 = 7*428 + 4 <<<<<<<<<
30000 = 7*4285 + 5

3 + 4 = 7

3000 + 3 = 7*428 + 4 + 7*0 + 3 = 7*429

3 = 3 mod 17
30 = 13 mod 17 <<<<<
300 = 11 mod 17
3000 = 8 mod 17 <<<<<
30000 = 12 mod 17 <<<<<<
300000 = 1 mod 17 <<<<<<<
3000000 = 10 mod 17
30000000 = 15 mod 17
300000000 = 14 mod 17
3000000000 = 4 mod 17
30000000000 = 6 mod 17

13 + 8 + 12 + 1 = 34 = 0 mod 17

so

333030 = 0 mod 17

So out of the finite list of 3*10^n mod k is it always possible to find a set that adds up to 0 mod k?

 

[AlephZero]

Sorry AlephZero, don't think this works for all k

Oops! Try again...

Let a < b and 3*10^a = 3*10^b = r mod k.

Let n = 3*10^a + 3*10^(a+1) + ... + 3*10^(b-1)

(10 - 1)n = 3*10^b - 3*10^a

9n = 0 mod k.

So most of the time, n = 0 mod k

... but what happens if k is a multiple of 3 or 9, I wonder.

EDIT: Lookat what happens for k = 81.

 

[AlephZero]

OK, I got it. First, prove the following:

1 + 10^a + 10^2a is divisible by 3, for any integer a > 0.

1 + 10^a + 10^2a = (10^3a - 1)/(10-1)
= (1000^a - 1)/9
= ((3*9*37 + 1)^a - 1)/9
Expand by the binomial theorem: the two "1" terms cancel out, and all the other terms are divisible by 3.

Now the main proof:

If k is not a multiple of 3, the previous post shows how to construct a number n with 9n = 0 mod k. Since 3 does not divide k, then n = 0 mod k.

If k is a multiple of 3, let k = 3m.
Construct a number q such that q = 0 mod m. (Note, this is a recursive algorithm, since m may be a multiple of 3.)

Let q = r mod 3m. If r = 0 we are done and n = q.

If r is not 0, then define n to be the digits of q "repeated" three times (for example if q = 30033, n = 300333003330033)

n = 3r mod 3m, and r = 0 mod m, therefore n = 0 mod 3m.

 

[jing]

AlephZero look back at your first attempt and extend a and b

The will be (at least) k integers n(i) 1<= i <=k and n(i) =/= n(j) for i=/=j such that 3*10^n(i) = r mod k

Sum these for i=1 to k and the result, n, will be 0 mod k

3*10^n(i) = k*m(i) + r for some m(i) 1<= i <=k

let m be sum of m(i) i=1 to k

n = km + kr

n = k(m + r)

 

[uart]

Good proof jing. So just summarizing, you're saying the Aleph's post should have gone some like as follows :Consider the sequence 3, 30, 300 ... 3*10^n ... mod k.

There are a finite number (k) of different values of the sequence.

So working through the terms in order, after searching k(k-1) terms either we find a term = 0 (mod k), or we can find at least k terms with the same nonzero (mod k) value, r say.

If we find a zero term, we have a value of n. In the other case, we can add the k terms with value r to get the required n, as kr = 0 mod k.

 

[jing]

Thank you uart. I hope it helped murshid_islam to see that when you do not know how to start you just start anyway and play around with some numbers to get a feel of what might be useful. Even if where you start leads you down a dead end it might well have taken you passed the right route. You just have to be open to looking for it.

 

[roger]

1 + 10^a + 10^2a = (10^3a - 1)/(10-1)

How did you get this?
A counter example is a=2

 

[AlephZero]

1 + 10^a + 10^2a = (10^3a - 1)/(10-1)

How did you get this?
A counter example is a=2

DOH...

1 + 10^{a} + 10^{2a} = (10^{3a} - 1)/(10^a-1)

Which makes a hash of the rest of the proof, though the result IS valid.