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$? 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.
 A: 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.
A: 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.
A: 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)=(4n+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$.
A: 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.
A: 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$
