6
$\begingroup$

I posted this question on math.SE 10 days ago and had no answer, comment or vote. If an answer is not available, I could really use a reference point as well.

For the sake of completeness, I am restating the essence of my question below, omitting details that can be found on the link above.


I am interested in the following problem:

For $n\in\mathbb{N}$, define the function $S_n:\mathbb{Z_n^*}\to\mathbb{Z_n}$ by $$ S_n(\bar a) := \bar 1 + \bar a + \bar a^2 + ...+ \bar a^{\left(ord_n(a)\right)-1}, $$ where $\mathbb{Z_n^*}$ is the set of all invertible elements of $\mathbb{Z_n}$, and $ord_n(a)$ the order of $a$ modulo $n$.

Can a characterization for the sets $$ A_n:=\{ \bar a \in \mathbb{Z_n^*} : S_n(\bar a) = \bar 0 \} $$

be found?

Now, considering the $\amalg {\mathbb{Z_n} }$ as consisting of the elements $(\bar a, n)$ where $n \in \mathbb{N}$ and $\bar a \in \mathbb{Z_n}$, we define the function $S : \mathbb{N} \to \amalg {\mathbb{Z_n} } $ such as \begin{align} S(n) = \left( \sum_{\bar a \in \mathbb{Z_n^*}} {S_n(\bar a)}, n \right)\end{align} thinking of $S(n)$ as an element of $\mathbb{Z_n}$ when there is no danger of confusion.

This bring us to the second question. Can we find (or know more about) the set \begin{align} A:= \{ n \in \mathbb{N} : S(n) \in \mathbb{Z_n^*} \}\end{align}

Thank you in advance.

$\endgroup$
3
  • 1
    $\begingroup$ For the first question, isn't $S(a)=0$ for all $a\ne1$? $\endgroup$ Mar 14, 2015 at 9:56
  • 1
    $\begingroup$ @AlexDegtyarev If n is prime, then yes, $S_n(a)=0$ for all $a\ne1$ . But if, lets say, $n=8$ then $S_n(3)=4$. $\endgroup$
    – Dosidis
    Mar 14, 2015 at 10:03
  • $\begingroup$ As a very basic observation, you have $S_n(\bar a)=0$ provided that both $a$ and $a-1$ are co-prime with $n$. $\endgroup$
    – Seva
    May 26, 2015 at 10:10

1 Answer 1

4
+25
$\begingroup$

Here is a partial answer to your first question:

A necessary condition for $S_n(\bar a)=0$ to hold is that $\gcd(a-1,n)\mid{\rm ord}_n(a)$; moreover, if $n$ is square-free, then this condition is also sufficient.

To see this, let $k:={\rm ord}_n(a)$ and $d:=\gcd(a-1,n)$, and write $a-1=db$ and $n=dm$. Then $S_n(\bar a)=0$ can be equivalently re-written as $$ 1+a+\dotsc+a^{k-1}\equiv 0\pmod{dm}; \tag{$\ast$} $$ this yields $1+a+\dotsc+a^{k-1}\equiv 0\pmod d$, and necessity follows now by observing that $a\equiv 1\pmod d$, resulting in $1+a+\dotsc+a^{k-1}\equiv k\pmod d$.

This argument also shows that, conversely, $1+a+\dotsc+a^{k-1}\equiv 0\pmod{d}$ holds whenever $d\mid k$. Since $\gcd(d,m)=1$ for $n$ square-free, to prove sufficiency it suffices to show that for such $n$, we have $1+a+\dotsc+a^{k-1}\equiv 0\pmod{m}$. This is equivalent to $m\mid\frac{a^k-1}{db}$, or $dbm\mid a^k-1$, which further splits into the two conditions $db\mid a^k-1$ and $m\mid a^k-1$ in view of $\gcd(db,m)=1$ (following from $\gcd(d,m)=\gcd(b,m)=1$). Recalling that $db=a-1$ and and that $m\mid n$ and $k={\rm ord}_n(a)$, we see that, in fact, both $db\mid a^k-1$ and $m\mid a^k-1$ hold in a trivial way.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.