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

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.

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--

Last edited:
Try the numbers below 10 to begin with.
but how does that help in proving it for every positive integer k?

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

If not extend up to 20 or 30

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

AlephZero
Homework Helper
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.

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?

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

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
Homework Helper
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.

Last edited:
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?

Last edited:
AlephZero
Homework Helper
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.

Last edited:
AlephZero
Homework Helper
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.

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.

Last edited:
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.

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

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

AlephZero
Homework Helper
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.