Cet article liste les identités nouvelles, intéressantes et utiles liées aux sommes de diviseurs apparaissant en théorie des nombres, c'est-à-dire les sommes d'une fonction arithmétique indexées par les diviseurs d'un nombre naturel , ou de manière équivalente, la convolution de Dirichlet d'une fonction arithmétique avec la fonction suivante :
Ces identités incluent des applications à des sommes d'une fonction arithmétique indexées seulement sur les diviseurs premiers propres de . Nous définissons également des variantes périodiques de ces sommes de diviseur par rapport au plus grand commun diviseur sous la forme
Des relations d'inversion bien connues qui permettent d'exprimer la fonction en fonction de sont fournis par la formule d'inversion de Möbius. Naturellement, certains des exemples les plus intéressants de telles identités résultent de l'étude de fonctions sommatoires d'ordre moyen d'une fonction arithmétique définie comme étant la somme des diviseurs d'une autre fonction arithmétique . Des exemples particuliers de sommes de diviseurs, impliquant des fonctions arithmétiques spéciales et des convolutions de Dirichlet spéciales de fonctions arithmétiques, peuvent être trouvées sur les pages dédiées à la fonction arithmétique, la convolution de Dirichlet, l'indicatrice d'Euler et la somme de Ramanujan.
Les identités suivantes sont la principale motivation pour créer cette page de sujets. Ces identités ne semblent pas bien être connues, ou du moins bien documentées, et sont des outils extrêmement utiles à avoir sous la main dans certaines applications. Dans ce qui suit, on suppose sont des fonctions arithmétiques données et que est la fonction sommatoire de . Un cas spécial plus courant de la première sommation ci-dessous est référencé sur la page "ordre moyen d'une fonction arithémtique".
Ces identités ne sont pas difficiles à prouver et constituent un exercice de manipulation standard d'inversion série-somme de diviseurs. Par conséquent, nous omettons leurs preuves ici.
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
In number theory, the prime omega functions and count the number of prime factors of a natural number Thereby (little omega) counts each distinct prime factor, whereas the related function (big omega) counts the total number of prime factors of honoring their multiplicity (see arithmetic function). That is, if we have a prime factorization of of the form for distinct primes (), then the respective prime omega functions are given by and . These prime factor counting functions have many important number theoretic relations.
We consider several "provably secure" hash functions that compute simple sums in a well chosen group (G,*). Security properties of such functions provably translate in a natural way to computational problems in G that are simple to define and possibly also ...