The sum of product pairs of integers prime to $n$

Question

For all composites $n$ take all pairs $a$, $b$ of integers relatively prime to $n$ with $a<b$ and $a+b=n$ to find the sum of all product pairs $a*b$.

(a) For $n=34$ the sum is $1*33+3*31+\dotsb+15*19=1496$. Find the remainder $r$ when divided by $34$ to get $r=0$.

(b) For $n=24$ the sum is $1*23+5*19+7*17+11*13=380$ which gives $r=20$ when divided by $24$ and $20$ divides $380$.

(c) All other $n$ have $r$ NOT dividing its sum.

Is there a way of predicting the result (a), (b), or (c) for any $n$?

Answer 1

For $1\le \ell \le n$ the number of $\ell$ prime to $n$ is given by Euler's totient-function $\varphi(n)$. Let the prime factorisation of $n=p_1^{a_1}\cdot p_2^{a_2}\dotsm p_k^{a_k}$, where $a_j$ are integers $>0$. The totient-function is given by $$\varphi(n)=p_1^{a_1-1}(p_1-1)\dotsm p_k^{a_k-1}(p_k-1)=n\prod_{p_i}\left(1-\frac1{p_i}\right)$$ Note $\varphi(n)$ is even for $n\ge3$.

These $\varphi(n)$ integers form a reduced residue system $S$ modulo $n$, and consist of all the invertible elements mod $n$. Let the reduced residue system $S=\{r_1, r_2, \dotsc , r_{\varphi(n)}\}$ be in ascending order.

Now we have an even amount of residues, for $n>2$, symmetrically placed, s.t. $r_i\equiv -(n-r_i)\equiv -r_{\varphi(n)-i+1}\pmod{n}$, where $r_i+(n-r_i)=n$. So we see that each product of two integers in $S$ that add to $n$ is given modulo $n$ by $r_i\cdot r_{\varphi(n)-i+1}\equiv -r_i^2\pmod{n}$, or equivalently $-r_{\varphi(n)-i+1}^2\pmod{n}$.

Therefore the sum required is $$-(r_1^2+r_2^2+\dotsb+r_{\varphi(n)/2}^2)\pmod{n}\tag{1}$$ that is it is the negative of the sum of quadratic residues, prime to $n$, modulo $n$.

For example: mod $24$ the quadratic residues prime to $24$ are just $1$. So $$-(1^2+5^2+7^2+11^2)=-196\equiv20\pmod{24}$$ and $$-(1+1+1+1)=-4\equiv20\pmod{24}$$

For another example: mod $34$ the quadratic residues are $1$, $9$, $13$, $15$, $19$, $21$, $25$, and $33$. So $$-(1^2+3^2+5^2+7^2+9^2+11^2+13^2+15^2)=-680\equiv0\pmod{34}$$ and $$-(1+9+25+15+13+19+33+21)=-136\equiv0\pmod{34}$$

---

A particular case is when the modulus is a prime $p>3$. The sum of the residue system mod $p$ is some multiple of $p$ and thus $\equiv0\pmod{p}$. This comes from the recipe above and the sum of the first $n$ integral squares formula $$S_n^2=\frac16n(n+1)(2n+1)\tag{2}$$ Now for $p$ a prime the reduced residue system is $S=\{r_1,r_2,\dotsc,r_{p-1}\}=\{1,2,\dotsc,\frac{p-1}{2},\frac{p+1}{2},\dotsc,p-1\}$. So $(1)$ gives \begin{align*} S_{(p-1)/2}^2=1^2+2^2+\dotsb+\left(\frac{p-1}{2}\right)^2&=\frac16\left(\frac{p-1}{2}\right)\left(\frac{p+1}{2}\right)p\\ &=\frac1{24}(p-1)(p+1)p=\frac1{24}(p-1)(p+1)p \end{align*} which as $24=2^3\cdot3$, and $p>3$, then $S_{(p-1)/2}^2\equiv0\pmod{p}$. This also implies that the sum of the quadratic residues are also $\equiv0\pmod{p}$.

For example: If $n=11$, $\varphi(11)=10$, the reduced residue system is $S=\{1,2,3,4,5,6,7,8,9,10\}$, sum up the first half of the residues squared to give $-(1^2+\dotsb+5^2)=-55\equiv0\pmod{11}$. The quadratic residues prime to $11$ are $1$, $3$, $4$, $5$, $9$, and $-(1+3+4+5+9)=-22\equiv0\pmod{11}$.

Answer 2

It seems, from numerical experiments, that the very same conjecture can be made, as for your previous question .

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*} \ 1&\le i \le \frac{n}{2}\\ &(i,n)=1 \end{align*}}i^2 $$ 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=10000$. There are $2221$ such $n$ up to $10000$.

Quadratic reciprocity is probably involved in any proof of this conjecture.

It also seems that the proportion of integers $n$ which dot not fall in case (a) tends to zero as $n$ grows to infinity.

EDIT (Oct 20th, 2018) I have found a proof for the above conjecture. It does not need Quadratic Reciprocity, it is a bit lengthy though.
The outline of the proof is to show first that, for $n \ge 3$, we have $$ g(n,2):=\sum_{\underset{(j,n)=1}{j=1}}^\frac{n}{2} j^2 = \begin{cases} & \frac{n^2}{24}\varphi(n)- \frac{n}{24}\prod_{p|n}(1-p) \text{ when } n \equiv \pm 1 \bmod 4\\ &\frac{n^2}{24}\varphi(n)+ \frac{n}{12}\prod_{p|n}(1-p) \text{ when }n \equiv 0 \bmod 4\\ & \frac{n^2}{24}\varphi(n)- \frac{n}{6}\prod_{p|n}(1-p) \text{ when } n \equiv 2 \bmod 4\end{cases} $$ where $\varphi(n)$ is the number of natural numbers smaller than $n$ and coprime to $n$ (Euler totient fucntion). This is obtained with the well known closed expression for the sum of the first consecutive squares and removing the non coprime. The above expression makes it clear that $12g(n,2)$ is always divisible by $n$. Then, with help of the above expression, we study the divisibility of $g(n,2)$ by $n$, for different cases, covering all the possibilities:

case 1: $(n,6)=1$, then $n$ divides $g(n,2)$.

case 2: $(n,6)\neq1$

case 2.1: $(n,6)\neq1$ and $n$ odd.

• case 2.1.1: There is $q$ such that $q\equiv 1 \bmod 6$ and $q|n$ then $n$ divides $g(n,2)$.
• case 2.1.2: There is no such $q$, then $n$ does not divide $g(n,2)$.

case 2.2: $n$ is even.

• case 2.2.1: $n$ has no odd prime divisor , then $n$ does not divide $g(n,2)$. Nota: this is shown for $n>2$, but this is clearly true also for $n=2$.

• case 2.2.2: $n$ has at least one odd divisor.

  • case 2.2.2.1: $\frac{n}{2}$ is odd.

    • case 2.2.2.1.1: $3$ divides $n$, then $n$ divides $g(n,2)$ if and only if there is a prime divisor $q$ of $n$ such that $q \equiv 1 \bmod 6$.

    • case 2.2.2.1.2: $3$ does not divide $n$, then $n$ divides $g(n,2)$ if and only if $n$ has more than one odd prime factor or its unique odd prime factor $q$ verify $q\equiv 1 \bmod 4$.

  • case 2.2.2.2: $\frac{n}{2}$ is even.

    • case 2.2.2.2.1: $3$ divides $n$, then $n$ divides $g(n,2)$ if and only if there is a prime divisor $q$ of $n$ such that $q \equiv 1 \bmod 6$.

    • case 2.2.2.2.2: $3$ does not divide $n$, then $n$ divides $g(n,2)$ if and only if $n$ has more than one odd prime factor or its unique odd prime factor $q$ verify $q\equiv 1 \bmod 4$.