Annuler
connectez vous
arithmétique en post-bac
- Arithmétique dans Z - supérieur
- Exercice : le petit théorème de Fermat
- Équations différentielles : un Cours complet avec des exemples
- Généralités sur les matrices, applications linéaires, changement de base, rang d'une matrice - supérieur
- Ensemble et application Partie II
- Un best-of d'exos de probabilités (après le bac)
- Espaces vectoriels et Applications linéaires - supérieur
Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... Maths sup ArithmétiqueTopics traitant de arithmétique [tout]Lister tous les topics de mathématiques
Niveau Maths sup
La fonction indicatrice d euler
Posté par alinea (invité)
Bonsoir à tous et à toutes, j'ai un souci avec cet exercice de maths au sujet de la bijection (question 3), je ne comprends pas comment on peut faire....Si quelqu'un peut me donner un petit coup de pouce!! Merci d'avance à tous ceux qui me répondront
Soit n un entier naturel strictement supérieur à 1. On note En l'ensemble {m E [1, n], PGCD(m, n) = 1} et φ(n) le cardinal de En.
La fonction φ(n) est la fonction indicatrice d'Euler.
1) Montrer que En est inclus dans [1, n - 1 ] .
2) Evaluer φ(p) φ(p^j) pour tout p premier et tout entier naturel j supérieure ou égal à 1.
3) On suppose que m et n sont deux entiers naturels strictement supérieurs à 1 et premiers entre eux.
On considère l'application H de [0,m-1] X [0,n-1] dans [0,mn-1] qui à tout couple (a,b) de [0, m - 1] X [(0, n - 1] associe le reste de la division euclidienne de an + bm par mn.
a) Montrer que H est une application bijective de [0, m - 1] X [0, n - 1] dans [0, mn - 1].
b) Montrer que la restriction de H à Em x En est une bijection de Em X En dans Emn.
c) En déduire une relation entre φ(mn), φ(m) et φ(n).
Bonsoir alinea
On remarque que Card([0, m - 1] X [0, n - 1])=Card([0, mn - 1])=mn.
Ainsi, pour montrer que H est bijective, il suffit de montrer H est par exemple injective.
Soit donc (a,b) et (a',b') tels que H(a,b)=H(a',b')
on a donc an+bm 
a'n+b'm [mn], mn divise(a-a')n+(b-b')m.
En particulier m divise (a-a')n+(b-b')m d'où m divise (a-a')n. Or m et n sont premiers entre eux d'où m divise a-a' (par le théorème de Gauss).
Mais a et a' sont dans [0, m - 1], donc a-a' est dans [-(m-1),(m-1)]. Or le seul entier contenu dans cet ensemble qui est divisible par m est 0, d'où a=a'.
Par un raisonnement analogue, on a b=b' et H est alors injective donc bijective d'après ce qu'on a dit.
Voilà
Kaiser
Posté par alinea (invité)La fonction indicatrice d euler
Merci de m'avoir répondu!!! C'est très gentil
Pour la question suivante,je pars du même principe: étant donné que H est injective sur [0,m-1] X [0,n-1] elle l'est aussi sur En x Em. Mais je ne comprends pas pourquoi si l'ensemble de départ est En x Em, on obtient un ensemble d'arrivée Emn....
Posté par flopiflopa (invité)re : La fonction indicatrice d euler
oula ca m'a l'air bien compliqué tt ca, bonne chance alinea 
si a est premier à m et que b est premier à n alors tu dois prouver que an+bm est premier à mn .Supposons que p premier divise an+bm et mn, comme p diviseur premier de mn il divise m ou n seulement (car (m,n)=1) s'il divise m
(par exemple) alors il divise an donc a d'où absurde ! Déjà ton application va de EnxEm dans Emn.
Récirpoquement si x est dans Enm reste à voir qu'il est de la forme an+bm Bezout devrait aider !
lolo
Bonsoir.
La formule est vraie si m et n sont premiers entre eux.
On montre facilement que est le cardinal de
. (ensemble des éléments inversibles de
)
Par conséquent, est le cardinal de
.
Si m et n sont premiers entre eux, le lemme chinois dit que , ce qui implique la formule voulue.
Ah merci beaucoup ! J'ai un DM dessus !
D'ailleurs à propos de cet ensemble des éléments inversibles de Z/nZ, j'aurais une petite question :
Soit w un élément appartenant à cet ensemble.
Comment je pourrais montrer que l'application qui à tout élément x de cet ensemble associe le reste de la division euclidienne de wx par n est bijective ?
Ensuite, je dois montrer que w^
(n) est congru à 1 modulo n et je ne sais vraiment pas quoi faire x) Si vous pouviez m'indiquer, ce serait génial...