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

  • #1
419
14
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.
 

Answers and Replies

  • #2
123
0
Try the numbers below 10 to begin with.
 
  • #3
uart
Science Advisor
2,797
21
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
 
  • #4
uart
Science Advisor
2,797
21
--Ignore--
 
Last edited:
  • #5
419
14
Try the numbers below 10 to begin with.
but how does that help in proving it for every positive integer k?
 
  • #6
123
0
Have you seen any patterns or processes that might be useful?

If not extend up to 20 or 30
 
  • #7
419
14
maybe i'm incredibly stupid but i still don't see any pattern.
 
  • #8
AlephZero
Science Advisor
Homework Helper
7,002
297
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.
 
  • #9
419
14
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?
 
  • #10
123
0
How did you get these results?
Have you checked them out with what alephzero said?
 
  • #11
419
14
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.
 
  • #12
AlephZero
Science Advisor
Homework Helper
7,002
297
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:
  • #13
123
0
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:
  • #14
AlephZero
Science Advisor
Homework Helper
7,002
297
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:
  • #15
AlephZero
Science Advisor
Homework Helper
7,002
297
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.
 
  • #16
123
0
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)
 
  • #17
uart
Science Advisor
2,797
21
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:
  • #18
123
0
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.
 
  • #19
319
0
1 + 10^a + 10^2a = (10^3a - 1)/(10-1)

How did you get this?
A counter example is a=2
 
  • #20
AlephZero
Science Advisor
Homework Helper
7,002
297
1 + 10^a + 10^2a = (10^3a - 1)/(10-1)

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

DOH.....

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

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

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

Replies
12
Views
2K
Replies
4
Views
2K
Replies
11
Views
3K
  • Last Post
Replies
11
Views
3K
  • Last Post
Replies
25
Views
7K
Replies
8
Views
1K
Replies
15
Views
8K
Top