Sharky's Conjecture

I thought of this while sitting in a car.

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

Note by Sharky Kesa
5 years, 4 months ago

No vote yet
1 vote

  Easy Math Editor

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.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

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

[example link](https://brilliant.org)example link
> 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×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

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

Abhinav Raichur - 4 years, 11 months ago

Log in to reply

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

Sharky Kesa - 4 years, 11 months ago

Log in to reply

yes :p :)

Abhinav Raichur - 4 years, 11 months ago

Log in to reply

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.

Star Light - 5 years, 4 months ago

Log in to reply

What about 714?

Sharky Kesa - 5 years, 4 months ago

Log in to reply

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

Lemma 1

All numbers in base nn such that n1(mod3)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 abcd\overline{abcd\dots}. In decimal representation, we take this to mean 10n(a)+10n1(b)+10n210^n(a)+10^{n-1}(b)+10^{n-2} \dots. Before going further, note that 101(mod3)10 \equiv 1 \pmod{3}. Thus any power of 1010, say 100100 will equal 1×1=1(mod3)1 \times 1=1 \pmod{3}, and by multiplying by 10 again, the number is still 1(mod3)1 \pmod{3}. For example, 1051=99999=3×3333310^5-1=99999=3 \times 33333. Anyways, using this property, we can split this given polynomial form for decimal numbers into two parts,

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

Which, when grouping, becomes

(10n1)a+(10n11)b+(10n21)c+(a+b+c)(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 1010 minus 11, the left part of the expression will have all of it's coefficients divisible by 33, since they're all powers of 1010 minus 11, which will make that whole part divisible by 33 regardless of what the actual numbers are. Now, as long as the right hand part ((a+b+c)(a+b+c\dots)) is divisible by 33, 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(mod3)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 na(mod3)n \equiv a \pmod{3}, then n+bn+b will be equivalent to a+b(mod3)a+b \pmod{3}.

Proof

This is easily proven by recalling Lemma 1. Because a number nn that is abcd\overline{abcd\dots} can be split up into a part that is clearly divisible by 33, and then added to a+b+ca+b+c\dots. Thus, by adding some arbitrary aa to nn, you will add to the digit sum which will cause it to change by a(mod3)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 nn:

Case 1

n0(mod3)n \equiv 0 \pmod{3}. This will obviously work for all cases, since the first part which is simply nn will have a digit sum divisible by 33 and so will 2n2n, 5n5n, 8n8n, and 11n11n.

Case 2

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

Case 3

n2(mod3)n \equiv 2 \pmod{3}. Similarly, we can construct that the digit sum of nn plus the digit sum of 2n2n, 5n5n, 8n8n, or 11n11n will equal 2+22(mod3)2+2^2 \pmod{3} which is 00 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

Finn Hulse - 5 years, 4 months ago

Log in to reply

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

Finn Hulse - 5 years, 4 months ago

Log in to reply

There was a smaller proof, you realise.

Sharky Kesa - 5 years, 4 months ago

Log in to reply

@Sharky Kesa Mwahahaha yeah... :D

Finn Hulse - 5 years, 4 months ago

Log in to reply

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

Sharky Kesa - 5 years, 4 months ago

Log in to reply

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

Finn Hulse - 5 years, 4 months ago

Log in to reply

@Finn Hulse Sounds good enough to me. :D

Sharky Kesa - 5 years, 4 months ago

Log in to reply

@Finn Hulse I expect you to have a proof.

Sharky Kesa - 5 years, 4 months ago

Log in to reply

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

Finn Hulse - 5 years, 4 months ago

Log in to reply

Hint: ndigit sum of n(mod3)n\equiv \text{digit sum of }n\pmod 3

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

Mursalin Habib - 5 years, 4 months ago

Log in to reply

Nice.

Sharky Kesa - 5 years, 4 months ago

Log in to reply

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

Mursalin Habib - 5 years, 4 months ago

Log in to reply

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

Sharky Kesa - 5 years, 4 months ago

Log in to reply

What does n2n\overline{n2n} mean?

Nanayaranaraknas Vahdam - 5 years, 4 months ago

Log in to reply

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.

Sharky Kesa - 5 years, 4 months ago

Log in to reply

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

Calvin Lin Staff - 5 years, 4 months ago

Log in to reply

@Calvin Lin OK.

Sharky Kesa - 5 years, 4 months ago

Log in to reply

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

Nanayaranaraknas Vahdam - 5 years, 4 months ago

Log in to reply

@Nanayaranaraknas Vahdam What about 714?

Sharky Kesa - 5 years, 4 months ago

Log in to reply

@Sharky Kesa The number must be of the form n×10k+1+2nn\times10^{k+1} + 2n, where kk is the number of digits in 2n2n. Now, the digit sum is equal to digit sum of n+n+ digit sum of 2n2n. Now, there are 33 cases. If the digit sum of nn is 1mod31 mod 3. Now, I am working on a proof to show that the digit sum of 2n2n would be 2mod32 mod 3. The sum of the two is divisible by 33.

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

If the digit sum is divisible by 33, then nn is divisible by 33, and 2n2n is also divisible by 33. Thus, the sum of the digit sums of nn and 2n2n is divisible by 33.

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

Nanayaranaraknas Vahdam - 5 years, 4 months ago

Log in to reply

@Nanayaranaraknas Vahdam I have a proof. Do we have the same proof?

Sharky Kesa - 5 years, 4 months ago

Log in to reply

@Sharky Kesa I am not sure

Nanayaranaraknas Vahdam - 5 years, 4 months ago

Log in to reply

@Nanayaranaraknas Vahdam Does it involve factorising? BTW, the above equation is n×10k+2nn \times 10^k + 2n.

Sharky Kesa - 5 years, 4 months ago

Log in to reply

@Sharky Kesa 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?

Alamuru Ganesh - 5 years, 4 months ago

Log in to reply

@Alamuru Ganesh YES!

Sharky Kesa - 5 years, 4 months ago

Log in to reply

@Sharky Kesa Is it the same proof what you thought of ?

Alamuru Ganesh - 5 years, 4 months ago

Log in to reply

@Alamuru Ganesh yep.

Sharky Kesa - 5 years, 4 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...