Why is it that $1+(1+2+3+4+5+6+\ldots+n)$, basically a triangular number plus $1$, doesn't divide by $3$ or $5$?

Question

As a self learner I am currently learning about triangular numbers, for which the formula is:

$$T(n)=\frac{n(n+1)}{2}$$

While playing with my calculator, I added 1 to each resulted number, and I noticed that none of the results divides by $3$ or $5$

I am assuming that I am correct about this observation, other wise please let me know.

So I have multiplied both sides of the original formula by $2$, and now I have:

$2(T(n))=n(n+1) = n^2+n$

Now my question still remains still wide open:

why is it that $(n(n+1)+1) \bmod 3 \neq 0$ and $(n(n+1)+1) \bmod 5 \neq 0$?

Or you can see it as why $(n^2+n+1) \bmod 3 \neq 0$ and $(n^2+n+1) \bmod 5 \neq 0$?

Or you can see it as why $(1+2+3+4+5+6+\ldots+n)+1$, Basically why a triangular number plus $1$ does not dividing by $3$ nor $5$?

I have tried Google and also tried searching over here, but either I don't know what I am searching for or I simply can't find an answer.

I am trying to pull my head for a possible answer, but I just don't have a clue where to begin with.

Any answers or hints are appreciated. Also if this is a duplicated, I honestly couldn't find it, so please just close and refer me to it.

Answer 1

For this kind of modular arithmetic problems, remember that there are only finitely many numbers to check, when we are dealing with polynomials. This is because $a\equiv b$ mod $n$ implies that $p(a)\equiv p(b)$ mod $n$ as well.

Let $p(x)=\frac12x(x+1)+1$. Then note that $2p(x)=x^2+x+2$, and $2p(0)=2,2p(1)=1,2p(2)=2$. Therefore none of the three possible values of $2p(x)$ are $0$, so $3\nmid 2p(x)$. Since $3\nmid 2$ obviously, then $3\nmid p(x)$. You can do the same thing for $5$ instead of $3$.

It is useful to remember this idea so that you can apply it to other problems too.

Answer 2

Another way to look at it is, starting from 0

first you add 1 mod 3, so that the first triangular number is 1 mod 3,

then you add 2 mod 3, which gives 0 mod 3,

then you add 0 mod 3, so that it is still 0 mod 3,

repeat indefinitely

So the triangular numbers mod 3 are: 1, 0, 0, 1, 0, 0, ...

Since they are never 2, adding one to a triangular number gives a number not divisible by 3.

You can make a similar argument for 5.

Answer 3

Since $T(n)=\frac{1}{2}n(n+1)$, we have $8(T(n)+1)=4n^2+4n+8$. Completing the square gives $8(T(n)+1)=(2n+1)^2+7$.

Modulo 3, the only perfect squares are $0$ and $1$, and so $8(T(n)+1) \equiv 7 \pmod{3}$ or $8(T(n)+1) \equiv 8 \pmod{3}$. Since neither $7$ nor $8$ is a multiple of $3$, the result follows.

We can work similarly modulo 5. The only perfect squares are $0$ and $\pm 1$. So $8(T(n)+1) \equiv 6 \pmod{5}$, $8(T(n)+1) \equiv 7 \pmod {5}$, or $8(T(n)+1) \equiv 8 \pmod{5}$, and none of $6,7,8$ is a multiple of $5$.

Answer 4

Amusingly, it is better to multiply by $8$ than $2.$

$$8(T(n)+1)=4n^2+4n+8=(2n+1)^2+7$$

Now, in general, $m^2+7$ is never divisible by $3$ nor $5.$ You only have to check a little more than half of the cases, modulo $3,5.$

$$m\equiv 0\pmod 3\implies m^2+7\equiv 1\pmod 3\\ m\equiv \pm 1\pmod 3\implies m^2+7\equiv 2\pmod 3$$

Similarly, check the three cases $m\equiv 0,\pm 1,\pm2\pmod 5.$

The study of when $m^2-a$ can be divisible by a prime $p$ was a big question in early number theory, culminating in a theorem called Quadratic Reciprocity.

Reciprocity lets us show that:

If $p$ is an odd prime other than $7$, then we can find $m^2+7$ divisible by $p$ if and only if $$p\equiv 1,2,4\pmod 7.$$

So your numbers are never divisible by $13,17,$ or $19,$ either.

Answer 5

let $p$ be an odd prime. Notice $(n+(p+1)/2)^2 \equiv n^2+n + 2^{-2} \bmod p$

Hence our polynomial is congruent to $\frac{n^2+n}{2} + 1 \equiv (k^2-2^{-2})2^{-1}+1$ with $k=(n+(p+1)/2)$.

We try to solve in $k$ for this to be $0$ and get $k^2-2^{-2} \equiv -2$ or $k^2 \equiv 2^{-2} -2$.

That number is a square if and only if it is a square by multiplying it by $4$, hence a solution exists if and only if $-7$ is a quadratic residue $\bmod p$.

$\left(\frac{-p}{7}\right) = \left(\frac{-1}{7}\right)\left(\frac{7}{p}\right)$

We can calculate $\left(\frac{7}{p}\right)$ with quadratic reciprocity as here and get,

$7$ is a quadratic residue for any prime $p\equiv\pm1,\pm3,\pm9\pmod{28}$

Finally you multiply by the other symbol ( which is just $-1^{(p-1)/2}$ )

and you can get which congruences for $p\bmod 28$ make $-7$ a quadratic residue.

I get the valid residues are $1,7,9,11,15,23,25$

This seems to check out, so an odd prime $p$ divides a number in that sequence if and only if it is congruent to one of the previous $7$ values $\bmod 28$