Indicatrice euler

[fatal_error]

Bonjour à tous,

voilà, on a commencé l'arithmétique et déjà, j'ai des problèmes de compréhension :marteau:

Un théorême énoncé dit :

Bon, du coup, je teste avec n=12
Avec la définition de l'indicateur d'euler :
1,2,3,4,6 et 12 divise 12, du coup

Avec le théorême précédent :

et donc

Ou se situe mon erreur?
mici a vous

[SimonB]

L'indicatrice d'Euler, c'est le nombre d'entiers premiers avec l'entier considéré, pas le nombre d'entiers qui ne divisent pas l'entier considéré !

C'est là qu'est l'erreur. Refais les calculs en te rappelant de ça, et tout marche :happy2:

[fatal_error]

Ah oui d'accord,
bon, je vais détailler parce que ca rentre toujours pas :marteau:

les nombres premiers avec 12:
1,5,7,11
2 a deux diviseurs communs avec 12(1,2)
3 idem(1,3)
4 en a 3 (1,2,4)
6 en a 3(1,2,3)
8 en a 3(1,2,4)
9 en a 2(1,3)
10 en a 2(1,2)

Donc

Maintenant a l'aide du théorême,

et on a donc ...

Edit : il ne faut apparemment pas compter 1, conséquemment, on garde 1,5,7,11
et dans le deuxieme cas, d'ou on a bien

[Mathusalem]

Il faut compter le un dans ta reponse

Phi(n) = nombre de "nombres" premiers avec n
Phi(p) si p est premier = p-1 (tous les nombres sauf p, donc un)


Apres pour les proprietes quand tu as des multiples, j'ai oublie

Si ca t'interesse, je peux essayer de te trouver ca et faire la demonstration

Bonne chance

EDIT :
Toujours que, ce qui t'interesse au final, c'est de decomposer tout chiffre en
etc en facteur de nombre premiers

Et tu as apres une formule qui te dit (genre)
phi( = (1-a/2)(1-b/3)(1-c/5) .... C'est pas exactement ca... parce que forcement ca doit etre plus grand que 1 et mon calcul l'est pas mais ca a la meme gueule

[leon1789]

est le nombre d'entiers premiers avec n, et compris entre 1 et n.

(sans convention)
etc.

[fatal_error]

Ok, merci pour ces précisions à vous deux.

Mais si je prends par exemple
alors on a 1,3 qui sont premiers avec 4 et donc
De même 1,5 sont premiers avec 6 et \phi(6)=2
De plus donc a partir de la

Or on avait

[leon1789]

Le théorème est en fait !!

[AL-kashi23]

Et avec cette propriété, il n'y a plus aucun problème ! (N'oublie pas de compter n comme diviseur de n )

[Mathusalem]

Je ne sais pas d'ou tu tiens la formule, je n'ai pas souvenir d'avoir vu cette formule sous cet angle. Regarde bien si l'erreur ne vient pas du fait que 4 et 6 ne sont pas premiers entre eux (je ne sais pas par quel calcul tu passes )
Toujours est-il que l'on peut se reposer sur les definitions suivantes.
1. soit n dans N, avec n premier alors
= n-1
2. Soit p premier dans N, et k dans N*, alors
= 2 dans N avec n = decomposes en facteurs de nombres premiers = Produits des (donc tous les sont premiers entre eux)
Alors par combinaison de 2 et 3, tu as que : = Le produit des = n * produit

En rebondissant sur ton exemple du
12 =


Tu peux donc pour n'importe quel nombre te reposer sur cette formule et trouver

C'est les proprietes que j'ai en tete, il y en a surement d'autres.

Pour ton probleme de l'incoherence, en y repensant , je crois savoir ou es ton probleme : Ca n'a rien a voir avec le fait que 4 ou 6 sont premiers entre eux comme je l'avais suggere, mais que :
Quand on prend La reponse nous dit combien de nombres sont premiers a n, 1 y compris

Alors que ta formule prends la somme des individuelle des diviseurs d de n. Si ma memoire est bonne, on ne considere pas 1 comme un diviseur. Du coup dans ta somme, tu as fais un "+1" de trop en comptant 1 comme diviseur d.

Donc pour recapituler : L'indicatrice montre le nombres de chiffres premiers a n, 1 y compris
1 n'est pas considere comme un diviseur de n.

J'espere que ca resout ton probleme et que tout est plus clair

Bonne chance

[Luc]

Salut,

Pour ton probleme de l'incoherence, en y repensant , je crois savoir ou es ton probleme :
Quand on prend La reponse nous dit combien de nombres sont premiers a n, 1 y compris

Alors que ta formule prends la somme des individuelle des diviseurs d de n.

En fait, la formule dont fatal_error parlait était , qui est quand même assez incroyable!

On peut la démontrer en factorisant par un produit de polynômes cyclotomiques, et en passant au degré.

EDIT: Le d-ième polynôme cyclotomique est , de degré

[leon1789]

PS: Le d-ième polynôme cyclotomique est , de degré

impossible : Le d-ième polynôme cyclotomique est irréductible sur Z.

La bonne formule est

[Luc]

Oui excuse moi, je voulais dire au lieu de , j'ai corrigé sur mon post :briques:

[fatal_error]

hum, merci a vous tous, quant a la formule, c'était bel et bien une erreur du poly!!!
Bon si j'applique tes conseils Al-Kashi123,

Achik achik achik!!

[abcd22]

Bonjour,

On peut la démontrer en factorisant par un produit de polynômes cyclotomiques, et en passant au degré.

Dit plus simplement, on regroupe les éléments de Z/nZ suivant leur ordre, il suffit de montrer que pour tout diviseur d de n, il y a éléments d'ordre d dans Z/nZ.

PS : c'est l'indicatrice d'Euler.

[fatal_error]

Erf encore une boulette du poly...
De toute façon, l'arithmétique ca a l'air sympa je vais essayer de trouver un petit livre dessus...

[Mathusalem]

Si tu trouves ca vraiment sympa :
C'est une extension de l'arithmetique modulo. Une fois que tu as assimile ca, tu peux t'attaquer a la methode de cryptage de RSA (le truc avec les cles de cryptage qui sont multiples de 2 nombres premiers enormes). Son fondement se trouve dans l'arithmetique modulo, et il y a une belle utilisation de l'indactrice au beau milieu de l'algorithme :)

A+