Somme modulaire et inverse
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$
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
-
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 -
Salut, un fait qui n'est pas trivial ( ) un bravo de moi.
Joyeux Noël. -
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$. -
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. -
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? -
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 -
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).$$ -
Bonjour noix de totos,
Oui le problème est équivalent à celui que tu proposes.
Ce problème à l'air vraiment coriace.
Al-Kashi -
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$. -
Le souci est que je ne vois pas comment tu définis $\epsilon$ dans le terme d'erreur.
Al-Kashi -
Tu veux dire que tu souhaiterais un terme d'erreur effectif en $\varepsilon$ ? Ai-je bien compris ?
-
Oui mais même dans ce cas le terme d'erreur il me semble ne serait pas majoré en valeur absolu par $p$.
-
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. -
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. -
Prendre $p=7$, $q=10$ et $q_n=4$ (donc $n=5$).
-
Merci mais ça marche dans des cas...
-
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). -
Edit
Formule vrai si $n\le q<p$ et $p=\alpha q+1$ pour un certain $\alpha$. -
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!
Catégories
- 163.1K Toutes les catégories
- 8 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
In this Discussion
Qui est en ligne 2
2 Invités