Fonction indicatrice d'Euler

[invite705d0470]

Voilà, il y a peu de temps (hier en fait ) je me suis intéressé à la fonction indicatrice d'Euler et au théorème d'Euler (un exo dans mon livre de spé en parle, donc j'ai essayé). Cette fonction correspond au nombre ne naturels inférieurs ou égaux et premiers avec n,
Donc,

Quand au théorème d'Euler, il revient à dire que:


Je me demandais s'il était possible d'en avoir une démonstration "classique" du niveau de terminale (plutôt courte ^^, mais je n'ai pas peur des longues démo.) L'exo en question m'amène à une démo (que je posterai ce soir, là je n'ai plus le temps, dsl) un peu longue et utilisant l'ensemble des nombres inversibles mod(n).

En tant que simple élève de terminale, je ne connais pas très bien (euphémisme ^^) les structures de monoïdes, groupes, anneaux ou corps (juste lu deux trois trucs) donc je ne saisis pas toute la subtilité d'une démo utilisant l'ordre d'un ensemble de résidus modulo n (si c'est comme ça qu'on le dit, bien sûr, sinon désolé de mes erreurs). je suis néanmoins très curieux et espère que quelqu'un pourra (si j'ai la niveau) m'expliques quelques rudiments d'algèbre des structures, ne serais-ce que pour comprendre "réellement" la démo d'Euler qui utilise, je crois (ce que je ne comprends qu'à moitié, au mieux):.

Merci,
Snowey (1er post )
-----

[Seirios]

Bonjour,

Pour faire court : on sait que est inversible ssi ; de plus, l'ordre de a divise nécessairement l'ordre de (le groupe multiplicatif des éléments inversibles), c'est-à-dire . Par conséquent, .

La première assertion se démontre facilement grâce au théorème de Bezout, ce qui implique également que l'ordre de est ; la seconde assertion est le théorème de Lagrange, peut-être plus difficile à montrer (la démonstration que je connais utilise les groupes quotients).

[Seirios]

Tu peux peut-être regarder ici : http://gilles.costantini.pagesperso-...s/lagrange.pdf

[invite705d0470]

Merci beaucoup Seirios! Ne sachant pas ce qu'était je pouvais difficilement comprendre la démonstration ^^
Et je me rends compte que la démonstration guidée de mon exo est basée sur le même principe , mais sans les outils d'anneau et de corps, bien sûr !

Pour certains terminals qui voudraient voir cette démonstration avec des éléments du cours d'arithmétique vu en spé, voilà son déroulement (le lien est beacoup plus rapide, mais un peu plus compliqué):

(essai de) démonstration du théorème d'Euler

1) montrer que
Il suffit d'appliquer le théorème de Bézout, par exemple en partant de la droite:

2) on dit que a est inversible modulo (n) s'il existe un entier a' tel que . D'après ce que l'on a montré, on a alors:
On voit alors que si , et si E est l'ensemble des entiers a inversible modulo n, alors card(E)=

3) On suppose maintenant ,
a) montrons
existence: soit x=O (dans ce cas là aucun soucis), soit 0<x<n, auquel cas , et puisqu'on a aussi , alors (on peut le vérifier par l'absurde, en utilisant le théorème de Gauss et aboutir à une contradiction) et alors
unicité: Soit
Or .
L'unicité est vérifiée

b) On cherche a montrer l'équivalence: x inversible modulo n ax inversible modulo n. Il suffit en fait de montrer que avec a et n premier entre eux. (facile, donc je ne l'écris pas)

c) On nomme l'ensemble des m entiers inversibles modulo n (inférieurs à n)

Selon a), avec (définition d'une fonction bijective)

De plus, et donc, par propriété de pgcd: . On sait alors que .
On en conclut que

D'où

qui s'écrit aussi (pour ceux qui n'aiment pas les pi):


4) Conclusion:
La remarque du 2) nous permet d'affirmer que card(I)=, Or card(I)=m donc .

Du 3) on trouve que

Or x inversible modulo n , donc selon une conséquence du théorème de Gauss n est premier avec le produits des nombres avec lesquels il est premier:

L'application du théorème de Gauss nous permet alors de finir de démontrer le théorème d'Euler:



Comme quoi quelques notions peuvent simplifier la vie, pas vrai seirios !!

En fait, je n'ai pas très bien saisi ce qu'était .
Si l'on se place dans l'anneau où est la loi de composition interne additive (+) et où est la loi de composition interne multiplicative (x), et que l'on choisit la relation d'équivalence entre x et y (éléments de l'anneau) qui correspond à la relation de congruence modulo n (donc " "), alors tous les y congrus à forment la classe d'équivalence , et puisqu'il y a n différent, est la réunion de toutes les classes d'équivalences ?

[A voir en vidéo sur Futura]

[Seirios]

3) On suppose maintenant ,
a) montrons
existence: soit x=O (dans ce cas là aucun soucis), soit 0<x<n, auquel cas , et puisqu'on a aussi , alors (on peut le vérifier par l'absurde, en utilisant le théorème de Gauss et aboutir à une contradiction) et alors
unicité: Soit
Or .
L'unicité est vérifiée

Ce n'est pas vraiment clair entre ce que tu fixes et ce dont tu prouves l'existence...

Selon a), avec (définition d'une fonction bijective)

De plus, et donc, par propriété de pgcd: . On sait alors que .
On en conclut que

D'où viennent les ?

En fait, je n'ai pas très bien saisi ce qu'était .
Si l'on se place dans l'anneau où est la loi de composition interne additive (+) et où est la loi de composition interne multiplicative (x), et que l'on choisit la relation d'équivalence entre x et y (éléments de l'anneau) qui correspond à la relation de congruence modulo n (donc " "), alors tous les y congrus à forment la classe d'équivalence , et puisqu'il y a n différent, est la réunion de toutes les classes d'équivalences ?

C'est bien ça. De manière générale, si tu prends un ensemble X sur lequel tu définis une relation d'équivalence R, on définit l'ensemble X/R comme l'ensemble des classes d'équivalence sur X par R (c'est donc un ensemble d'ensembles, mais par abus langage, on condidère souvent X/R comme un sous-ensemble de X).

[invite705d0470]

D'abord, merci de me corriger, parce que je n'ai aucun moyen de vérifier que la démonstration que j'ai faite est correcte !
Les Yi sont les entiers correspondant aux aXi (puisque un seul Xi est associé à un seul Y, j'ai implicitement appelé ce nombre Yi).
Quant à l'existence, j'avoue ne pas avoir très bien su comment y répondre (il semble que je prouve l'existence de y et non pas de x). Si tu sais comment faire ...

Je comprends un peu mieux les résidus modulo n dans Z/nZ, mais qu'est ce que l'ordre d'un ensemble ?

Quoiqu'il en soit, merci de m'avoir lu et d'avoir répondu
Je pense que relire le lien m'aidera, et de toute façon je l'apprendrai l'année prochaine ^^

[Seirios]

Les Yi sont les entiers correspondant aux aXi (puisque un seul Xi est associé à un seul Y, j'ai implicitement appelé ce nombre Yi).

Dans ce cas, il te suffit dire que , ayant prouvé que f est bijective.

Quant à l'existence, j'avoue ne pas avoir très bien su comment y répondre (il semble que je prouve l'existence de y et non pas de x). Si tu sais comment faire ...

Si j'ai bien compris, tu cherches à montrer que f est bijective. Tu peux alors montrer qu'elle est injective en utilisant ton argument d'unicité, ce qui suffit puisque tu travailles sur des ensembles finis (sur des ensembles finis, une fonction est bijective ssi elle est injective ssi elle est surjective).

Je comprends un peu mieux les résidus modulo n dans Z/nZ, mais qu'est ce que l'ordre d'un ensemble ?

L'ordre correspond au cardinal du groupe fini, mais également au plus petit entier n tel que n1=0.