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

## Comments

Sort by:

TopNewestHint: \(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 · 2 years, 8 months ago

Log in to reply

– Sharky Kesa · 2 years, 8 months ago

Nice.Log in to reply

– Mursalin Habib · 2 years, 8 months ago

Do you realize that this hint is as good as a proof?Log in to reply

– Sharky Kesa · 2 years, 8 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.Log in to reply

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

Lemma 1All 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.

ProofAll 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 2If \(n \equiv a \pmod{3}\), then \(n+b\) will be equivalent to \(a+b \pmod{3}\).

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

Log in to reply

– Finn Hulse · 2 years, 8 months ago

That was unbelievably hard to type. What a waste of time. :DLog in to reply

– Sharky Kesa · 2 years, 8 months ago

There was a smaller proof, you realise.Log in to reply

– Finn Hulse · 2 years, 8 months ago

Mwahahaha yeah... :DLog in to reply

– Sharky Kesa · 2 years, 8 months ago

Aren't you incensed at the thought of a smaller proof? :DLog in to reply

– Finn Hulse · 2 years, 8 months ago

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

– Sharky Kesa · 2 years, 8 months ago

Sounds good enough to me. :DLog in to reply

What does \(\overline{n2n}\) mean? – Nanayaranaraknas Vahdam · 2 years, 8 months ago

Log in to reply

– Sharky Kesa · 2 years, 8 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.Log in to reply

– Calvin Lin Staff · 2 years, 8 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 \)."Log in to reply

– Sharky Kesa · 2 years, 8 months ago

OK.Log in to reply

– Nanayaranaraknas Vahdam · 2 years, 8 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\).Log in to reply

– Sharky Kesa · 2 years, 8 months ago

What about 714?Log in to reply

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

Log in to reply

– Sharky Kesa · 2 years, 8 months ago

I have a proof. Do we have the same proof?Log in to reply

– Nanayaranaraknas Vahdam · 2 years, 8 months ago

I am not sureLog in to reply

– Sharky Kesa · 2 years, 8 months ago

Does it involve factorising? BTW, the above equation is \(n \times 10^k + 2n\).Log in to reply

– Alamuru Ganesh · 2 years, 8 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?Log in to reply

– Sharky Kesa · 2 years, 8 months ago

YES!Log in to reply

– Alamuru Ganesh · 2 years, 8 months ago

Is it the same proof what you thought of ?Log in to reply

– Sharky Kesa · 2 years, 8 months ago

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

396943659which is obtained when 3969 and 3969*11 are concatenated. :p – Abhinav Raichur · 2 years, 3 months agoLog in to reply

– Sharky Kesa · 2 years, 3 months ago

Heh, Heh ... Evil plan forming. :PLog in to reply

– Abhinav Raichur · 2 years, 3 months ago

yes :p :)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 · 2 years, 8 months ago

Log in to reply

– Sharky Kesa · 2 years, 8 months ago

What about 714?Log in to reply

@Finn Hulse I expect you to have a proof. – Sharky Kesa · 2 years, 8 months ago

Log in to reply

– Finn Hulse · 2 years, 8 months ago

I just found this. Okay, I'll write one. :DLog in to reply