A Strange Result Of Divisibility

536 Views Asked by At

Let $p$ be a positive integer. Let $H$ be a subgroup of the multiplicative group $(\mathbb Z/p\mathbb Z)^*$.

Let $a>1$ be an integer such that $a \in H$ (more precisely, the residue class of $a$ modulo $p$ belongs to $H$). Let $c$ be an integer such that $-pc \equiv 1 \mod a$.

Prove that $(a-1) \mid \sum \limits_{h\in H} p(hc \mod a)$.

Here, $m \mod n$ means the remainder of $m$ modulo $n$.

Source : les dattes à Dattier

1

There are 1 best solutions below

7
On BEST ANSWER
  • $ \newcommand{\mymod}{\mathop{\mathtt{mod}}} $For clarity, we will write $\mymod(k,n)$ in place of $k\text{ mod }n$ to denote the remainder of $k$ modulo $n$ in the set of representatives $\{0,\cdots,n-1\}$. For future use, note that $\mymod(\cdot,\cdot)$ takes the form

    $$ \mymod(k,n) = k - n\lfloor k/n\rfloor $$

    for each positive integer $n$.

  • We identify the elements of $H \subseteq \left(\mathbb Z / p\mathbb Z\right)^{\ast}$ with their representatives in the set $\left\{0,1,\ldots,p-1\right\}$. Since $a \in H$, the mapping $h \mapsto \mathtt{mod}(ah,p) $ is a permutation on $H$.

  • Now let $S$ denote the sum in question. Then we can write

    \begin{align*} S &= \sum_{h \in H} p \mymod(hc, a) \tag{by def. of $S$} \\ &= \sum_{h \in H} p \mymod(c \mymod(ah, p), a) \tag{by permutation} \\ &= \sum_{h \in H} p \mymod(c( ah - p\lfloor ah/p\rfloor), a) \tag{by def. of $\mymod$} \\ &= \sum_{h \in H} p \mymod(\lfloor ah/p\rfloor, a). \end{align*}

    Here, the last step follows from

    $$c(ah-p\lfloor ah/p\rfloor) \equiv \lfloor ah/p \rfloor \pmod{a},$$

    which itself is an easy consequence of the assumption $-cp \equiv 1 \pmod{a}$.

  • Since $a > 1$ and $0 < h/p < 1$, it follows that $\mymod(\lfloor ah/p\rfloor, a) = \lfloor ah/p\rfloor$. Plugging this back,

    \begin{align*} S &= \sum_{h \in H} p \lfloor ah/p\rfloor \\ &= \sum_{h \in H} ah - \sum_{h \in H} \mymod(ah, p) \tag{by def. of $\mymod$} \\ &= \sum_{h \in H} ah - \sum_{h \in H} h \tag{by permutation} \\ &= (a-1)\sum_{h\in H} h. \end{align*}

    Therefore the claim follows.