Forum de mathématiques - Bibm@th.net

Karine

Invité

Exercice fonction d'euler

Bonjour je suis en train de faire un exercice fameux dit de fonction d'euler .
https://www.bibmath.net/ressources/just … php?id=722
Je suis bloqué dans deux passages.
Pour le corrigé de la question 6.1 , comment on a montré que l et n sont premiers entre eux ?
Pour la dernière question ،pourquoi les ensembles Ad forment une partition dans {1,,,,n} ?
Merci.

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 352

Re : Exercice fonction d'euler

Bonjour,

  Pour 6.1, il y a une erreur. C'est $l$ et $n/d$ qui sont premiers entre eux (ce qu'on utilise d'ailleurs dans la suite de l'exercice). Cela vient d'une propriété du pgcd. Si $a\wedge b=d$, alors on peut écrire $a=da'$ et $b=db'$ avec $a'\wedge b'=1.$
Pour la dernière question, le pgcd de $k$ et de $n$ est forcément un entier $d$ qui est un diviseur de $n$, non?
Ce qui prouve que la réunion des $A_d$ est égale à $\{1,\dots,n\}.$

F.

Glozi

Invité

Re : Exercice fonction d'euler

Bonjour,
Effectivement il me semble qu'il y a une erreur dans le corrigé, si $n=6$, $d=2$ et $k=4$ alors $k\wedge n = d$, donc $k\in A_2$. Pourtant $k=d\times l$ avec $l=2$ et on n'a évidemment pas $l\wedge n=1$.
En revanche le corrigé est presque exact, car on peut dire :
$k\in A_d \Leftrightarrow \exists 1\leq l\leq n/d,\ l\wedge (n/d) = 1 \text{ et }  k=dl.$
Pour le sens $\Rightarrow$ si $k\in A_d$ alors $k\wedge n =d$ donc $d$ divise $k$ et donc $k=dl$ pour un certain entier $l$. Par la relation de Bézout, on a $u,v\in \mathbb{Z}$ tels que $ku+nv = d$ soit $dlu + d(n/d)v=d$ en divisant par $d$ (et aussi en remarquant que $n/d$ est bien un entier) alors par le théorème de Bézout on voit que $l$ et $n/d$ sont premiers entre eux. De plus, comme $1\leq k\leq n$ alors $l=k/d$ est bien compris entre $1$ et $n/d$.

Pour le sens $\Leftarrow$, supposons que $1\leq l\leq n/d$ tel que $l\wedge (n/d)=1$. Posons $k=dl$. On a bien sûr $1\leq k \leq n$, reste à voir que $k\wedge n = d$. Posons $x= k\wedge n$. On a $d|k$ car $k=dl$ et $d|n$ par définition de $n$ donc $d|x$. Maintenant, $l\wedge (n/d)=1$ donc on a $u,v$ tels que $lu+(n/d)v=1$ en mutlipliant par $d$ on trouve $ku+nv = d$, cela montre que $x|d$ et donc $x=d$.

Pour la dernière question, on dispose de sacs vides $(A_d)_{d|n}$, un sac pour chaque diviseur de $n$. On va remplir ces sacs avec les entiers de $1$ à $n$. On prend un entier $i\in \{1,\dots, n\}$ on calcule le pgcd $i\wedge n$ il s'agit forcément d'un diviseur de $n$. On met $i$ dans le sac correspondant et on passe à l'entier suivant. À la fin on voit bien que chaque entier $i\in \{1,\dots,n\}$ a bien été mis dans un et un seul sac. C'est pourquoi on trouve une partition.
De manière plus formelle, il suffit de montrer que les $A_d$ sont deux à deux disjoints, et que leur union vaut bien $\{1,\dots, n\}$.

Bonne journée

Karine

Invité

Re : Exercice fonction d'euler

Bonjour, pour la première question,je pense que l'implication directe suffit, pourquoi la réciproque ??

Glozi

Invité

Re : Exercice fonction d'euler

Bonjour,
L'objectif est de montrer que $A_d$ est en bijection avec $\{1\leq l\leq n/d\ | l\wedge (n/d)=1\}$, ensemble dont le cardinal est par définition $\varphi(n/d)$. Pour ce faire on considère l'application $A_d \to \{1\leq l\leq n/d\ | l\wedge (n/d)=1\}, k \mapsto k/d$. Le sens $\Rightarrow$ montre simplement que cette application est bien définie (et c'est évidemment bien une injection). Le sens $\Leftarrow$ sert à montrer que cette application est bien surjective.
Bonne journée