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 224

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 : 83

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 : 83

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

Réponse rapide

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quel est le résultat de l'opération suivante (donner le résultat en chiffres)?
vingt huit plus soixante dix-sept
Système anti-bot

Faites glisser le curseur de gauche à droite pour activer le bouton de confirmation.

Attention : Vous devez activer Javascript dans votre navigateur pour utiliser le système anti-bot.

Pied de page des forums