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\)

Log in to reply

Nice.

Log in to reply

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

Log in to reply

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

Log in to reply

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

Log in to reply

There was a smaller proof, you realise.

Log in to reply

Log in to reply

Log in to reply

Log in to reply

Log in to reply

What does \(\overline{n2n}\) mean?

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.

Log in to reply

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

Log in to reply

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

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.

Log in to reply

Log in to reply

Log in to reply

Log in to reply

Log in to reply

Log in to reply

Log in to reply

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. :pLog in to reply

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

Log in to reply

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.

Log in to reply

What about 714?

Log in to reply

@Finn Hulse I expect you to have a proof.

Log in to reply

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

Log in to reply