Sharky's Conjecture

I thought of this while sitting in a car.

Say there is a positive integer $n$. Prove that if you concatenate $n$ and $2n$ (as $\overline {n2n}$), the resultant is always divisible by 3. e.g. $510, 1734$, etc. Furthermore, prove that $\overline {n5n}, \overline {n8n}, \overline {n11n}$, etc. are all divisible by 3.

Note by Sharky Kesa
7 years, 2 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

• bulleted
• list

1. numbered
2. list

1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

> This is a quote
This is a quote
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

Hint: $n\equiv \text{digit sum of }n\pmod 3$

Furthermore, you can do this as well: $144\equiv (14+4)\equiv (1+44)\equiv (1+4+4)\pmod 3$

- 7 years, 2 months ago

Nice.

- 7 years, 2 months ago

Do you realize that this hint is as good as a proof?

- 7 years, 2 months ago

Yes, as soon as the hint was given, a proof as found. I want to see if anyone else could find the proof.

- 7 years, 2 months ago

What do we notice about the given conditions? i.e. that $2, 5, 8, 11 \equiv 2 \pmod{3}$.

Lemma 1

All numbers in base $n$ such that $n \equiv 1 \pmod{3}$ which have a digit sum divisible by three will themselves be divisible by three.

Proof

All numbers are in the form $\overline{abcd\dots}$. In decimal representation, we take this to mean $10^n(a)+10^{n-1}(b)+10^{n-2} \dots$. Before going further, note that $10 \equiv 1 \pmod{3}$. Thus any power of $10$, say $100$ will equal $1 \times 1=1 \pmod{3}$, and by multiplying by 10 again, the number is still $1 \pmod{3}$. For example, $10^5-1=99999=3 \times 33333$. Anyways, using this property, we can split this given polynomial form for decimal numbers into two parts,

$(10^n-1)a+a+(10^{n-1}-1)b+b+(10^{n-2}-1)c+c \dots$

Which, when grouping, becomes

$(10^n-1)a+(10^{n-1}-1)b+(10^{n-2}-1)c \dots+(a+b+c \dots)$

From what we've derived about powers of $10$ minus $1$, the left part of the expression will have all of it's coefficients divisible by $3$, since they're all powers of $10$ minus $1$, which will make that whole part divisible by $3$ regardless of what the actual numbers are. Now, as long as the right hand part ($(a+b+c\dots)$) is divisible by $3$, the WHOLE expression will be divisible by three. This is simply the digit sum! We can further extend this to encompass numbers in all bases that are $1 \pmod{3}$ because as shown above, they will be able to be split up into a clearly divisible-by-three part, and a digit sum part. Thus we have proven the lemma.

Lemma 2

If $n \equiv a \pmod{3}$, then $n+b$ will be equivalent to $a+b \pmod{3}$.

Proof

This is easily proven by recalling Lemma 1. Because a number $n$ that is $\overline{abcd\dots}$ can be split up into a part that is clearly divisible by $3$, and then added to $a+b+c\dots$. Thus, by adding some arbitrary $a$ to $n$, you will add to the digit sum which will cause it to change by $a \pmod{3}$ and we're done.

With these little lemmas in hand, we can begin to approach this problem. Anyways, we'll consider three different cases for $n$:

Case 1

$n \equiv 0 \pmod{3}$. This will obviously work for all cases, since the first part which is simply $n$ will have a digit sum divisible by $3$ and so will $2n$, $5n$, $8n$, and $11n$.

Case 2

$n \equiv 1 \pmod{3}$. In this case, $n$ will have a digit sum of $1 \pmod{3}$. So for any given $2n$, the digit sum will for sure be equivalent to $2 \pmod{3}$ from Lemma 2 and thus by adding the digit sum of $2n$, $5n$, $8n$, or $11n$ to the digit sum of $n$, the result will be equivalent to $1+2 \pmod{3}$ and we're finished with this case.

Case 3

$n \equiv 2 \pmod{3}$. Similarly, we can construct that the digit sum of $n$ plus the digit sum of $2n$, $5n$, $8n$, or $11n$ will equal $2+2^2 \pmod{3}$ which is $0$ and we're done!

Absolutely amazing proof problem @Sharky Kesa! I loved writing this obnoxiously long proof. @Mursalin Habib how you like me now? :D

- 7 years, 2 months ago

That was unbelievably hard to type. What a waste of time. :D

- 7 years, 2 months ago

There was a smaller proof, you realise.

- 7 years, 2 months ago

Mwahahaha yeah... :D

- 7 years, 2 months ago

Aren't you incensed at the thought of a smaller proof? :D

- 7 years, 2 months ago

Lemme just get my dictionary out and then answer you. Just kidding, yes, but I was just doing that for fun. :D

- 7 years, 2 months ago

Sounds good enough to me. :D

- 7 years, 2 months ago

What does $\overline{n2n}$ mean?

- 7 years, 2 months ago

It means you have the number as the first part of the number and the double of that is the second part of the number. If the number is 5, the second part would be 10, and the number altogether would be 510.

- 7 years, 2 months ago

You should clarify that in the question. I thought you meant that with $n = 1$, $\overline{n2n} = 121$. A better way of phrasing it, would be to say "Concatenate the digits of $n$ with the digits of $2n$."

Staff - 7 years, 2 months ago

OK.

- 7 years, 2 months ago

In that case, wouldn't the digit sum just be equal to $3$ times the digit sum of $n$ itself. Thus, it is divisible by $3$.

- 7 years, 2 months ago

- 7 years, 2 months ago

The number must be of the form $n\times10^{k+1} + 2n$, where $k$ is the number of digits in $2n$. Now, the digit sum is equal to digit sum of $n+$ digit sum of $2n$. Now, there are $3$ cases. If the digit sum of $n$ is $1 mod 3$. Now, I am working on a proof to show that the digit sum of $2n$ would be $2 mod 3$. The sum of the two is divisible by $3$.

If the digit sum of $n$, and I find a proof, then let $n=2k$, then $2n=4k\equiv k mod 3 \equiv 1 mod 3$. The sum is the two is divisible by $3$.

If the digit sum is divisible by $3$, then $n$ is divisible by $3$, and $2n$ is also divisible by $3$. Thus, the sum of the digit sums of $n$ and $2n$ is divisible by $3$.

Thus, $\overline{n2n}$ is divisible by $3$. Once I work out a proof, I will post it.

- 7 years, 2 months ago

I have a proof. Do we have the same proof?

- 7 years, 2 months ago

I am not sure

- 7 years, 2 months ago

Does it involve factorising? BTW, the above equation is $n \times 10^k + 2n$.

- 7 years, 2 months ago

if we take n common we will get n (10^k +2), 10 in mod 3 is 1 so the expression simplifies to n (1^k + 2) 1^k +2 is always equal to 3 , as one of the prime factors of the number"n2n" is 3 it leaves no remainder when divided by 3 . So any number of the form"n2n" is divisible by 3 is the proof satisfying?

- 7 years, 2 months ago

YES!

- 7 years, 2 months ago

Is it the same proof what you thought of ?

- 7 years, 2 months ago

yep.

- 7 years, 2 months ago

@Finn Hulse I expect you to have a proof.

- 7 years, 2 months ago

I just found this. Okay, I'll write one. :D

- 7 years, 2 months ago

This is quite simple.

The digit sum n + 2n = 3n. Therefore, it is divisible by three. Similarly, note that 5, 8 and 11 are all one less than a multiple of three. Hence, similiar logic applies.

- 7 years, 2 months ago

- 7 years, 2 months ago

hey! .... it may seem simple but i think that it has some interesting outcomes. You can tease your friend by giving him a very large number and ask him if it is prime or not....... you could give him 396943659 which is obtained when 3969 and 3969*11 are concatenated. :p

- 6 years, 9 months ago

Heh, Heh ... Evil plan forming. :P

- 6 years, 9 months ago

yes :p :)

- 6 years, 9 months ago