This formula gives $8^{-1}$ (mod $n$). Is there a deeper pattern lurking here?

121 Views Asked by At

Pick $n\equiv 1$ (mod $4$) which is not a multiple of $3$ and such that $n>5$. Consider the sum $$S(n):=2\cdot\frac{n-1}2+3\cdot\frac{n-3}2+\ldots+m(m+2)+m+1,$$

where $m:=\frac{n-1}4$. For example, for $n=17$ we are considering $$2\cdot 8+3\cdot 7+4\cdot 6+5.$$

Then we can show, by expanding $$S(n)=\sum_{i=0}^{m-2}(2+i)\left(\frac{n-1}2-i\right)+m+1$$

and applying the formulas for triangular and pyramidal numbers, that in fact $$S(n)\equiv 8^{-1}(\text{mod } n),$$ as the numerator of the resulting fraction reduces to 1 (with a denominator of $8$).

(We cannot do the same for multiples of 3 because of the factor of 6 in the denominator of the pyramidal formula).

The simplicity of the final expression is a happy finding. I wonder:

1) Is there a neater explanation for it? Should we in fact expect the numerator to be 1?

2) More in general, can we pinpoint by some method other similar sums with particularly simple reductions?

For example, for $n\equiv 3$ (mod $4$) we get $S'(n)\equiv -11\cdot 2^{-5}$ (mod $n$) with $S'(n)$ the sums of pairs from $2\cdot\frac{n-1}2$ until possible without repetitions. Could we predict this, or choose to avoid this formula in behalf of another?

3) Is there some simple way of getting prime factors other than $2,3$ for the inverse of the final result, apart from adding more factors to the products (i.e., taking sums of products of $k$ numbers)?

1

There are 1 best solutions below

0
On

This is a partial answer.

Using that $$\sum_{i=0}^{N}1=N+1,\qquad \sum_{i=0}^{N}i=\frac{N(N+1)}{2},\qquad\sum_{i=0}^{N}i^2=\frac{N(N+1)(2N+1)}{6}$$ we have $$\small\begin{align}8S(n)&=8\sum_{i=0}^{m-2}(2+i)\left(\frac{n-1}{2}-i\right)+8m+8\\\\&=-8\left(\sum_{i=0}^{m-2}i^2\right)+(4n-20)\left(\sum_{i=0}^{m-2}i\right)+(8n-8)\left(\sum_{i=0}^{m-2}1\right)+8m+8 \\\\&=-8\cdot \frac{(m-2)(m-1)(2m-3)}{6}+(4n-20)\cdot\frac{(m-2)(m-1)}{2}+(8n-8)\cdot (m-2+1)+8m+8 \\\\&=-8\cdot \frac{(m-2)(m-1)(2m-3)}{6}+(16m-16)\cdot\frac{(m-2)(m-1)}{2}+32m (m-1)+8m+8 \\\\&=\frac 43m(4m^2+9m-1) \\\\&=\frac 43\cdot\frac{n-1}{4}\left(4\left(\frac{n-1}{4}\right)^2+9\cdot\frac{n-1}{4}+1\right) \\\\&=\frac{1}{12}(n-1)(n^2+7n-12) \end{align}$$

Now, integers such that $$n\equiv 1\pmod 4\quad\text{and}\quad n\not\equiv 0\pmod 3\quad \text{and}\quad n\gt 5$$ can be written as $$n=12k+1\quad\text{or}\quad n=12k+5$$ where $k$ is a positive integer, and we have

  • $8S(12k+1)=(12k+1)(12k^2+8k-1)+1\equiv 1\pmod{12k+1}$

  • $8S(12k+5)=(12k+5)(12k^2+16k+3)+1\equiv 1\pmod{12k+5}$