the sum of the convolutions with themselves of the coprimes of composite $n$

Question

Convolve the coprimes with themselves of composite n and find their sum. Let n =$5\cdot2^k$ with $k>0$ and use the example for $n=10$: $1\cdot1 + (3*1+1*3) + (7\cdot1+3\cdot3+1\cdot7) + (9\cdot1+7\cdot3+3\cdot7+1\cdot9) =90$, which is divisble by 10. This is also true for $n=20,40,80$ that each divides the sum of its convolution of coprimes with themselves. These sums in order are $1300, 19080$, and $289680$. Will this divisibility continue for all values of $k$? Can it be true of other $n$ of different prime factors?

Answer 1

This is not an answer, but a conjecture which does not fit into a comment.

Let $q$ be a prime number and $n=\prod_q q^{v_q}$ be the prime factorization of the integer $n >1 $. We have:

$$ n \ \text{ does not divide}\sum_{\begin{align*} \ 0&\le i,j \le n\\ &i+j\le n \\ (i,n)&=(j,n)=1 \end{align*}}ij $$ if and only if \begin{align*} &n=2^k q^m &\text{where } k>0,m \ge0 &\text{ and }q\equiv 3 \bmod4 \\ \text { or }\ \ &n=2^k 3^\ell\prod_{q} q^{v_q}&\text{where } k \ge0 , \ell >0, v_q \ge 0 &\text{ and }q\equiv 5 \bmod6. \end{align*}

This was verified numerically up to $n=1000$. There are $302$ such $n$ up to $1000$.

EDIT. Actually, when $n$ does not divide the sum, it fails by little, because it seems that whatever $n$, we have:

$$ 12\cdot\left(\sum_{\begin{align*} \ 0&\le i,j \le n\\ &i+j\le n \\ (i,n)&=(j,n)=1 \end{align*}}ij \right)\equiv 0 \pmod n$$

Answer 2

Hereafter is a proof of the following proposition:

Let $n,m$ be natural numbers and let
$$f(n):=\sum_{\underset{\underset{ (i,n)=(j,n)=1 } { i+j\le n}} {0\le i,j \le n }} ij .$$ Let $p$ be a prime number. We have: $$f(p^n)\equiv 0 \bmod p^n \iff p>3.$$ Moreover, when $p$ is odd, we have: $$f(2^mp^n)\equiv 0 \bmod 2^mp^n \iff p\equiv 1 \bmod 4.$$

which answers the OP, and constitutes a partial result for the previous conjecture on the characterization of the $n$ satisfying $f(n) \equiv 0 \bmod n$.

Start of proof. The proof uses the classical closed forms for the sum of powers of integers for the exponent $1,2\text{ and }3$. We have: \begin{align*} f(p^n)&=\sum_{\underset{\underset{ (i, p^n)=(j, p^n)=1 } { i+j\le p^n}} {0\le i,j \le p^n }} ij=\sum_{\underset{\underset{ i,j\not{\equiv}0\bmod p}{ i+j\le p^n}} {1\le i,j \le p^n-1 } } ij\\ f(p^n)&=\sum_{k=2}^{p^n} \sum_{\underset{j,k-j\not{\equiv}0 \bmod p} {1\le j \le k-1 } } j(k-j) \end{align*} We have introduced the new summation index $k=i+j$. Then, \begin{align*} f(p^n)&=\sum_{\underset{j\not{\equiv} 0 \bmod p} {1\le j \le p^n-1 } } j\sum_{\underset{k-j\not{\equiv} 0 \bmod p} {j+1\le k \le p^n } }(k-j)\\ f(p^n)&=\sum_{\underset{j\not{\equiv} 0 \bmod p} {1\le j \le p^n-1 } } j \sum_{\underset{u \not{\equiv} 0 \bmod p} {1\le u \le p^n-j } }u\\ f(p^n)&=\sum_{1\le j \le p^n-1 } j \sum_{\underset{u \not{\equiv} 0 \bmod p} {1\le u \le p^n-j } }u-\sum_{\underset{j\equiv 0 \bmod p} {1\le j \le p^n-1 } } j \sum_{\underset{u \not{\equiv} 0 \bmod p} {1\le u \le p^n-j } }u\\ f(p^n)&=\sum_{1\le j \le p^n-1 } j \sum_{1\le u \le p^n-j } u-\sum_{1\le j \le p^n-1 } j \sum_{\underset{u \equiv 0 \bmod p} {1\le u \le p^n-j } }u\\ &-\sum_{\underset{j\equiv 0 \bmod p} {1\le j \le p^n-1 } } j \sum_{1\le u \le p^n-j }u+\sum_{\underset{j\equiv 0 \bmod p} {1\le j \le p^n-1 } } j \sum_{\underset{u \equiv 0 \bmod p} {1\le u \le p^n-j } }u\\ f(p^n)&=\sum_{1\le j \le p^n-1 } j \sum_{1\le u \le p^n-j } u-2\sum_{\underset{j\equiv 0 \bmod p} {1\le j \le p^n-1 } } j \sum_{1\le u \le p^n-j }u+\sum_{\underset{j\equiv 0 \bmod p} {1\le j \le p^n-1 } } j \sum_{\underset{u \equiv 0 \bmod p} {1\le u \le p^n-j } }u\\ f(p^n)&=\sum_{1\le j \le p^n-1 }\frac{j(p^n-j)(p^n-j+1)}{2}\\ &-2p\sum_{1\le k \le p^{n-1}-1 } k \sum_{1\le u \le p^n-kp }u\\ &+p^2\sum_{1\le k \le p^{n-1}-1 }k \sum_{1\le \ell \le p^{n-1}-k } \ell\\ f(p^n)&=\sum_{1\le j \le p^n-1 }\frac{j(p^n-j)(p^n-j+1)}{2}\\ &-2p\sum_{1\le k \le p^{n-1}-1 } \frac{k(p^n-kp)(p^n-kp+1)}{2}\\ &+p^2\sum_{1\le k \le p^{n-1}-1 } \frac{k(p^{n-1}-k)(p^{n-1}-k+1)}{2}\\ \end{align*} We expand the sums on the right hand side and replace the sums of powers by their well-known closed forms, and then, after some elementary algebric manipulations, we find: \begin{align*} f(p^n)=p^n\left(\frac{p-1}{2}\right)\frac{ p^{3 n - 2}(p-1) + 2 p^{2 n - 1}+2p^{n}+2}{12} \end{align*} If $p=2$, $f(2^n)=2^n\frac{ 2^{3 n - 3} + 2^{2 n-1}+2^{n}+1}{12}$. But $f(2)=1$ and if $n>1$, $2^{3 n - 3} +2^{2 n-1}+2^{n}+1$ is odd and a fortiori not multiple of $12$, then $2^n$ does not divide $f(2^n)$.

If $p=3$, $f(3^n)=3^n\frac{ 3^{3 n - 2} + 3^{2 n - 1}+3^{n}+1}{6}$.
But $ 3^{3 n - 2} + 3^{2 n - 1}+3^{n}+1$ is not divisible by $3$ and a fortiori not by $6$, then $3^n$ does not divide $f(3^n)$.

If $p>3$, we will show that $p^n$ divides $f(p^n)$. In that case, $p \equiv a \bmod 12$, whith $a= 1,5,7 \text{ or }-1$.

If $a=1$, $\frac{p-1}{4}$ is integer, and $f(p^n)=p^n\left(\frac{p-1}{4}\right)\frac{ 2p^{3 n - 2}(p-1) + 4 p^{2 n - 1}+4p^{n}+4}{12}$ and \begin{align*} 2p^{3 n - 2}(p-1) + 4 p^{2 n - 1}+4p^{n}+4 &\equiv 0+ 4+4+4\equiv0 \bmod 12 \end{align*} If $a=5$, $\frac{p-1}{4}$ is integer, and $f(p^n)=p^n\left(\frac{p-1}{4}\right)\frac{ 2p^{3 n - 2}(p-1) + 4 p^{2 n - 1}+4p^{n}+4}{12}$ and \begin{align*} 2p^{3 n - 2}(p-1) + 4 p^{2 n - 1}+4p^{n}+4 &\equiv 4(2\cdot5^{3 n - 2} + 5^{2 n - 1}+5^{n}+1) \bmod 12\\ 2\cdot5^{3 n - 2} + 5^{2 n - 1}+5^{n}+1&\equiv (-1)^{3 n -1} + (-1)^{2 n - 1}+(-1)^{n}+1 \bmod 3\\ &\equiv0 \bmod 3. \end{align*} If $a=7$, $f(p^n)=p^n\left(\frac{p-1}{2}\right)\frac{ p^{3 n - 2}(p-1) + 2 p^{2 n - 1}+2p^{n}+2}{12}$ and \begin{align*} p^{3 n - 2}(p-1) + 2 p^{2 n - 1}+2p^{n}+2 &\equiv 6\cdot 7^{3 n - 2} +2 \cdot 7^{2 n - 1}+2\cdot 7^{n}+2 \bmod 12\\ 3\cdot 7^{3 n - 2} + 7^{2 n - 1}+ 7^{n}+1&\equiv 3+1+1 +1 \bmod 6\\ &\equiv0 \bmod6. \end{align*} If $a=-1$, $f(p^n)=p^n\left(\frac{p-1}{2}\right)\frac{ p^{3 n - 2}(p-1) + 2 p^{2 n - 1}+2p^{n}+2}{12}$ and \begin{align*} p^{3 n - 2}(p-1) + 2 p^{2 n - 1}+2p^{n}+2 &\equiv -2\cdot (-1)^{3 n - 2} +2 \cdot (-1)^{2 n - 1}+2\cdot (-1)^{n}+2 \bmod 12\\ - (-1)^{3 n - 2} + (-1)^{2 n - 1}+ (-1)^{n}+1&\equiv -(-1)^n-1+(-1)^n+1 \bmod 6\\ &\equiv0 \bmod6. \end{align*}

Now, let $m,n>0$ be natural integers. \begin{align*} f(2^mp^n)&=\sum_{\underset{\underset{ (i,2^m p^n)=(j,2^m p^n)=1 } { i+j\le 2^m p^n}} {0\le i,j \le 2^m p^n }} ij=\sum_{\underset{\underset{i,j \text{ odd and } i,j\not{\equiv}0\bmod p}{ i+j\le 2^mp^n}} {1\le i,j \le 2^mp^n-1 } } ij\\ f(2^mp^n)&=\sum_{k=2}^{2^mp^n} \sum_{\underset{\underset{j,k-j \text{ odd} }{j,k-j\not{\equiv}0 \bmod p}} {1\le j \le k-1 } } j(k-j) \end{align*} We have introduced the new summation index $k=i+j$ and we see that in the above sum, $j$ must be odd and $k$ must be even. Then, \begin{align*} f(2^mp^n)&=\sum_{k=1}^{2^{m-1}p^n} \sum_{\underset{2j-1,2k-2j+1\not{\equiv} 0 \bmod p} {1\le j \le k } }(2j-1)(2k-2j+1)\\ f(2^mp^n)&=\sum_{\underset{2j-1\not{\equiv} 0 \bmod p} {1\le j \le 2^{m-1}p^n } } (2j-1)\sum_{\underset{2k-2j+1\not{\equiv} 0 \bmod p} {j\le k \le 2^{m-1}p^n } }(2k-2j+1)\\ f(2^mp^n)&=\sum_{\underset{2j-1\not{\equiv} 0 \bmod p} {1\le j \le 2^{m-1}p^n } } (2j-1) \sum_{\underset{2u-1 \not{\equiv} 0 \bmod p} {1\le u \le 2^{m-1}p^n-j+1 } } (2u-1)\\ f(2^mp^n)&=\sum_{ 1\le j \le 2^{m-1}p^n } (2j-1) \sum_{\underset{2u-1 \not{\equiv} 0 \bmod p} {1\le u \le 2^{m-1}p^n-j+1 } } (2u-1)-\sum_{\underset{2j-1\equiv 0 \bmod p} {1\le j \le 2^{m-1}p^n } } (2j-1) \sum_{\underset{2u-1 \not{\equiv} 0 \bmod p} {1\le u \le 2^{m-1}p^n-j+1 } } (2u-1)\\ f(2^mp^n)&=\sum_{ 1\le j \le 2^{m-1}p^n } (2j-1) \sum_{1\le u \le 2^{m-1}p^n-j+1 } (2u-1)-\sum_{ 1\le j \le 2^{m-1}p^n } (2j-1) \sum_{\underset{2u-1 \equiv 0 \bmod p} {1\le u \le 2^{m-1}p^n-j+1 } } (2u-1)\\ &-\sum_{\underset{2j-1\equiv 0 \bmod p} {1\le j \le 2^{m-1}p^n } } (2j-1) \sum_{1\le u \le 2^{m-1}p^n-j+1 } (2u-1)+\sum_{\underset{2j-1\equiv 0 \bmod p} {1\le j \le 2^{m-1}p^n } } (2j-1) \sum_{\underset{2u-1 \equiv 0 \bmod p} {1\le u \le 2^{m-1}p^n-j+1 } } (2u-1)\\ f(2^mp^n)&=\sum_{ 1\le j \le 2^{m-1}p^n } (2j-1) (2^{m-1}p^n-j+1)^2-\sum_{ 1\le j \le 2^{m-1}p^n } (2j-1) \sum_{\underset{2u-1 \equiv 0 \bmod p} {1\le u \le 2^{m-1}p^n-j+1 } } (2u-1)\\ &-\sum_{\underset{2j-1\equiv 0 \bmod p} {1\le j \le 2^{m-1}p^n } } (2j-1) (2^{m-1}p^n-j+1)^2+\sum_{\underset{2j-1\equiv 0 \bmod p} {1\le j \le 2^{m-1}p^n } } (2j-1) \sum_{\underset{2u-1 \equiv 0 \bmod p} {1\le u \le 2^{m-1}p^n-j+1 } } (2u-1)\\ f(2^mp^n)&=\sum_{ 1\le j \le 2^{m-1}p^n } (2j-1) (2^{m-1}p^n-j+1)^2-\sum_{\underset{2u-1 \equiv 0 \bmod p} {1\le u \le 2^{m-1}p^n} } (2u-1)\sum_{ 1\le j \le 2^{m-1}p^n-u+1 } (2j-1) \\ &-\sum_{\underset{2j-1\equiv 0 \bmod p} {1\le j \le 2^{m-1}p^n } } (2j-1) (2^{m-1}p^n-j+1)^2+\sum_{\underset{2j-1\equiv 0 \bmod p} {1\le j \le 2^{m-1}p^n } } (2j-1) \sum_{\underset{2u-1 \equiv 0 \bmod p} {1\le u \le 2^{m-1}p^n-j+1 } } (2u-1)\\ f(2^mp^n)&=\sum_{ 1\le j \le 2^{m-1}p^n } (2j-1) (2^{m-1}p^n-j+1)^2 \\ &-2\sum_{\underset{2j-1\equiv 0 \bmod p} {1\le j \le 2^{m-1}p^n } } (2j-1) (2^{m-1}p^n-j+1)^2\\ &+\sum_{\underset{2j-1\equiv 0 \bmod p} {1\le j \le 2^{m-1}p^n } } (2j-1) \sum_{\underset{2u-1 \equiv 0 \bmod p} {1\le u \le 2^{m-1}p^n-j+1 } } (2u-1)\\ f(2^mp^n)&=\sum_{ 1\le j \le 2^{m-1}p^n } (2j-1) (2^{m-1}p^n-j+1)^2 \\ &-2p\sum_{ 1\le k \le 2^{m-1}p^{n-1} } (2k-1) (2^{m-1}p^n-kp+\frac{p+1}{2})^2\\ &+\sum_{\underset{2j-1\equiv 0 \bmod p} {1\le j \le 2^{m-1}p^n } } (2j-1) \sum_{\underset{2u-1 \equiv 0 \bmod p} {1\le u \le 2^{m-1}p^n-j+1 } } (2u-1) \end{align*} \begin{align*} f(2^mp^n)&=\sum_{ 1\le j \le 2^{m-1}p^n } (2j-1) (2^{m-1}p^n-j+1)^2 \\ &-2p\sum_{ 1\le k \le 2^{m-1}p^{n-1} } (2k-1) (2^{m-1}p^n-kp+\frac{p+1}{2})^2\\ &+p^2\sum_{ 1\le k \le 2^{m-1}p^{n-1} } (2k-1) \sum_{1\le \ell \le 2^{m-1}p^{n-1}-k+1 } (2\ell-1)\\ f(2^mp^n)&=\sum_{ 1\le j \le 2^{m-1}p^n } (2j-1) (2^{m-1}p^n-j+1)^2 \\ &-2p\sum_{ 1\le k \le 2^{m-1}p^{n-1} } (2k-1) (2^{m-1}p^n-kp+p-\frac{p-1}{2})^2\\ &+p^2\sum_{ 1\le k \le 2^{m-1}p^{n-1} } (2k-1) (2^{m-1}p^{n-1}-k+1)^2\\ f(2^mp^n)&=\sum_{ 1\le j \le 2^{m-1}p^n } (2j-1) (2^{m-1}p^n-j+1)^2 \\ &+2p^2(p-1)\sum_{ 1\le k \le 2^{m-1}p^{n-1} } (2k-1) (2^{m-1}p^{n-1}-k+1)\\ &-2p2^{2m-2}p^{2n-2} (\frac{p-1}{2})^2\\ &+(p^2-2p^3)\sum_{ 1\le k \le 2^{m-1}p^{n-1} } (2k-1) (2^{m-1}p^{n-1}-k+1)^2\\ \end{align*} We expand the sums on the right hand side and replace the sums of powers by their well-known closed forms, and then, after some lengthy but elementary algebric manipulations, we find: \begin{align*} f(2^mp^n)=2^mp^n(p-1)\frac{ 8^{m - 1} (p-1) p^{3 n - 2} + 2\cdot4^{m } p^{2 n - 1}- 2^{m - 1} (p-3) p^{n - 1}-1}{12} \end{align*} in particular \begin{align*} f(2^m3^n)&=2^m3^n\left(8^{m - 1} 27^{n - 1}+4^{m - 1} 9^{n - 1}-\frac{1}{6}\right) \end{align*} which clearly shows that $2^m3^n$ does not divide $f(2^m3^n)$.

Now suppose that $p>3$, then $p \equiv a \bmod 12$, whith $a= 1,5,7 \text{ or }11$.

If $a=1$, $ p-1 \equiv 0 \bmod 12$, and then $2^mp^n$ divides $f(2^mp^n)$.

If $a=5$, $ p-1 \equiv 0 \bmod 4$, and $p\equiv 2 \bmod3$ and then
\begin{align*}A&=8^{m - 1} (p-1) p^{3 n - 2} + 2\cdot4^{m } p^{2 n - 1}- 2^{m - 1} (p-3) p^{n - 1}-1 \\ &\equiv2^{m - 1} 2^{3 n - 2} +1+2^{m - 1} 2^{n - 1}-1 \pmod 3\\ &\equiv2^{m - 1} 2^{3 n - 2} +2^{m - 1} 2^{n - 1} \pmod 3\\ &\equiv2^{m - 1} 2^{n - 1}( 2^{2 n -1} +1) \pmod 3\\ &\equiv 0\pmod 3, \end{align*} and then $2^mp^n$ divides $f(2^mp^n)$.

If $a=7$ or $a=11$, $ p-1$ is not divisible by $4$ and $A$ is odd clearly then $(p-1)\cdot A$ is not divisible by $4$ hence a fortiori not by $12$ and then $2^mp^n$ does not divide $f(2^mp^n)$.

We then have shown that $2^mp^n$ divides $f(2^mp^n)$ if and only if $a=1$ or $a=5$, that is if and only if $p-1\equiv 0 \bmod 4$. End of proof.