1

Is it OK to assert that a number (mod 3) is the sum of each of its digit (mod 3), i.e., for an n-digit number represented by a1a2a3...an (mod 3) = a1 (mod 3) + a2 (mod 3) + a3 (mod 3) + ... + an( mod 3) ?

Beedassy Lekraj
  • 121
  • 1
    That's perfectly correct. It's also true mod $9$. This is because $10\equiv 1\mod3$ (resp. $9$). – Bernard Jul 10 '16 at 15:18
  • Good ! Then can we further simplify it by saying : "a number (mod 3) is its digital root (mod 3)" ? – Beedassy Lekraj Jul 10 '16 at 15:24
  • ??? I have not the least idea of what a ‘digital root’ is, so I couldn't tell you. – Bernard Jul 10 '16 at 15:26
  • Digital root of a number N is the sum of its digits iterated until a single digit is obtained and is in fact equal to N (mod 9). For instance, digital root of 58635967351 is digital root of (5 + 8 + 6 + 3 + 5 + 9 + 6 + 7 + 3 + 5 + 1 = 58) is the digital root of (5 + 8 = 13) is equal to 1 + 3 = 4. This is most easily computed by casting out 9's, then sum of digits that add up to 9"s. – Beedassy Lekraj Jul 10 '16 at 15:35
  • Didn't know this name… – Bernard Jul 10 '16 at 20:17

1 Answers1

1

Not quite, but you're close. Assuming you mean the decimal digits, then what you have is that

$$d_nd_{n-1}\dots d_1d_0\equiv (d_n\hspace{-1em}\mod 3+d_{n-1}\hspace{-1em}\mod 3+\dots+d_0\hspace{-1em}\mod 3)\pmod 3$$

The reason that you can't just say that the number mod $3$ "is" the sum of all of its digits (with each digit taken mod $3$) is that that value might be too large; even though they're in the same equivalence class, when we talk about $n\mod 3$ we usually mean the smallest member of that equivalence class; in other words, the remainder when $n$ is divided by $3$. So, for instance, $111111\mod 3$ 'is' $0$, since it's divisible by $3$ - but $1+1+1+1+1+1$ is $6$. But of course $0\equiv 6\pmod 3$, so they are in the same residue class.

The reason that this is so, incidentally, is because $10\equiv 1\pmod 3$, so (because modularity 'respects' multiplication), $10^n\equiv 1\pmod 3$ for all $n$; and since $d_nd_{n-1}\ldots d_1d_0$ is shorthand notation for $d_n\times 10^n+d_{n-1}\times 10^{n-1}+\ldots$, we can write $$\begin{align} d_nd_{n-1}\ldots d_0 &= d_n\times 10^n+d_{n-1}\times 10^{n-1}+\dots\\ &\equiv d_n\hspace{-1em}\mod 3\times 10^n\hspace{-1em}\mod 3+d_{n-1}\hspace{-1em}\mod 3\times 10^{n-1}\hspace{-1em}\mod 3+\dots \\ &\equiv d_n\hspace{-1em}\mod 3\times 1+d_{n-1}\hspace{-1em}\mod 3\times 1+\dots\\ &\equiv (d_n\hspace{-1em}\mod 3+d_{n-1}\hspace{-1em}\mod 3+\dots+d_0\hspace{-1em}\mod 3) \pmod 3 \end{align}$$

Steven Stadnicki
  • 51,746
  • Application : Given the largest product of numbers that add up to N is 3^(N/3) or 43^{(N - 4)/3} or 23^{(N - 2)/3} according as to whether N (mod 3) is 0, 1 or 2. Thus, for N = 31122016 working (mod 3) we have N ≡ 1, so that maximum product of numbers that add up to 31122016 is 4*3^10374004. – Beedassy Lekraj Jul 10 '16 at 16:22
  • Further to the previous comment, the quotient [31122016/3] can be obtained without long division as [(3 + 1 + 1 + 2 + 2 + 0 + 1 + 6)/3] + 3(3112201 + 311220 + 31122 + 3112 + 311 + 31 + 3) = 5 + 3×3458000 = 10374005. – Beedassy Lekraj Jul 31 '19 at 07:45