Somme modulaire et inverse

Al-Kashi
Al-Kashi
dans Arithmétique
Bonsoir
Voici un petit exercice que je vous propose.

$p$ et $q$ étant deux entiers premiers entre eux. Déterminer : $$\sum\limits_ {z=0}^{q^{-1}}(qz)_p$$ où $(qz)_p$ représente le reste de $qz$ par $p$ et $0<q^{-1}<p$ l'inverse de $q$ modulo $p$

Réponses

  • Al-Kashi
    Al-Kashi
    Bonjour,

    Plus précisément prouver que:

    $$\sum\limits_ {z=0}^{q^{-1}}(qz)_p=\dfrac{(q^{-1}-1)(p+1)}{2}+1$$

    Al-Kashi
  • Tonm
    Tonm
    Salut, un fait qui n'est pas trivial ( ) un bravo de moi.


    Joyeux Noël.
  • jandri
    jandri
    Merci pour ce petit exercice. C'est très simple à démontrer si on pense à poser $y=q^{-1}-z$ et à calculer $2S$.

    Si $(qz)_p\geq2$ et $(1-qz)_p\geq2$ alors $(qz)_p+(1-qz)_p=p+1$.
  • Al-Kashi
    Al-Kashi
    @jandri (tu)

    En attendant je sèche toujours sur cette somme dans le cas général.

    Al-Kashi
  • Fin de partie
    Fin de partie
    Si on calcule:

    $\begin{align} 2\sum\limits_ {z=0}^{q^{-1}}qz&=2q\sum\limits_ {z=1}^{q^{-1}-1}z+2qq^{-1}\\
    &=q(q^{-1}-1)q^{-1}+2qq^{-1}
    \end{align}$

    modulo $p$ cette somme vaut donc, sauf erreur:

    $q^{-1}+1$

    cette somme vaut donc $q^{-1}+1+kp$ pour un certain $k$ entier.
  • jandri
    jandri
    Al-Kashi écrivait:
    > En attendant je sèche toujours sur cette somme dans le cas général.


    Qu'est-ce que tu veux dire par le cas général?
  • Al-Kashi
    Al-Kashi
    Bonjour Jandri,

    Le cas général consiste à déterminer le résultat de $$\sum\limits_ {z=0}^{r}(qz)_p$$
    Pour $r$ quelconque.

    Il s'avère que dans la pratique ce genre de somme intervient avec un dénominateur valant $p$. Une erreur absolue de l'ordre de $p$ est donc tolérable.

    Je suis sur quelques pistes mais le terme d'erreur dépasse $p$ dans certains cas.

    Pour finir je cherche à résoudre ce problème car celui-ci permet de donner une formule exacte pour le nombre de solutions entières de $ax+by+cz=n$

    Al-Kashi
  • noix de totos
    noix de totos
    Si je comprends bien, tu cherches
    $$p\sum_{k=0}^r \left \{ \frac{kq}{p} \right \}$$
    où $0 \leqslant r < p$ et $\{ x\}$ désigne la partie fractionnaire de $x$.

    Si oui, à ma connaissance, il n'y a pas de formule "close" pour ce type de somme incomplète en toute généralité. En revanche, en utilisant des résultats connus, on devrait pouvoir montrer que
    $$p \sum_{k=0}^r \left \{ \frac{kq}{p} \right \} = \tfrac{1}{2} r p + O_{\varepsilon, q,p} \left( pr^\varepsilon \right).$$
  • Al-Kashi
    Al-Kashi
    Bonjour noix de totos,

    Oui le problème est équivalent à celui que tu proposes.
    Ce problème à l'air vraiment coriace.

    Al-Kashi
  • noix de totos
    noix de totos
    L'estimation indiquée te satisfait-elle ?

    Edit : j'ai supprimé les termes inutiles. De même, inutile de faire débuter cette somme à $k=0$.
  • Al-Kashi
    Al-Kashi
    Le souci est que je ne vois pas comment tu définis $\epsilon$ dans le terme d'erreur.

    Al-Kashi
  • noix de totos
    noix de totos
    Tu veux dire que tu souhaiterais un terme d'erreur effectif en $\varepsilon$ ? Ai-je bien compris ?
  • Al-Kashi
    Al-Kashi
    Oui mais même dans ce cas le terme d'erreur il me semble ne serait pas majoré en valeur absolu par $p$.
  • noix de totos
    noix de totos
    Avoir une constante effective en $\varepsilon$ est une chose assez délicate, car le théorème utilisé ici est difficile. De plus, c'est surtout utile si tu veux ensuite sommer ce résultat sur $r$.

    Quant au terme d'erreur, il me semble difficile à améliorer : en fait, un terme en $\ll p \times r^{o(1)}$ est plutôt une bonne estimation dans ce problème.
  • Tonm
    Tonm
    Bonjour, mais ça semble 'simple' si $q_n$ est tel que $(q_nq)_p=n$, $n\le p$ et $q_n $ aussi $$ \sum_{z=1}^{q_n}(qz)_p=\dfrac{(q_n-1)(p+n)}{2}+n.\qquad (?)
    $$ Edit due à noix de toto.
  • noix de totos
    noix de totos
    Prendre $p=7$, $q=10$ et $q_n=4$ (donc $n=5$).
  • Tonm
    Tonm
    Merci mais ça marche dans des cas...
  • noix de totos
    noix de totos
    Certes, mais il faudrait cerner ces cas (par exemple, on peut exclure les cas où l'entier $(q_n-1)(p+n)$ n'est pas pair).

    De plus, je le répète, en toute généralité, il n'y a pas de formule "close" pour les sommes incomplètes de telles parties fractionnaires. En revanche, pour les sommes complètes, il existe des résultats dans la littérature (par exemple : Kubert).
  • Tonm
    Tonm
    Edit
    Formule vrai si $n\le q<p$ et $p=\alpha q+1$ pour un certain $\alpha$.
  • Al-Kashi
    Al-Kashi
    Il est possible d'établir certaines formules pour des cas particuliers, mais le cas général comme l'a précisé noix de totos doit difficilement avoir une formule close.

    Al-Kashi
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 29

JLapinLP2Thierry Pomadedekind93diegaumanuzeste +22 Invités