If $g \in (\mathbb{Z}/n\mathbb{Z})^\times$ then $\displaystyle \sum_{i=0}^{\lambda \cdot k-1} g^i \equiv 0 \pmod{n}$

56 Views Asked by At

Could someone provide a proof or a counterexample of the following statement:

Given integer $n \ge 2$.

If $g \in (\mathbb{Z}/n\mathbb{Z})^\times$ and $\text{ord}(g) = k$ then there exists a $\lambda \ge 1$ such that $\displaystyle \sum_{i=0}^{\lambda \cdot k-1} g^i \equiv 0 \pmod{n}$
Moreover, $\lambda k \le \varphi (n)$.


My Work

I was analyzing problems on this site and started asking half-baked questions that I subsequently deleted. But comments from Calvin Lin, John Omielan and lulu encouraged me to get more focused and write a better question.

I created a spreadsheet to work examples and the cell formulas

Column A            | Column B
=mod($D$1*A1,$C$1)  | =mod(B1+A2,$C$1)

are in row 2 and copied down from those two columns.

Example 1: $\lambda = 1$
$\quad$ $n = 21$ and $g = 10$:

enter image description here

Example 2: $\lambda = 1$
$\quad$ $n = 143$ and $g = 3$:

enter image description here

Example 3: $\lambda = 3$ (thanks to John Omielan)
$\quad$ $n = 15$ and $g = 4$:

enter image description here

1

There are 1 best solutions below

1
On BEST ANSWER

First, for $g \neq 1$, have

$$s = \sum_{i=0}^{k-1}g^i = \frac{g^{k}-1}{g-1} \tag{1}\label{eq1A}$$

For any integer $j \ge 0$, we get that

$$\sum_{i=jk}^{(j+1)k-1}g^{i} = \sum_{i=0}^{k-1}(g^k)^{j}g^i \equiv \sum_{i=0}^{k-1}g^i \equiv s \pmod{n} \tag{2}\label{eq2A}$$

Thus, for any integer $\lambda \ge 1$,

$$\sum_{i=0}^{\lambda k-1}g^i = \sum_{j=0}^{\lambda-1}\left(\sum_{i=jk}^{(j+1)k-1}g^{i}\right) \equiv \lambda s \pmod{n} \tag{3}\label{eq3A}$$

Note, using \eqref{eq1A}, since $g^{k} - 1 \equiv 0 \pmod{n}$, then $\lambda = \gcd(g-1,n)$ will always give $\lambda s \equiv 0 \pmod{n}$ in \eqref{eq3A}. However, this isn't necessarily the smallest value of $\lambda$ that works. That would instead be the least multiple of $s$ which is also a multiple of $n$, i.e.,

$$\lambda s = \operatorname{lcm}(s,n) \;\;\to\;\; \lambda = \frac{\operatorname{lcm}(s,n)}{s} \tag{4}\label{eq4A}$$

From $sn = \gcd(s,n)\operatorname{lcm}(s,n) \;\;\to\;\; \frac{\operatorname{lcm}(s,n)}{s} = \frac{n}{\gcd(s,n)}$, we also have $\lambda = \frac{n}{\gcd(s,n)}$. With your example #$1$, we have $s = 111111$ so $\lambda = \frac{21}{\gcd(111111,21)} = 1$, while $\gcd(g-1,n)=\gcd(9,21)=3$ instead. On the other hand, your example #$3$, Stinking Bishop's comment #$1$ one of $n = 8$ & $g = 5$, and Stinking Bishop's comment #$2$ example of $n = 9$ & $g = 4$, all have $\lambda = \frac{n}{\gcd(s,n)} = \gcd(g - 1,n)$.


Regarding the second part of your question, i.e., that $\lambda k \le \varphi(n)$, it's not always true, as the $2$ examples in Stinking Bishop's comments indicate. This is due to $\gcd(g - 1,n) \ne 1$, with $\gcd(g - 1,n) = 1$ being a sufficient condition (since $\lambda = 1$ then) as shown in Proving $\sum_{i=0}^{\phi(n)-1} a^i\equiv 0\pmod n$, where $\gcd(a,n)=\gcd(a-1,n)=1 $, from Euler's theorem. However, note it's not a necessary condition, as your example #$3$ has $\gcd(g - 1,n) = (3,15) = 3$, but $\lambda k = 3(2) = 6 \lt 8 = \varphi(15)$.