- #1

- 409

- 12

thanks in advance.

- Thread starter murshid_islam
- Start date

- #1

- 409

- 12

thanks in advance.

- #2

- 123

- 0

Try the numbers below 10 to begin with.

- #3

uart

Science Advisor

- 2,776

- 9

Well, as it turns out it can be verified for all the numbers 1..9, but what does that prove?Try the numbers below 10 to begin with.

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

- 9

--Ignore--

Last edited:

- #5

- 409

- 12

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

- #6

- 123

- 0

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

If not extend up to 20 or 30

If not extend up to 20 or 30

- #7

- 409

- 12

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

- #8

AlephZero

Science Advisor

Homework Helper

- 6,994

- 292

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

- #9

- 409

- 12

i tried upto 20. but still i can't see any pattern.Have you seen any patterns or processes that might be useful?

If not extend up to 20 or 30

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?

Have you checked them out with what alephzero said?

- #11

- 409

- 12

yeah i did. but i am still in the dark.How did you get these results?

Have you checked them out with what alephzero said?

- #12

AlephZero

Science Advisor

Homework Helper

- 6,994

- 292

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.

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?

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

- 6,994

- 292

Oops! Try again...Sorry AlephZero, don't think this works for all k

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

- 6,994

- 292

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

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

- 9

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.

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

- #19

- 319

- 0

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

How did you get this?

A counter example is a=2

How did you get this?

A counter example is a=2

- #20

AlephZero

Science Advisor

Homework Helper

- 6,994

- 292

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

How did you get this?

A counter example is a=2

[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

- Replies
- 16

- Views
- 6K

- Replies
- 2

- Views
- 2K

- Last Post

- Replies
- 2

- Views
- 7K

- Replies
- 1

- Views
- 1K

- Last Post

- Replies
- 8

- Views
- 1K

- Replies
- 7

- Views
- 690

- Replies
- 28

- Views
- 6K

- Replies
- 6

- Views
- 1K

- Replies
- 4

- Views
- 2K

- Replies
- 47

- Views
- 16K