- #1

- 419

- 14

thanks in advance.

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter murshid_islam
- Start date

- #1

- 419

- 14

thanks in advance.

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

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

- 419

- 14

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

- #8

AlephZero

Science Advisor

Homework Helper

- 7,002

- 297

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

- #9

- 419

- 14

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

- 419

- 14

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

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

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

- 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

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

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

- 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

Share:

- Replies
- 2

- Views
- 2K