When Is the Digital Root Three?

Equivalently, we want to know for which $n$ is $n^2+n+1 \equiv 3 \pmod 9$ . For this to occur we need $3 \mid n^2+n+1 \mid n^3-1$ , so by Fermat's theorem a necessary condition is $n \equiv 1 \pmod 3$ . Conversely, it's easy to check that for $n \equiv -2, 1, 4 \pmod 9$ we get $n^2+n+1 \equiv 3 \pmod 9$ so this condition is also sufficient.

So we just want the number terms in the arithmetic progression $1, 4, 7, \ldots, 1000$ , which is $1 + (1000-1)/3 = 334$ .

Obviously the digit root is any number must be a positive integer from 1 to 9. Now, a well-known fact, the sum of the digits of a number is congruent to the original number mod 9. If n=3k-1, then n^2+n+1=9k^2-3k+1 which cannot be 3 mod 9. Now if n=3k, then n^2+n+1=9k^2+3k+1 which cannot be 3 mod 9. If n=3k+1, then n^2+n+1=9k^2+9k+3 which is 3 mod 9. So only numbers of the form 3k+1 work. These numbers are 1, 4, 7, ..., 1000 and there are 334 of these numbers.

The digital root of a number is the residue when that number is divided by 9, because a number is congruent to its sum of digits mod 9. Thus we need to find the number of n such that $n^2+n+1 \equiv 3 \pmod{9}$ . We see that if n is 1 mod 3, then n^2+n+1 is 3 mod 9. If n is 2 mod 3, then n^2+n+1 is 1 mod 3, so not 3 mod 9. If n is 0 mod 3, then n^2+n+1 is also 1 mod 3. Thus the digital root is 3 iff $3 \mid n-1$ , so the answer is 334

Define $S(n)$ to be the sum of digits function. Observe that $n\equiv S(n)\pmod {9}$ . So, $n^2+n+1\equiv 3\pmod {9}\implies n\equiv 1,4,7\pmod 9$ . So, we have 3 different arithmetic progression of n's which'll work namely, $\{1,10,19,...,1000\}, \{4,13,...,994\},\{7,16,...,997\}$ . Calculate the number of terms in each of these sequences which'll actually give the number of solutions: $112+111+111=\boxed{334}$ .

Peace. AD.

We first notice that the digital root of a number $x$ is equivalent to $x \pmod{9}$ if $x$ is neither equal to $0$ nor divisible by $9$ .This is because $10^k \equiv 1\pmod{9}$ . So independent of the position, the value mod 9 is the same.This reduces the problem to finding the number of $n$ 's that satisfy the following quadratic congruency. $n^2 + n + 1 \equiv 3 \pmod{9}$ . Thus the problem boils down to finding the number of n's that make the expression $n^2 + n - 2$ or ( $n+2)(n-1) \equiv 0 \pmod{9}$ divisible by 9.

After replacing a few numbers in the expression it becomes obvious that $n$ 's have to be of the form $3x+1$ . This can be easily confirmed by check that $n=3x+2, 3x$ clearly is not a multiple of 9, and $n=3x+1$ gives us $9(x)(x+1)$ which validates our assumption. Whats left to do is to count the number of integers of the form $3x+1$ below one thousand. Since the relationship is linear we can subtract one from 1000 and divide it by 3 and add one,giving us 334 integers that make the expression divisible by 9.

[Slight edits - Calvin]

The digit root of a number will be 3 if the number is a multiple of 3, but not of 6 and 9. So n^2+n+1 \equiv 0 \pmod{3} \rightarrow n(n+1) \equiv 2 \pmod{3} , and it is for n \equiv 1 \pmod{3} . We can demonstrate that n(n+1)\equiv 5 \pmod{6} and n(n+1)\equiv 8 \pmod{9} is impossible for integers n. So there are \frac {999}{3}+1=334

using (mod 9) , n^2 + n + 1 = 3 (mod 9) ; n(n + 1) = 2 (mod 9) ; n must be = 1 , 4 , 7 , 10 , .... ; with U (n) = *3n - 2* ; maximum n = 334 ---> U (334) = 1000 ; thus, the answer is 334

Let $\sigma(x)$ denote the sum of the digits of $x$ .

Lemma 1: $\sigma(x)\equiv x\pmod{9}$ .

Proof: Let $x= \overline{a_na_{n-1}\cdots a_1a_0}$ . Then $x=\sum_{i=0}^{n}a_i10^{i}$

Since $10^i\equiv 1^i\equiv 1 \pmod{9}$ ,

We have $x\equiv \sum_{i=0}^{n}a_i10^{i}\equiv \sum_{i=0}^{n}a_i \equiv \sigma(x) \pmod{9}.$

$\Box$

Define $\sigma_{k}(x)=\sigma(\sigma_{k-1}(x))$ and $\sigma_1(x)=\sigma(x)$ .

Lemma 2: $x\equiv \sigma_{i}(x) \pmod{9}$ .(For all $i\geq 1$ )

Proof: Let $\mathcal{A}$ be the set of all elements $p$ such that $\sigma_p(x) \not\equiv x \pmod{9}$ . Since each $p$ is positive, $\mathcal{A}$ must contain a lowest element $a$ . So we know that $\sigma_{a-1}(x)\equiv x \pmod{9}$ since $a-1$ does not belong in the set. But then $\sigma_a(x)\equiv \sigma(\sigma_{a-1}(x))\equiv \sigma_{a-1}(x)\equiv x \pmod{9}$ . Contradiction. Thus, set $\mathcal{A}$ must be empty and so $x\equiv \sigma_{i}(x) \pmod{9}$ .(For all $i\geq 1$ ).

$\Box$

This means our problem is reduced to finding all values of $n$ such that $n^2+n+1\equiv 3 \pmod{9}$ . So then we get $n^2+n-2\equiv 0 \pmod{9}$ . Factoring gives $(n-1)(n+2)\equiv \pmod{9}$

So $n$ must be congruent to 1 mod 3. Thus, there are 334 values of $n$ less than or equal to 1000.

The digit sum of a number is equivalent to the number modulo 9. The digit sum of a number decreases if the number has 2 or more digits. Hence, the digit root of a number, will be equal to the equivalence class of the number modulo 9.

We just need to calculate the values of $k^2 + k + 1 \pmod{9}$ for $k = 1, 2, \ldots 9$ . We see that this value is 3 if and only if $k = 1, 4, 7$ . There are 112 positive integers $n \leq 1000$ which satisfy $n \equiv 1 \pmod{9}$ . There are 111 positive integers $n \leq 1000$ which satisfy $n \equiv 4 \pmod{9}$ . There are 111 positive integers $n\leq 1000$ which satisfy $n \equiv 7 \pmod{9}$ . Hence there $112 + 111 + 111 = 334$ positive integers $n \leq 1000$ such that the digit root of $n^2+n+1$ is equal to 3.

we have that 1 is correct and every time we add 3 we have a solution so we have from 1 to 1000 we have 334

1000 = 1 + 3(n-1) 1000 = 1 + 3n - 3 1000 = 3n - 2 1002 = 3n 1002\3 = n n = 334