Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 05-06-2020 15:21:19

adnanemohib99
Membre
Inscription : 02-06-2020
Messages : 11

la fonction indicatrice d'euler

bonjour à tous smiling smiley, aider moi à comprendre une partie de cette démonstration s'il vous plait et merci d'avance

si m et n premiers entre eux alors phi(mn) = phi(m).phi(n)

démonstration: Il s’agit de comptabiliser les nombres compris entre 1 et mn qui sont
premiers avec mn.
Tout entier naturel a situé entre 1 et mn, peut s’écrire sous la forme a = lm + r avec
0 <= l <= n − 1 et 1 <= r <= n.
Mais d’après le Lemme d’Euclide, on a pgcd(a, m) = pgcd(lm + r, m) = pgcd(r, m).
Or, par définition de la fonction d’Euler, il y a phi(m) entiers entre 1 et m − 1 qui sont
premiers avec m .
Les nombres qui sont entre 1 et mn qui sont premiers avec m sont de la forme
lm + r où r est premier avec m car pgcd(a, m) = pgcd(r, m) et 0 <= l <= n − 1.
Maintenant, il faut remarquer que pour un tel r, l # l′ ⇒ lm + r # l′m + r mod (n)
Car, en effet, si lm + r = l′m + r mod (n) alors (l − l′)m = 0 mod (n) donc l = l′ car pgcd(m, n) = 1
puisque d’après le théorème de Gauss, on aurait n|(l − l′) avec |l − l′| < n.
----------------------------------- la suite je ne la comprend pas---------------------------------------------
On en déduit que, pour chaque r=1, 2, 3, ..., n premier avec n, les nombres de la forme
lm + r avec 0 <= l <= n − 1 sont deux à deux distincts modulo n.
Donc parmi ces n nombres, il y en a phi(n) qui sont premiers avec n.
conclusion
Il y a phi(m) nombres premiers avec m
Pour chacun de ces nombres, il y en a phi(n) qui sont premiers avec n .
Donc il y a phi(m)phi(n) nombres premiers avec mn .

Hors ligne

#2 05-06-2020 16:36:16

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 7 457

Re : la fonction indicatrice d'euler

Salut,

si tu ne dis pas ce que tu ne comprends pas et à quel stade du raisonnement tu coinces, on ne peut pas deviner et donc, on ne va pas pouvoir t'aider.

Dernière modification par freddy (05-06-2020 16:36:42)


De la considération des obstacles vient l’échec, des moyens, la réussite.

Hors ligne

#3 05-06-2020 16:36:41

valoukanga
Membre
Inscription : 30-11-2019
Messages : 196

Re : la fonction indicatrice d'euler

Bonjour !

On montre dans la démonstration d'abord qu'il y a $\varphi(m)$ entiers entre $1$ et $m-1$ qui sont premiers avec $m$ (par définition). Ces entiers sont les $lm+r$ avec $r$ premier avec $m$, et ils sont tous distincts modulo $n$. Il y'en a donc $n$ modulo $n$, et $\varphi(n)$ qui sont premiers avec $n$. Ainsi, pour chaque $\varphi(m)$, tu as $\varphi(n)$ entiers, d'où le résultat.

Est-ce plus clair ?

Hors ligne

#4 05-06-2020 17:00:09

adnanemohib99
Membre
Inscription : 02-06-2020
Messages : 11

Re : la fonction indicatrice d'euler

#3 merci, je veux comprendre l'effet du fait que les entiers qui sont premiers avec m sont tous distincts modulo n sur le reste de la démonstration

Hors ligne

#5 05-06-2020 17:06:45

valoukanga
Membre
Inscription : 30-11-2019
Messages : 196

Re : la fonction indicatrice d'euler

Le fait qu'ils soient uniques modulo $n$ implique qu'il n'y en a que $n$ qui "t'intéresse". Et comme le nombre d'entiers premiers avec $n$ entre 1 et $n$ est $\varphi(n)$, tu peux conclure.

Hors ligne

#6 05-06-2020 17:11:41

adnanemohib99
Membre
Inscription : 02-06-2020
Messages : 11

Re : la fonction indicatrice d'euler

#3 merci bcccccp

Hors ligne

#7 21-01-2021 17:00:53

Tian2718
Membre
Inscription : 16-01-2021
Messages : 7

Re : la fonction indicatrice d'euler

Bonjour,
pour ma part, dans l'exercice 10, Fonction indicatrice d'Euler, je ne comprends pas la correction du 2. et notamment comment on passe de :

"Un tel nombre s'écrit [tex]p×l [/tex] avec [tex]p×l≤p^α[/tex], soit [tex]l≤p^{α−1}. [/tex]"

à : "On obtient donc [tex]ϕ(p^α)=p^{α}−p^{α−1}"[/tex]

Pourriez-vous me détailler ce passage?

Merci beaucoup!

Hors ligne

#8 21-01-2021 17:36:03

Fred
Administrateur
Inscription : 26-09-2005
Messages : 7 033

Re : la fonction indicatrice d'euler

Bonjour,

  Il y a $p^{\alpha-1}$ multiples de $p$ qui sont compris entre $1$ et $p^\alpha$. Ces nombres sont exactement les nombres compris entre $1$ et $p^\alpha$ qui ne sont pas premiers avec $p^\alpha$. Donc le nombre de nombres compris entre $1$ et $p^\alpha$ et qui sont premiers avec $p^\alpha$ est $p^{\alpha}-p^{\alpha-1}$ (c'est-à-dire le nombre total de nombres moins le nombre de ceux qui ne sont pas premiers).

F.

Hors ligne

#9 22-01-2021 10:19:45

Tian2718
Membre
Inscription : 16-01-2021
Messages : 7

Re : la fonction indicatrice d'euler

ok, merci beaucoup.

Dans la correction ce n'est pas explicitement écrit qu'il y a [tex]p^{α−1}[/tex] multiples de p qui sont compris entre 1 et [tex]p^α[/tex].

Est-ce que cela se "voit" intuitivement? Oui bien est-ce que ça se calcule ou se démontre? par récurrence?

Merci encore!

Hors ligne

#10 22-01-2021 11:03:51

Fred
Administrateur
Inscription : 26-09-2005
Messages : 7 033

Re : la fonction indicatrice d'euler

C'est presque écrit explicitement quand même quand on dit qu'un tel nombre s'écrit $p\times l$ avec $l$ un entier, $l\geq 1$ et $p\times l\leq p^\alpha$...

F.

Hors ligne

Pied de page des forums