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

For all composites $$n$$ take all pairs $$a$$, $$b$$ of integers relatively prime to $$n$$ with $$a 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$$?

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}$$.

• The first attempt at a comment did NOT want to go through. Try again with : further examples could be given to confirm this for each a, b, c, – J. M. Bergot Oct 4 '18 at 18:28
• I'm not sure I get you. Your (a) and (b) are already correct, as I illustrated. I have given you a recipe to find the remainder on multiplying numbers $a\cdot b$ with $a<b$ and the property $a+b=n$ as you asked for. I have added what happens with the modulus a prime. Here's another example: It all depends on your modulus. If $n=14$, $\varphi(14)=6$, the reduced residue system is $S=\{1,3,5,9,11,13\}$, sum up the first half of the residues squared to give $-(1^2+3^2+5^2)=-35\equiv7\pmod{14}$. The quadratic residues prime to $14$ are $1$, $9$, $11$, and $-(1+9+11)=-21\equiv7\pmod{14}$. – Daniel Buck Oct 4 '18 at 22:46
• I see what you are doing, but it is still just an alternative method to find whether the particular n belongs in set (a) or (b) or (c). The challenge,which may have NO solution, is to find all elements of all three sets withOUT having to go through the laborious calculations, either my tedious method or yours a bit quicker. Take n=126 and ask, "What are the properties of 126 that immediately – J. M. Bergot Oct 5 '18 at 17:22
• I see what you are doing, but it is still just an alternative method to find whether the particular n belongs in set (a) or (b) or (c). The challenge,which may have NO solution, is to find all elements of all three sets withOUT having to go through the laborious calculations, either my tedious method or yours, a bit quicker. Take n=126 and ask, "What are the properties of 126 that immediately allow me to determine into which set I can place it?" All this could easily be another case of "It all depends what the electrons are doing in the machine to find the answer--it is unpredictable." – J. M. Bergot Oct 5 '18 at 17:28
• The thing is it all comes down to the modulus. If it is a prime, $p$, or any power of $p$ (which you might want to prove expanding on my answer) the sum gives a remainder of $0$. But for this you would need to know $p$ is a prime (or prime power) which is no easy task. Same for composites, you would need to know the quadartic residues (qrs) of $34=2\cdot17$, and then follow the above recipe, or know the qrs of $2$ and $17$ and stitch an answer together using the Chinese Remainder Theorem which is even more laborious than just using the qrs mod $34$. It all depends what you mean by 'immediately – Daniel Buck Oct 6 '18 at 14:18

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$$.

• Are you saying that success in (a) with r=0 is virtually the case as n increases? Did the machine report this finding? – J. M. Bergot Oct 9 '18 at 17:23