[<] PGCD et PPCM [>] Nombres premiers

 
Exercice 1  4400  

Montrer que pour tout n, les entiers n, n+1 et 2n+1 sont premiers entre eux deux à deux. Que dire des entiers n2+n et 2n+1?

 
Exercice 2  1204  Correction  

Montrer que pour tout n*

  • (a)

    (n2+n)(2n+1)=1

  • (b)

    (3n2+2n)(n+1)=1

Solution

  • (a)

    n2+n=n(n+1).
    1×(2n+1)-2×n=1 donc (2n+1)n=1.
    2×(n+1)-1×(2n+1)=1 donc (2n+1)(n+1)=1
    Par produit (2n+1)(n2+n)=1.

  • (b)

    3n2+2n=n(3n+2).
    1×(n+1)-1×n=1 donc n(n+1)=1.
    3×(n+1)-1×(3n+2)=1 donc (3n+2)(n+1)=1.
    Par produit (3n2+2n)(n+1)=1.

 
Exercice 3  1202  Correction  

Soient a et b deux entiers. Montrer que a+b et ab sont premiers entre si, et seulement si, a et b le sont.

Solution

Raisonnons par double implication.

() Supposons a+b et ab premiers entre eux et calculons le pgcd d de a et b. L’entier d divise a et b et donc divise aussi a+b et ab. On en déduit que d vaut 1: les entiers a et b sont premiers entre eux.

() Supposons a et b premiers entre eux.

Méthode: On vérifie que a+b est premier avec a et avec b afin d’affirmer qu’il est alors premier avec ab.

Introduisons d le pgcd de a et a+b. L’entier d divise a et divise aussi b car b=(a+b)-a. On en déduit que d vaut 1 et donc a et a+b sont premiers entre eux. Il en est de même pour b et a+b et donc pour ab et a+b.

 
Exercice 4  1203  Correction  

Soient a,b.

  • (a)

    On suppose ab=1. Montrer que (a+b)ab=1.

  • (b)

    On revient au cas général. Calculer pgcd(a+b,ppcm(a,b)).

Solution

  • (a)

    pgcd(a,a+b)=pgcd(a,b) et pgcd(b,a+b)=pgcd(a,b)=1.
    Ainsi (a+b)a=1 et (a+b)b=1 donc (a+b)ab=1.

  • (b)

    Posons δ=pgcd(a,b). On peut écrire a=δa et b=δb avec ab=1.
    pgcd(a+b,ppcm(a,b))=δpgcd(a+b,ppcm(a,b))=δ

 
Exercice 5  1205  Correction  

Soit n*.

  • (a)

    Montrer que n+1 et 2n+1 sont premiers entre eux.

  • (b)

    En déduire

    n+1(2nn).

Solution

  • (a)

    On peut écrire 2×(n+1)1×(2n+1)=1. Par le théorème de Bézout, (n+1)(2n+1)=1.

  • (b)

    On a

    (2n+1n+1)=2n+1n+1(2nn)

    donc

    (n+1)(2n+1n+1)=(2n+1)(2nn).

    Puisque (2n+1n+1), on a

    (n+1)(2n+1)(2nn)

    or (n+1)(2n+1)=1 donc

    (n+1)(2nn).
 
Exercice 6  4401   

Soient a, b et c trois entiers avec a et c premiers entre eux.

  • (a)

    Montrer a(bc)=ab.

  • (b)

    Que dire de a(bc)?

 
Exercice 7  1208   Correction  
  • (a)

    Pour n, montrer qu’il existe un couple unique (an,bn)2 tel que

    (1+2)n=an+bn2.
  • (b)

    Calculer an2-2bn2.

  • (c)

    En déduire que an et bn sont premiers entre eux.

Solution

  • (a)

    Unicité: Si (an,bn) et (αn,βn) sont solutions alors

    an+bn2=αn+βn2

    donc

    (bn-βn)2=(αn-an).

    Si bnβn alors

    2=αn-abn-βn

    ce qui est absurde.
    On en déduit bn=βn puis an=αn.

    Existence: Par la formule du binôme de Newton,

    (1+2)n=k=0n(nk)2k.

    En séparant les termes d’indices pairs de ceux d’indices impairs, on a

    (1+2)n=an+bn2

    avec

    an=p=0n/2(n2p)2p et bn=p=0(n-1)/2(n2p+1)2p.
  • (b)

    On a

    an2-2bn2=(an+bn2)(an-bn2).

    Or en reprenant les calculs qui précèdent

    (1-2)n=an-bn2

    donc

    an2-2bn2=(1+2)n(1-2)n=(-1)n.
  • (c)

    La relation qui précède permet d’écrire

    anu+bnv=1 avec u,v.

    On en déduit que an et bn sont premiers entre eux.

 
Exercice 8  1209   Correction  

Soient a et b deux entiers relatifs premiers entre eux et d un diviseur de ab.
Montrer

!(d1,d2)2,d=d1d2,d1a et d2b.

Solution

Unicité: Si (d1,d2) est solution alors pgcd(d,a)=pgcd(d1d2,a)
Or d2a=1 car d2b et ab=1, donc pgcd(d1d2,a)=pgcd(d1,a)=d1 car d1a.
De même, d2=pgcd(d,b) d’où l’unicité.
Existence: Posons d1=pgcd(d,a) et d2=pgcd(d,b). On a d1a et d2b.
d1a et d2b donc d1d2=1 car ab=1.
d1d, d2d et d1d2=1 donc d1d2d.
Inversement: Par l’égalité de Bézout on peut écrire d1=u1d+v1a et d2=u2d+v2b donc dd1d2=Ud+v1v2ab car dab.

 
Exercice 9  1210   

On note Div(n) l’ensemble des diviseurs positifs d’un entier n.
Soient a,b deux entiers premiers entre eux. Établir la bijectivité de l’application

φ:{Div(a)×Div(b)Div(ab)(k,)k.
 
Exercice 10  3624   Correction  

Soit n. Montrer que les entiers

ai=in!+1

pour i{1,,n+1} sont deux à deux premiers entre eux.

Solution

Par l’absurde, supposons que ai et aj (avec i,j{1,,n+1}) ne soient pas premiers entre eux.
Considérons d un diviseur premier commun à ai et aj. L’entier d est diviseur de ai-aj donc de (i-j)n!.
Puisque d est premier et diviseur de i-j ou de n!, il est nécessairement inférieur à n et donc assurément diviseur de n!. Or d divise aussi ai=in!+1 et donc d divise 1.
C’est absurde.

 
Exercice 11  5734   Correction  

Soient n*. Pour q, on considère l’application

φq:{𝕌n𝕌nzzq.
  • (a)

    Soient p,q. Calculer φpφq.

  • (b)

    On suppose que n et q sont premiers entre eux. Vérifier que l’application φq est bijective.

  • (c)

    Inversement, on suppose l’application φq bijective, montrer que n et q sont premiers entre eux.

Solution

  • (a)

    Pour tout z𝕌n,

    (φpφq)(z)=φp(φq(z))=φp(zq)=(zq)p=zpq=φpq(z).

    On a donc φpφq=φpq.

  • (b)

    Supposons n et q premiers entre eux. Il existe k, tels que nk+q=1. On vérifie φqφ=φq avec

    z𝕌n,φq(z)=zq=z1-nk=z(zn)-k=z.

    On a donc φqφ=Id𝕌n. On vérifie de même φφq=Id𝕌n. On en déduit que φq est bijective (et l’application φ est sa bijection réciproque).

  • (c)

    Supposons l’application φq bijective. Puisque e2iπ/n est élément de 𝕌n, il existe z𝕌n tel que φq(z)=e2iπ/n, c’est-à-dire il existe k0;n-1 tel que

    (e2ikπ/n)q=e2iπ/nsoite2ikqπ/n=e2iπ/n.

    Par égalité de deux exponentielles imaginaires, il existe tel que

    2kqπn=2πn+2π

    et donc

    kq-n=1.

    On en déduit que k et sont premiers entre eux.

[<] PGCD et PPCM [>] Nombres premiers



Édité le 08-12-2023

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