Waste less time on Facebook — follow Brilliant.
×

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
3 years ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

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\) Mursalin Habib · 3 years ago

Log in to reply

@Mursalin Habib Nice. Sharky Kesa · 3 years ago

Log in to reply

@Sharky Kesa Do you realize that this hint is as good as a proof? Mursalin Habib · 3 years 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 · 3 years ago

Log in to reply

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 Finn Hulse · 3 years ago

Log in to reply

@Finn Hulse That was unbelievably hard to type. What a waste of time. :D Finn Hulse · 3 years ago

Log in to reply

@Finn Hulse There was a smaller proof, you realise. Sharky Kesa · 3 years ago

Log in to reply

@Sharky Kesa Mwahahaha yeah... :D Finn Hulse · 3 years ago

Log in to reply

@Finn Hulse Aren't you incensed at the thought of a smaller proof? :D Sharky Kesa · 3 years 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 · 3 years ago

Log in to reply

@Finn Hulse Sounds good enough to me. :D Sharky Kesa · 3 years ago

Log in to reply

What does \(\overline{n2n}\) mean? Nanayaranaraknas Vahdam · 3 years ago

Log in to reply

@Nanayaranaraknas Vahdam 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 · 3 years ago

Log in to reply

@Sharky Kesa 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 \)." Calvin Lin Staff · 3 years ago

Log in to reply

@Calvin Lin OK. Sharky Kesa · 3 years ago

Log in to reply

@Sharky Kesa 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\). Nanayaranaraknas Vahdam · 3 years ago

Log in to reply

@Nanayaranaraknas Vahdam What about 714? Sharky Kesa · 3 years ago

Log in to reply

@Sharky Kesa 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. Nanayaranaraknas Vahdam · 3 years ago

Log in to reply

@Nanayaranaraknas Vahdam I have a proof. Do we have the same proof? Sharky Kesa · 3 years ago

Log in to reply

@Sharky Kesa I am not sure Nanayaranaraknas Vahdam · 3 years ago

Log in to reply

@Nanayaranaraknas Vahdam Does it involve factorising? BTW, the above equation is \(n \times 10^k + 2n\). Sharky Kesa · 3 years 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 · 3 years ago

Log in to reply

@Alamuru Ganesh YES! Sharky Kesa · 3 years ago

Log in to reply

@Sharky Kesa Is it the same proof what you thought of ? Alamuru Ganesh · 3 years ago

Log in to reply

@Alamuru Ganesh yep. Sharky Kesa · 3 years ago

Log in to reply

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 · 2 years, 7 months ago

Log in to reply

@Abhinav Raichur Heh, Heh ... Evil plan forming. :P Sharky Kesa · 2 years, 7 months ago

Log in to reply

@Sharky Kesa yes :p :) Abhinav Raichur · 2 years, 7 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 · 3 years ago

Log in to reply

@Star Light What about 714? Sharky Kesa · 3 years ago

Log in to reply

@Finn Hulse I expect you to have a proof. Sharky Kesa · 3 years ago

Log in to reply

@Sharky Kesa I just found this. Okay, I'll write one. :D Finn Hulse · 3 years ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...