[<] Équations modulaires, théorème chinois [>] Algèbres

 
Exercice 1  2655  Correction  

Combien y a-t-il d’éléments inversibles dans /78?

Solution

Les inversibles dans /78 sont les classes associés aux entiers de {1,,78} qui sont premiers avec 78=2×3×13. Il suffit ensuite de dénombrer les multiples de 2,3,13 compris entre 1 et 78. On conclut qu’il y a 24 éléments inversible dans /78. On peut aussi calculer φ(78)=1×2×12=24.

 
Exercice 2  151   Correction  

Pour n*, on note φ(n) le nombre d’éléments inversibles dans (/n,×).

  • (a)

    Calculer φ(p) et φ(pα) pour p premier et α*.

  • (b)

    Soient m et n premiers entre eux.
    On considère l’application f:/mn/n×/m définie par f(x¯)=(x^,x~).
    Montrer que f est bien définie et réalise un isomorphisme d’anneaux.

  • (c)

    En déduire que φ(mn)=φ(m)φ(n).

  • (d)

    Exprimer φ(n) selon la décomposition primaire de n.

Solution

Les éléments inversibles de (/n,×) sont les éléments représentés par un nombre premier avec n.

  • (a)

    φ(p)=p-1. Être premier avec pα équivaut à être premier avec p c’est-à-dire à ne pas être divisible par p puisque p𝒫. Il y a pα-1 multiples de p compris entre 1 et pα donc φ(pα)=pα-pα-1.

  • (b)

    Si x=y[mn] alors x=y[n] et x=y[m] donc f est bien définie.
    φ(1¯)=(1^,1~) et si a=x+y/xy[mn] alors a=x+y/xy[n] donc φ est un morphisme d’anneaux.
    Si f(x¯)=f(y¯) alors x=y[m] et x=y[n] alors m,ny-x et puisque mn=1 alors mny-x donc x¯=y¯[mn].
    f est injective puis bijective par l’égalité des cardinaux.

  • (c)

    Les inversibles de /mn correspondent aux couples formés par un inversible de /n et un inversible de /m. Par suite, φ(mn)=φ(m)φ(n).

  • (d)

    Si n=i=1Npiαi alors φ(n)=i=1Npiαi-1(pi-1).

 
Exercice 3  152  Correction  

Pour n*, on note φ(n) le nombre d’éléments inversibles dans (/n,×).

Établir

a(/n)*,aφ(n)=1.

(où (/n)* désigne l’ensemble des inversibles de l’anneau /n

Solution

Soit f:xax de (/n)* vers lui-même.

Cette application est bien définie, injective et finalement bijective par cardinalité.

Ainsi,

x(/n)*x=x(/n)*ax=aφ(n)x(/n)*x

puis aφ(n)=1 car l’élément x(/n)*x est inversible.

Plus directement, on peut aussi dire que (/n)* est un groupe multiplicatif à φ(n) éléments et conclure.

 
Exercice 4  4241   

Soit a et n avec n2.

  • (a)

    On suppose a et n premiers entre eux, montrer aφ(n)1[n].

  • (b)

    On suppose an-11[n] et ad1[n] pour tout entier naturel d diviseur strict de n-1. Montrer que n est un nombre premier.

 
Exercice 5  4061   

Soient a,n au moins égaux à 2 et N=an-1. Montrer que n divise φ(N).

 
Exercice 6  2374  

Montrer que, pour tout entier n3, φ(n) est un nombre pair.

 
Exercice 7  257   Correction  

Établir

n3,φ(n)nln(2)ln(n)+ln(2).

Solution

Notons p1,,pr les facteurs premiers de n. On sait

φ(n)=n(1-1p1)(1-1p2)(1-1pr).

En ordonnant les p1,p2,,pr, on peut affirmer

1ir,pi1+i

et donc

(1-1p1)(1-1p2)(1-1pr)(1-12)(1-13)(1-11+r).

Par produit télescopique

(1-1p1)(1-1p2)(1-1pr)>1223rr+1=1r+1.

Or on a aussi

np1pr2r

et donc

rnln(2).

On en déduit

φ(n)nnln(2)+1=nln(2)n+ln(2).
 
Exercice 8  153   Correction  

Pour n*, on note φ(n) le nombre de générateurs de (/n,+).

  • (a)

    Montrer que si H est un sous-groupe de (/n,+), il existe a divisant n vérifiant H=<a¯>.

  • (b)

    Observer que si dn il existe un unique sous-groupe de (/n,+) d’ordre d.

  • (c)

    Justifier que si dn le groupe (/n,+) possède exactement φ(d) éléments d’ordre d.

  • (d)

    Montrer

    dnφ(d)=n.

Solution

  • (a)

    Soit H un sous-groupe de /n.
    Si H={0} alors H=<n>.
    Sinon, on peut introduire a=min{k*|k¯H}.
    La division euclidienne de n par a donne n=qa+r d’où r¯H puis r=0. Ainsi an.
    On a <a¯>H et par division euclidienne on montre H<a¯> d’où a=H.

  • (b)

    Si a divise n, on observe que <a¯> est de cardinal ’ordre n/a. Ainsi <n/d> est l’unique sous-groupe d’ordre d de (/n,+).

  • (c)

    Un élément d’ordre d de /n est générateur d’un sous-groupe à d éléments donc générateur de <n/d¯>. Inversement, tout générateur de <n/d¯> est élément d’ordre d de /n. Or <n/d¯> est cyclique d’ordre d donc isomorphe à /d et possède ainsi φ(d) générateurs. On peut donc affirmer que /n possède exactement φ(d) élément d’ordre d.

  • (d)

    L’ordre d’un élément de /n est cardinal d’un sous-groupe de /n et donc diviseur de n. En dénombrant /n selon l’ordre de ses éléments, on obtient

    dnφ(d)=n.
 
Exercice 9  3634   

Soit n un entier naturel non nul.

  • (a)

    Pour d diviseur positif de n, combien y a-t-il de k1;n vérifiant kn=d?

  • (b)

    En déduire

    n=dnφ(d)

    où la somme s’étend sur les diviseurs positifs de n.

 
Exercice 10  5281     Navale (MP)Correction  

On note φ la fonction indicatrice d’Euler. Soit n avec n2.

  • (a)

    Pour d un diviseur de n, montrer qu’il y a exactement φ(d) éléments d’ordre d dans le groupe (/n,+).

  • (b)

    En déduire

    n=dnφ(d)

    où la somme s’étend sur les entiers d diviseurs positifs de n.

  • (c)

    Écrire un programme employant cette formule pour calculer les valeurs de la fonction indicatrice d’Euler.

Solution

  • (a)

    Soit k1;n. L’ordre de k¯ dans /n est le plus petit entier tel que k¯=0¯, c’est-à-dire tel que k soit un multiple de n. L’ordre de k¯ apparaît donc comme le facteur qui mutliplie k pour atteindre le ppcm de k et n,

    =knk=nkn.

    L’élément k est donc d’ordre d si, et seulement si,

    kn=d avec d=nd.

    Les entiers k correspondant s’écrivent

    k=dk avec k1;d et kd=1.

    Il y en a exactement φ(d).

  • (b)

    Les ordres des éléments de (/n,+) sont tous des diviseurs de n et, en dénombrant /n par regroupement de ses éléments selon leur ordre, il vient

    n=Card(/n)=dnCard{k1;n|k¯ est d’ordre d}=dnφ(d).
  • (c)

    Une programmation récursive emploie la formule qui précède sans être (a priori ?) plus efficace qu’un simple dénombrement des entiers compris entre 1 et n premier avec n

    def phi(n):
        if n == 1:
            return 1
        S = 0
        for d in range(1,n):
            if n % d == 0:
                S = S + phi(d)
        return n - S
    
 
Exercice 11  2381    

(Déterminant de Smith)

Soit T=(ti,j)n() la matrice de coefficients

ti,j={1 si i divise j0 sinon.

Soit aussi Dn() la matrice diagonale de coefficients diagonaux φ(1),,φ(n)φ désigne la fonction indicatrice d’Euler.

  • (a)

    Exprimer le coefficient d’indice (i,j) de la matrice TtDT en fonction de ij.

  • (b)

    En déduire la valeur du déterminant de la matrice de Smith

    S=(11121n21222nn1n2nn).
 
Exercice 12  4151      CENTRALE (MP)Correction  

Dans tout ce sujet n désigne un naturel non nul.

On note φ(n) l’indicatrice d’Euler de n, Un l’ensemble des racines n-ième de l’unité et Un* l’ensemble des racines de l’unité d’ordre exactement n. Enfin, pour d*, on pose

Φd=zUd*(X-z).
  • (a)

    Écrire en Python la fonction liste(n) qui renvoie

    {k1;n|kn=1}.

    Écrire la fonction phi(n) qui renvoie φ(n) puis sumphi(n) qui renvoie

    dnφ(d).
  • (b)

    Montrer

    Xn-1=dnΦd.
  • (c)

    Justifier

    dnφ(d)=n.
  • (d)

    Montrer que Φn est un polynôme à coefficients entiers.

On pose Qn=Xn-1 et l’on choisit p,q,r des nombres premiers vérifiant

p<q<r<p+q.

On pose

n=pqr et R=QpQqQrX-1.
  • (e)

    Montrer

    Φn=QnRQpqQqrQrp.
  • (f)

    Montrer qu’il existe un polynôme S tel que

    Φn-R=XpqS.
  • (g)

    En déduire que le coefficient de Xr dans Φn est égal à -2.

Solution

  • (a)

    On commence par définir une fonction calculant le pgcd de deux entiers

    def gcd(a,b):
        if a % b == 0:  return b
        else: return gcd(b, a % b)
    def liste(n):
        L = []
        for k in range(1,n):
            if gcd(n,k) == 1: L.append(k)
        return L
    def phi(n):
        return len(liste(n))
    def sumphi(n):
        return sum(liste(n))
    
  • (b)

    Un est un groupe à n. Les éléments de ce groupe ont un ordre divisant n et pour tout d divisant n, les éléments du groupe Un d’ordre d sont exactement ceux de Ud*. On en déduit que Un est la réunion disjointe des Ud* pour d parcourant les diviseurs de n. On en déduit

    Xn-1=zUd(X-z)=dnΦd.
  • (c)

    Le polynôme Φn est de degré φ(n) car les racines de l’unité d’ordre n sont les

    e2ikπ/n avec k1;n,kn=1.

    L’identité précédente donne la relation voulue en passant celle-ci au degré.

  • (d)

    Par récurrence forte sur l’entier n1.

    La propriété est immédiate quand n=1. Supposons la propriété vérifiée jusqu’au rang n-1.

    On a

    Xn-1=dn,dnΦd×Φn.

    Le polynôme Xn-1 est à coefficients entiers et dn,dn l’est aussi. De plus, le coefficient dominant de ce dernier vaut 1. On réalisant une division euclidienne, le calcul de Φn détermine un polynôme à coefficients entiers.

  • (e)

    Les diviseurs de n sont 1,p,q,r,pq,qr,rp et n donc

    Qn=(X-1)ΦpΦqΦrΦpqΦqrΦrpΦn.

    De même

    Qpq=(X-1)ΦpΦqΦpq, etc.

    La relation demandée s’en déduit.

  • (f)

    Par ce qui précède, on peut écrire

    (Φn-R)QpqQqrQrp=R(Qn-QpqQqrQrp)

    0 n’est pas racine de QpqQqrQrp, ni de R, mais

    Qn-QpqQqrQrp=Xpq+

    On en déduit que 0 est racine de multiplicité pq de Φn-R.

  • (g)

    Puisque r<pq, le coefficient de Xr dans Φn est celui de Xr dans P. Or

    P =(Xp-1)(Xq-1)(1+X++Xr-1)
    =(1-Xp-Xq+Xp+q)(1+X++Xr-1).

    Le coefficient de Xr dans ce polynôme est -2 car p+q>r.

[<] Équations modulaires, théorème chinois [>] Algèbres



Édité le 08-11-2019

Bootstrap Bootstrap 3 - LaTeXML [LOGO] - Powered by MathJax Powered by MathJax