Indicatrice d'Euler: question annexe

[invite76e2b617]

Bonjour,

Quand je calcul: Phi(210)=210*(2-1)/2*(3-1)/3*(5-1)/5*(7-1)/7=48
48 correspond au nombre de nombres non multiples de 2,3,5,7 jusque n=210 (210=2*3*5*7)

Existe-t-il une formule pour trouver ce nombre de nombres non multiples de 2,3,5,7 mais pour une autre valeur de n?

Par le théorème des restes chinois, il me semble qu'on démontre que si on multiplie n par un entier, on peut multiplier directement le résultat par cet entier. Par exemple, pour 2*210=420 mon nombre de nombres non multiples de 2,3,5,7 est 2*48=96.

Mais comment faire pour, par exemple, 80?

La décomposition en facteurs premiers de 80 est 2^4*5 ce qui donne Phi(80)=80*(2-1)/2*(5-1)/5=32 ce qui correspond au nombre de nombres non multiples de 2 et 5 jusque 80.

Mais, ce que je voudrais, c'est le nombre de nombres non multiples de 2,3,5,7 jusque 80!

Si je 'triche' est que je mets 80 à la place de 210 dans 'Phi(210)' cela donne
80*(2-1)/2*(3-1)/3*(5-1)/5*(7-1)/7=18,285 arrondi à 18 c'est proche de la valeur réelle qui est 19 mais ce n'est pas exact et en procédant de la sorte on peut tomber sur des écarts bien plus importants pour d'autres valeurs.

A défaut de formule, auriez-vous des pistes pour résoudre ce problème?

Vous remerciant par avance pour toute réponse.
-----

[azizovsky]

Slt, les multiples de 2,3,5,7 jusqu'à 80 sont donc le nombre des multiples est , mais il y'a des multiples des deux ou des trois ou des quatres : leurs somme est
est le nombre des multiple de 2 et 3,4,5,7 qui ne se croisent pas .

donc il reste et ce que tu'as trouvé, mais pourquoi, on doit dévisé par 2 ?

[azizovsky]

annulé: , tu'es sûr que 19?

[invite76e2b617]

Pour vérifier, dans un tableur, j'ai mis les entiers de 1 à 80, en première colonne, puis j'ai calculé les modulos 2,3,5,7 dans les colonnes suivantes pour chaque valeurs et j'ai compté combien de lignes sans 1 jusque 80 et je trouve 19. J'ai vérifié Phi(210) de la même façon et je retrouve bien 48.

[A voir en vidéo sur Futura]

[Médiat]

Slt, les multiples de 2,3,5,7 jusqu'à 80 sont donc le nombre des multiples est , mais il y'a des multiples des deux ou des trois ou des quatres : leurs somme est
est le nombre des multiple de 2 et 3,4,5,7 qui ne se croisent pas .

donc il reste et ce que tu'as trouvé, mais pourquoi, on doit dévisé par 2 ?

Bonjour,

Vous comptez les multiples de 2, 3, 5, et 7 (vous trouvez 93 k), comme vous avez compté les multiples de 6, 10, 14, 15, 21 et 35 deux fois vous les soustrayez 93 - 36 = 57, mais du coup, vous avez soustrait 2 fois les multiples de 30, 42, 70 et 105, il faut donc les ajouter : 57 + 4 = 61, ce qui donne bien 19 non multiples de 2, 3, 5 ou 7.

[invite76e2b617]

Pour vérifier, dans un tableur, j'ai mis les entiers de 1 à 80, en première colonne, puis j'ai calculé les modulos 2,3,5,7 dans les colonnes suivantes pour chaque valeurs et j'ai compté combien de lignes sans 1 jusque 80 et je trouve 19. J'ai vérifié Phi(210) de la même façon et je retrouve bien 48.

Dans mon message précédent il fallait évidemment lire "j'ai compté combien de lignes sans 0 jusque 80".

Merci à Azizovsky et Médiat pour leurs réponses.

[invite76e2b617]

Une formule générale ressemblerait donc à quelque chose comme ça:


Le problème c'est que la combinatoire a un peu tendance à exploser
Avec tous les résultats en théorie des nombres, il n'y a vraiment pas quelque chose de plus "efficace" ?

[azizovsky]

Bonjour, Merci médiat la correction, l'indictrice d'Euler a donné 18, tu'as ajouter 1, car il n'est pas multiple de 2,3,5,7 ce qui donne 19,

En mathématiques, l'indicatrice d'Euler est une fonction arithmétique de la théorie des nombres, qui à tout entier naturel n non nul associe le nombre d'entiers compris entre 1 et n (inclus) et premiers avec n.

[invite76e2b617]

Pourtant il me semble être tombé sur des écarts supérieurs à 1 dans certain cas !?

Sinon, dans ma tentative trop rapide de formulation, j'ai oublié la partie n-(n/P+n/P'+n/P''+...)

[azizovsky]

Bonojur, tu peut passer par une autre théorème:

soit la factorisation canonique du nombre naturel n la somme de tous les diviseurs naturels du nombre n s'exprime alors par la formule : (Algèbre et théorie des nombres,L.Koulikov)

[invite76e2b617]

Je ne suis pas certain de bien comprendre, mais on retombe encore sur 210-192=18 et non 19, il me semble?
192=[2^5/(2-1)]*[3^1/(3-1)]*[5^2/(5-1)]*[7^1/(7-1)]

[azizovsky]

Bonjour, il faut ajouter le 1 commme avant

[invite76e2b617]

C'est bien ce qu'il me semblait, je ne comprends pas comment utiliser la formule. D'ailleurs, j'ai zappé les -1 dans les numérateurs dans mon calcul...
Je reprendrais cette question quand j'aurais les idées plus claires !
Merci quand même pour ton aide.