[>] Division euclidienne

 
Exercice 1  4396  

Soit n. Établir les divisibilités suivantes:

  • (a)

    65n3+n

  • (b)

    522n+1+32n+1

  • (c)

    94n-1+6n.

 
Exercice 2  2358    CENTRALE (MP)Correction  

Pour n*, on désigne par N le nombre de diviseurs positifs de n et par P leur produit. Quelle relation existe-t-il entre n, N et P?

Solution

En associant dans P2=P×P chaque diviseur d avec celui qui lui est conjugué n/d, on obtient un produit de N termes égaux à n. Ainsi,

P2=nN.
 
Exercice 3  4404   

Déterminer les x tels que:

  • (a)

    (x-2)(x+2)

  • (b)

    (x-1)(x2+x+1).

 
Exercice 4  1187   Correction  

Résoudre dans les équations suivantes:

  • (a)

    x-1x+3

  • (b)

    x+2x2+2.

Solution

  • (a)

    x=1 n’est pas solution. Pour x1,

    x-1x+3 x+3x-1=1+4x-1
    x-1𝒟(4)={1,2,4,-1,-2,-4}.

    Ainsi,

    𝒮={2,3,5,0,-1,-3}.
  • (b)

    x=-2 n’est pas solution. Pour x-2,

    x+2x2+2 x2+2x+2=x-2+6x+2
    x+2𝒟(6)={1,2,3,6,-1,-2,-3,-6}.

    Ainsi,

    𝒮={-1,0,1,4,-3,-4,-5,-8}.
 
Exercice 5  4397   

(Équations diophantiennes)

Déterminer les couples (x,y)2 vérifiant:

  • (a)

    xy=3x+y+2

  • (b)

    x2-6x-y2-2y=4.

 
Exercice 6  1188   Correction  

Résoudre dans 2 les équations suivantes:

  • (a)

    xy=3x+2y

  • (b)

    1x+1y=15

  • (c)

    x2-y2-4x-2y=5

Solution

  • (a)

    On a

    xy=3x+2y(x-2)(y-3)=6.

    En détaillant les diviseurs de 6 possibles, on obtient

    𝒮={(3,9),(4,6),(5,5),(8,4),(1,-3),(0,0),(-1,1),(-4,2)}.
  • (b)

    Pour x,y*,

    1x+1y=155x+5y=xy(x-5)(y-5)=25.

    En détaillant les diviseurs de 25 possibles, on obtient

    𝒮={(6,30),(10,10),(30,6),(4,-20),(-20,4)}.
  • (c)

    On a

    x2-y2-4x-2y=5(x-2)2-(y+1)2=8

    et donc

    x2-y2-4x-2y=5(x-y-3)(x+y-1)=8.

    En détaillant les diviseurs de 8 possibles et sachant

    {x-y-3=ax+y-1=b{x=a+b2+2y=b-a2-1

    on obtient

    𝒮={(5,0),(5,-2),(-1,0),(-1,-2)}.
 
Exercice 7  155   

Soit A un ensemble de n+12 entiers distincts tous inférieurs ou égaux à 2n.
Montrer qu’il existe deux éléments de A tels que l’un divise l’autre.

 
Exercice 8  5964      CENTRALE (MP)Correction  

Pour n*, on note τ(n) le nombre de diviseurs positifs de n et σ(n) la somme de ceux-ci.

  • (a)

    Coder une fonction qui donne σ(n) et une autre qui donne τ(n).

  • (b)

    Déterminer n2 tel que σ(τ(n))=n.

  • (c)

    Tracer nσ(τ(n)) et n25/2n3/4 et conjecturer une inégalité.

  • (d)

    Montrer τ(n)2n.

  • (e)

    Démontrer la conjecture de la question (c).

  • (f)

    En déduire les points fixes de στ.

  • (g)

    De même trouver les points fixes de τσ.

On considère la série

n1τ2(n)n3.
  • (h)

    Montrer que cette série converge et donner une valeur approchée de S à 10-3 près.

Solution

  • (a)

    On parcourt les entiers allant de 1 à n et l’on cumule les diviseurs de n.

    def s(n):
        res = 0
        for d in range(1, n+1):
            if n % d == 0:
                res += d
        return res
    
    def t(n):
        res = 0
        for d in range(1, n+1):
            if n % d == 0:
                res += 1
        return res
    
  • (b)

    À l’aide d’une boucle while, on recherche n convenable.

    
    n = 2
    while s(t(n)) != n:
        n += 1
    print(n)
    

    On obtient n=3.

  • (c)

    On représente les deux courbes

    
    import matplotlib.pyplot as plt
    
    N = list(range(1, 21))
    plt.plot(N, [s(t(n)) for n in N])
    plt.plot(N, [2**(5/2)*n**(3/4) for n in N])
    plt.show()
    

    On observe σ(τ(n))25/2n3/4.

  • (d)

    Les diviseurs d de n vont par paires (d,n/d) et l’un des deux entiers est assurément inférieur à n. Il y a au plus n paires (d,n/d) avec dn/d. Il y a donc au plus 2n diviseurs positifs de n.

  • (e)

    Il y a au plus 2n diviseurs de n tous inférieurs à n donc

    σ(n)2nn=2n3/2.

    On en déduit

    σ(τ(n))2τ(n)3/2223/2n3/4=25/2n3/4.
  • (f)

    Pour n>210,

    n1/4>25/2 donc n>25/2n3/4>σ(τ(n)).

    Il n’y a donc pas de points fixes à στ en dehors de 1;1024

    Il suffit de rechercher les solutions dans cet intervalle pour conclure.

    n = 2
    while n <= 1024:
        if s(t(n)) == n:
            print(n)
        n += 1
    

    On obtient les valeurs 3, 4 et 12.

  • (g)

    On a

    τ(σ(n))2σ(n)221/2n3/4=23/2n3/4.

    Cette fois-ci, les solutions figurent nécessairement dans 1;26. On obtient les valeurs 2, 3 et 6.

  • (h)

    On a

    0τ2(n)n34nn3=4n2.

    Par comparaison de séries à termes positifs, la série étudiée converge.

    Le reste de rang n de cette série vérifie

    0Rn=k=n+1+τ2(k)k34k=n+1+1k24n+dtt2=4n.

    Pour n vérifiant 4/n0.510-3 (par exemple n=8 000), une valeur décimale approchée de Sn à 10-3 près répond à la question.

    def S(n):
        res = 0
        for i in range(1, n+1):
            res += t(i)**2 / i**3
        return res
    
    print(S(8000))
    

    On obtient S=2,052 à 10-3 près.

[<] Divisibilité[>] Calculs en congruence

 
Exercice 9  1189  Correction  

Soient a et b*, on note q le quotient de la division euclidienne de a-1 par b.
Déterminer pour tout n, le quotient de la division euclidienne de (abn-1) par bn+1.

Solution

a-1=bq+r avec 0r<b.
abn-1=(bq+r+1)bn-1=qbn+1+bn(r+1)-1.
Or 0bn(r+1)-1<bn+1 donc la relation ci-dessus est la division euclidienne de abn-1 par bn+1.
Le quotient de celle-ci est donc q.

 
Exercice 10  4430    

(Développement factoriel d’un entier)

  • (a)

    Montrer que pour tout n*, il existe p* et (a1,a2,,ap)p tels que

    n=k=1pakk! avec 0akk et ap0.
  • (b)

    Vérifier l’unicité de cette écriture.

[<] Division euclidienne[>] PGCD et PPCM

 
Exercice 11  1190  Correction  

Montrer que 112123+3121.

Solution

25=-1[11] donc 210=1[11] puis 2123=2120×23=(210)12×8=1×8=8[11].
35=1[11] donc 3121=3120×3=(35)24×3=1×3=3[11].
Ainsi 2123+3121=8+3=0[11] et donc 112123+3121.

 
Exercice 12  1191  Correction  

Quel est le reste de la division euclidienne de 12344321+43211234 par 7?

Solution

1234=2[7] et 23=1[7] donc 12344321=24321=24320×2=1×2=2[7].
4321=2[7] donc 43211234=21234=21233×2=1×2=2[7].
Par suite, 12344321+43211234=2+2=4[7]. Le reste cherché est 4.

 
Exercice 13  1193  Correction  

Trouver les entiers n tel que 10n2+(n+1)2+(n+3)2.

Solution

On a

n0123456789n2+(n+1)2+(n+3)20181056365

donc 10n2+(n+1)2+(n+3)2n=0 ou 4[10].

 
Exercice 14  1192   Correction  

Montrer que pour tout n:

  • (a)

    65n3+n

  • (b)

    732n+1+2n+2

  • (c)

    522n+1+32n+1

  • (d)

    1138n×54+56n×73

  • (e)

    94n-1-3n

  • (f)

    15216n-1-15n

Solution

  • (a)

    Pour n=0,1,2,3,4,5 on a n3=n[6] donc 5n3+n=6n=0[6].

  • (b)

    32n+1+2n+2=3.(32)n+4.2n=3.2n+4.2n=7.2n=0[7].

  • (c)

    22n+1+32n+1=2.(22)n+3.(32)n=2.4n+3.4n=5.4n=0[5].

  • (d)

    38n×54+56n×73=5n×9+5n×2=11×5n=0[11].

  • (e)

    4n-1-3n=(4-1)(1+4++4n-1)-3n=3(1+4++4n-1-n)
    or 1+4++4n-1-n=1++1-n=n-n=0[3] donc 94n-1-3n.

  • (f)

    16n-1-15n=(16-1)(1+16++16n-1)-15n=15(1+16++16n-1-n)
    or 1+16++16n-1-n=1++1-n=n-n=0[15] donc 15216n-1-15n.

 
Exercice 15  3679  Correction  

Montrer que si n est entier impair alors

n21[8].

Solution

On peut écrire n=2p+1 et alors

n2=(2p+1)2=4p(p+1)+1.

Puisque l’un des facteurs de p(p+1) est pair, le produit 4p(p+1) est multiple de 8 et donc

4p(p+1)+11[8].
 
Exercice 16  1194   

Soient x et y deux entiers. Établir

7x et 7y7(x2+y2).
 
Exercice 17  3680   Correction  

Soient λ,a,b et m*. On suppose λ et m premiers entre eux. Montrer

ab[m]λaλb[m].

Solution

() Si ab[m] alors m divise b-a et divise a fortiori λb-λa=λ(b-a).
() Si λaλb[m] alors m divise λ(b-a). Or m et λ sont supposés premiers entre eux donc, en vertu du théorème de Gauss, m divise b-a.

 
Exercice 18  2359     CENTRALE (MP)Correction  

Soient A la somme des chiffres de 44444444, B celle de A et enfin C celle de B.

Que vaut C?

Solution

Posons x=44444444, 44447[9], 731[9] donc 444444447[9].

Sachant x<105×4444, on a A9×5×4444=199980, B9×5+1=46 puis C4+9=13. Or CBAx[9] donc C=7.

[<] Calculs en congruence[>] Nombres premiers entre eux

 
Exercice 19  4398  

Calculer le pgcd d des entiers a=33 et b=24 et déterminer un couple (u,v) de coefficients entiers exprimant une relation de Bézout d=au+bv.

 
Exercice 20  1195  Correction  

Déterminer le pgcd et les coefficients de l’égalité de Bézout (1730-1783) des entiers a et b suivants:

  • (a)

    a=33 et b=24

  • (b)

    a=37 et b=27

  • (c)

    a=270 et b=105.

Solution

  • (a)

    pgcd(a,b)=3 et 3a-4b=3.

  • (b)

    pgcd(a,b)=1 et 11b-8a=1

  • (c)

    pgcd(a,b)=15 et 2a-5b=15

 
Exercice 21  1196  Correction  

Soient a,b,d. Montrer l’équivalence:

(u,v,au+bv=d)pgcd(a,b)d.

Solution

() Supposons d=au+bv avec u,v. pgcd(a,b)a et pgcd(a,b)b donc pgcd(a,b)au+bv=d.

() Supposons pgcd(a,b)d. On peut écrire d=kpgcd(a,b) avec k.
Par l’égalité de Bézout, il existe u0,v0 tels que

au0+bv0=pgcd(a,b)

et on a alors

d=au+bv

avec u=ku0 et v=kv0

 
Exercice 22  4405   

(Coefficients de l’égalité de Bézout)

Soient a et b deux entiers non nuls de pgcd d. Notre but est de déterminer tous les couples (u,v)2 tels que au+bv=d.

  • (a)

    Justifier l’existence d’un couple solution (u0,v0).

  • (b)

    Exprimer à partir de (u0,v0) tous les couples solutions.

 
Exercice 23  1197   Correction  

Montrer que le pgcd de 2n+4 et 3n+3 ne peut être que 1, 2, 3 ou 6.

Solution

3×(2n+4)-2×(3n+3)=6 donc pgcd(2n+4,3n+3)6.

 
Exercice 24  4399   

Soient a,b et k des entiers. Établir

ab=(a+kb)b.
 
Exercice 25  1201   Correction  

Résoudre dans 2 les systèmes:

  • (a)

    {pgcd(x,y)=5ppcm(x,y)=60

  • (b)

    {x+y=100pgcd(x,y)=10

Solution

  • (a)

    Soit (x,y) solution. pgcd(x,y)=5 donc x=5x et y=5y avec x,y premiers entre eux.
    ppcm(x,y)=5xy=60 donc xy=12 d’où

    (x,y){(1,12),(2,6),(3,4),(4,3),(6,2),(12,1)}.

    Les couples (2,6) et (6,2) sont à éliminer car 2 et 6 ne sont pas premiers entre eux.
    Finalement,

    (x,y){(5,60),(15,20),(20,15),(60,5)}.

    Inversement: ok.

    Finalement,

    𝒮={(5,60),(15,20),(20,15),(60,5)}.
  • (b)

    Soit (x,y) solution. pgcd(x,y)=10 donc x=10x et y=10y avec x,y premiers entre eux.
    x+y=10(x+y)=100 donc x+y=10.
    Sachant xy=1, il reste (x,y){(1,9),(3,7),(7,3),(9,1)} puis (x,y){(10,90),(30,70),(70,30),(90,10)}.
    Inversement: ok.

    Finalement,

    𝒮={(10,90),(30,70),(70,30),(90,10)}.
 
Exercice 26  1199   Correction  

Soient d,m. Donner une condition nécessaire et suffisante pour que le système

{pgcd(x,y)=dppcm(x,y)=m

possède un couple (x,y)2 solution.

Solution

Si le système possède une solution alors dm est une condition nécessaire.
Inversement, si dm alors x=d et y=m donne un couple (x,y)2 solution.

 
Exercice 27  1200   Correction  

Résoudre dans 2 l’équation:

pgcd(x,y)+ppcm(x,y)=x+y.

Solution

Soit (x,y)2 un couple solution. Posons δ=pgcd(x,y).
On peut écrire

x=δx et y=δy avec xy=1.

L’équation devient:

1+xy=x+y(x-1)(y-1)=0x=1 ou y=1.

Ainsi (x,y) est de la forme (δ,δk) ou (δk,δ) avec k.
Inversement, ces couples sont solutions.

 
Exercice 28  1198   

Soient a et b deux entiers naturels avec b non nul.

  • (a)

    Montrer que, si r est le reste de la division euclidienne de a par b, alors 2r-1 est le reste de la division euclidienne de 2a-1 par 2b-1.

  • (b)

    En déduire

    (2a-1)(2b-1)=2ab-1.
 
Exercice 29  4409    

(Suite de Fibonacci)

On considère la suite (φn) déterminée par

φ0=0,φ1=1etφn+2=φn+1+φn pour tout n.
  • (a)

    Vérifier que, pour tout n, φn et φn+1 sont des entiers premiers entre eux.

  • (b)

    Soit k*. Montrer

    φk+n=φkφn+1+φk-1φnpour tout n.

Soient a et b*.

  • (c)

    Établir

    φa+bφb=φaφb puis φaφb=φbφr

    r est le reste de la division euclidienne de a par b.

  • (d)

    Conclure

    φaφb=φab.

[<] PGCD et PPCM[>] Nombres premiers

 
Exercice 30  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 31  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 32  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 33  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 34  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 35  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 36  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 37  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 38  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 39  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 40  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.

[<] Nombres premiers entre eux[>] Études arithmétiques

 
Exercice 41  2653    ENTPE (MP)

Soit p un nombre premier supérieur à 5.

Montrer que p2-1 est divisible par 24.

 
Exercice 42  3209    ENTPE (MP)Correction  

Soient n2 et N la somme de n entiers impairs consécutifs. Montrer que N n’est pas un nombre premier.

Solution

Notons 2p+1 le premier nombre impair sommé. On a

N=k=0n-1(2k+2p+1)=n(n+2p)

avec n2 et n+2p2. Ainsi, N est composé.

 
Exercice 43  1219  Correction  

Montrer que les nombres suivants sont composés:

  • (a)

    4n3+6n2+4n+1 avec n*

  • (b)

    n4-n2+16 avec n.

Solution

  • (a)

    4n3+6n2+4n+1=(n+1)4-n4=((n+1)2-n2)((n+1)2+n2)=(2n+1)(2n2+2n+1).
    Cet entier est composé pour n* car 2n+12 et 2n2+2n+12.

  • (b)

    n4-n2+16=(n2+4)2-9n2=(n2-3n+4)(n2+3n+4).
    De plus, les équations n2-3n+4=0,1 ou -1 et n2+3n+4=0,1 ou -1 n’ont pas de solutions car toutes de discriminant négatif. Par conséquent, n4-n2+16 est composée.

 
Exercice 44  4402  

Soient p un nombre premier et a un entier. Montrer

paoup et a sont premiers entre eux.
 
Exercice 45  3623  Correction  

Soit n un naturel non nul. Montrer qu’il existe toujours un nombre premier strictement compris entre n et n!+2.

Solution

Considérons l’entier n!+1. Celui-ci est divisible par un nombre premier p inférieur à n!+1.
Si ce nombre premier p est aussi inférieur à n alors il divise n! (car apparaît comme l’un des facteurs de ce produit) et donc il divise aussi 1=(n!+1)-n!. Ceci est absurde et donc le nombre premier en question est au moins égal à n+1. Finalement, il est strictement compris entre n et n!+2.

 
Exercice 46  1224   Correction  

Justifier l’existence de 1 000 entiers consécutifs sans nombres premiers.

Solution

Considérons les xk=1 001!+k avec 2k1001. Ce sont 1 000 entiers consécutifs.
Pour tout 2k1001, on a k(1001)! donc kxk avec 2k<xk donc xk𝒫.

 
Exercice 47  2369     CENTRALE (MP)Correction  

On suppose que n est un entier 2 tel que 2n-1 est premier.

Montrer que n est nombre premier.

Solution

Supposons n=ab avec a,b*. On a alors

2n-1=(2a)b-1b=(2a-1)(1+2a++2a(b-1))

On a 2a-12n-1. On en déduit 2a-1=1 ou 2a-1=2n-1 ce qui implique a=1 ou a=n.

Ainsi, n ne possède que des diviseurs triviaux, il s’agit d’un nombre premier.

 
Exercice 48  1220   

Soient a et p deux nombres entiers supérieurs à 2. Montrer que, si ap-1 est un nombre premier, alors a=2 et p est premier.

 
Exercice 49  2656     MINES (MP)Correction  

Soient des entiers a>1 et n>0.
Montrer que si an+1 est premier alors n est une puissance de 2.

Solution

On peut écrire

n=2k(2p+1).

On a alors

an+1=b2p+1-(-1)2p+1=(b-(-1))k=02pbk(-1)2p-k=(b+1)c

avec b=a2k.
On en déduit que b+1an+1, or an+1 est supposé premier et b+1>1 donc b+1=an+1 puis n=2k.

 
Exercice 50  3351     X (PC)Correction  

Soient a,b{0,1} et n*.
On suppose que an+bn est un nombre premier. Montrer que n est une puissance de 2.

Solution

On peut écrire n=2k(2p+1) avec k,p et l’enjeu est d’établir p=0.
Posons α=a2k et β=b2k. On a

an+bn=α2p+1+β2p+1=α2p+1-(-β2p+1).

On peut alors factoriser par α-(-β)=α+β et puisque an+bn est un nombre premier, on en déduit que α+β=1 ou α+β=an+bn. Puisque α,β1, le cas α+β=1 est à exclure et puisque αan et βbn, le cas α+β=an+bn entraîne

α=an et β=bn.

Puisque a2, l’égalité α=an=α2p+1 entraîne p=0 et finalement n est une puissance de 2.

 
Exercice 51  4403   

(Morphisme de Frobenius)

Soit p un nombre premier.

  • (a)

    Pour tout 1k<p, montrer que le coefficient binomial (pk) est un multiple de p.

  • (b)

    En déduire que pour tous entiers a et b, (a+b)pap+bp[p].

 
Exercice 52  3682   Correction  

Soit n avec n2.

  • (a)

    On suppose que n est premier. Montrer

    k{2,,n-1},n divise (nk).
  • (b)

    Inversement, on suppose que n est composé. Montrer

    k{2,,n-1},n ne divise pas (nk).

Solution

  • (a)

    On suppose n premier. On sait

    (nk)=nk(n-1k-1)

    donc

    k(nk)=n(n-1k-1)

    ce qui permet d’affirmer que n divise l’entier k(nk). Or n est premier et donc premier avec k puisque k<n. Par le théorème de Gauss, on peut alors affirmer que n divise (nk).

  • (b)

    Supposons maintenant n composé. On peut introduire p un facteur premier de n avec p<n. Nous allons alors montrer que n ne divise par (np) ce qui permet de conclure.
    Par l’absurde, supposons que m=1n(np) soit un entier. On peut écrire

    (n-1)!=mp!(n-p)!.

    Puisque p divise n, on peut aussi écrire n=pq avec q entier et donc

    (pq-1)!=mp!(p(q-1))!.

    Dans les produits définissant (pq-1)! et (p(q-1))!, on retrouve les mêmes multiples de p, à savoir p,2p,(q-1)p. On peut donc écrire

    (pq-1)!=kaet(p(q-1))!=kb

    avec k regroupant le produit des multiples de p précédents et a et b non divisibles par p.

    La relation initiale se simplifie alors pour donner

    a=mp!b

    ce qui entraîne que a est divisible par p. C’est absurde!

 
Exercice 53  2654      MINES (MP)

Montrer qu’il existe une infinité de nombres premiers de la forme 4n-1 avec n entier.

 
Exercice 54  2657      MINES (MP)

(Nombres de Fermat)

Pour n, on introduit Fn=22n+1.

  • (a)

    On suppose n et m sont deux entiers naturels distincts. Montrer FnFm=1.

  • (b)

    Exploiter cette propriété afin de retrouver le théorème d’Euclide affirmant l’existence d’une infinité de nombres premiers.

[<] Nombres premiers[>] Valuation p-adique

 
Exercice 55  1211  

Soient a et b deux entiers relatifs. Montrer

aba2b2.
 
Exercice 56  1225  Correction  

Soit n. Montrer

nm,n=m2.

En déduire que 2 et 3

Solution

() C’est immédiat.

() Si n alors on peut écrire n=pq avec pq=1.
On a alors q2n=p2 donc np2
De plus, q2n=p2 et p2q2=1 donne p2n.
Par double divisibilité n=p2.
ni 2, ni 3 ne sont des carrés d’un entier, donc 2 et 3.

 
Exercice 57  4406   

Soient m et n deux entiers naturels non nuls premiers entre eux.

  • (a)

    Soit x un nombre rationnel. On suppose que xn est entier, montrer que x est entier.

  • (b)

    Soient a et b deux entiers non nuls tels que am=bn. Montrer qu’il existe c* tel que a=cn et b=cm.

 
Exercice 58  1214   Correction  

On divise un cercle en n arcs égaux et l’on joint les points de division de p en p jusqu’à ce que l’on revienne au point de départ. Quel est le nombre de côtés du polygone construit?

Solution

Le nombre de côté du polygone construit est le plus petit entier k* tel que nkp.
Posons δ=pgcd(n,p). On peut écrire n=δn et p=δp avec np=1.
nkpnkp c’est-à-dire nk. Ainsi k=n=n/δ.

 
Exercice 59  3669   Correction  

On étudie l’équation algébrique

(E):xn+an1xn1++a1x+a0=0

d’inconnue x réelle et où les coefficients a0,a1,,an1 sont supposés entiers.

Montrer que les solutions de (E) sont des nombres entiers ou des nombres irrationnels.

Solution

Supposons x=p/q une solution de l’équation (E) avec p et q premiers entre eux.

En réduisant au même dénominateur, on obtient

pn+an1qpn1++a1pqn1+a0qn=0.

Puisque q divise an1qpn1++a1pqn1+a0qn, on obtient que q divise pn. Or p et q sont premiers entre eux donc nécessairement q=1 et donc x=p.

Ainsi, les racines rationnelles de (E) sont des nombres entiers et cela répond à la question posée.

 
Exercice 60  1228  Correction  

Soient p𝒫 et α*. Déterminer les diviseurs positifs de pα.

Solution

Soit dDiv(pα). Notons β la plus grande puissance de p telle que pβd.
On peut écrire d=pβk avec pk.
Puisque pk et p𝒫 on a pk=1. Or kpα×1 donc, par Gauss: k1.
Par suite, d=pβ avec β. De plus, dpα donc pβpα puis βα.
Inversement: ok.

 
Exercice 61  1229   Correction  

Soient n{0,1} et n=k=1Npkαk sa décomposition en produit de facteurs premiers.

Quel est le nombre de diviseurs positifs de n?

Solution

Les diviseurs positifs de n sont les

d=k=1Npkβk

avec

1kN, 0βkαk.

Le choix des βk conduisant à des diviseurs distincts, il y a exactement k=1N(αk+1) diviseurs positifs de n.

 
Exercice 62  1227   

Soit n au moins égal à 2. Montrer que n est le produit de ses diviseurs non triviaux11 1 Dans ce sujet, on se limite aux diviseurs positifs. Les diviseurs triviaux de n sont 1 et n. si, et seulement si, n=p3 avec p nombre premier ou n=pq avec p et q deux nombres premiers distincts.

 
Exercice 63  1230   Correction  

Soit n{0,1} dont la décomposition primaire est

n=i=1Npiαi.

On note d(n) le nombre de diviseurs supérieurs ou égaux à 1 de n et σ(n) la somme de ceux-ci.
Montrer

d(n)=i=1N(αi+1)etσ(n)=i=1Npiαi+1-1pi-1.

Solution

Soit d diviseur de n.
Tout diviseur premier de d est aussi diviseur de n et c’est donc l’un des p1,,pN.
Par suite, on peut écrire d=i=1Npiβi avec βi.
piβid donc piβin d’où βiαi.
Ainsi d est de la forme d=i=1Npiβi avec pour tout i{1,,N}, 0βiαi.
Inversement, de tels nombres sont bien diviseurs de n.
Il y a autant de nombres de cette forme distincts que de choix pour les β1,,βN.Pour βi, il y a αi+1 choix possibles, au total d(n)=i=1N(αi+1).
De plus,

σ(n) =β1=0α1β2=0α2βN=0αNp1β1p2β2pNβN
=(β1=0α1p1β1)(β2=0α2p2β2)(βN=0αNpNβN).

Par sommation géométrique

σ(n)=i=1Npiαi+1-1pi-1.
 
Exercice 64  4410   

Soit n{0,1} dont la décomposition en facteurs premiers s’écrit

n=k=1rpkαk avec p1,,pr nombres premiers deux à deux distincts.

Montrer que la somme σ(n) des diviseurs positifs de n vaut

σ(n)=k=1rpkαk+1-1pk-1.
 
Exercice 65  4408   

(Théorème RSA)

Soient p et q deux nombres premiers distincts, n=pq et e un entier naturel premier avec le produit N=(p-1)(q-1).

  • (a)

    Justifier qu’il existe un entier d0 tel que ed1[(p-1)(q-1)].

  • (b)

    Montrer que xedx[n] pour tout x.

 
Exercice 66  4407   

(Triplets pythagoriciens)

On étudie l’équation (E):a2+b2=c2 d’inconnue (a,b,c)3.

Soit (a,b,c) une solution non nulle. Si d désigne le pgcd des trois entiers a, b et c, on peut simplifier l’équation par d2 et se ramener à la situation où d=1: nous supposons par la suite être dans ce contexte.

  • (a)

    Montrer que a, b et c sont deux à deux premiers entre eux.

  • (b)

    Quelles sont les congruences possibles d’un carré modulo 4? En déduire que l’une des deux valeurs a ou b est paire et l’autre impaire.

On suppose que b est la valeur paire.

  • (c)

    Montrer qu’il existe x et y entiers tels que c+a=2x2 et c-a=2y2.

  • (d)

    Quels sont les triplets (a,b,c)3 solutions de l’équation a2+b2=c2?

 
Exercice 67  4411    

(Formule d’inversion de Möbius)

Pour n*, on pose11 1 En particulier, μ(1)=1.

μ(n)={0 si n est divisible par le carré d’un nombre premier(-1)r si n est le produit de r nombres premiers deux à deux distincts.

Pour n*, on pose

s(n)=dnμ(d)

où la somme porte sur les entiers d diviseurs positifs de n.

  • (a)

    Soient p un nombre premier et α*. Calculer s(pα).

  • (b)

    Soient m et n* premiers entre eux, vérifier s(mn)=s(m)s(n).

  • (c)

    En déduire la valeur de s(n) pour tout n*.

On considère une fonction u:* et la fonction v:* définie par

v(n)=dnu(d).
  • (d)

    Soit n*. Vérifier la formule d’inversion

    u(n)=dnμ(nd)v(d).
 
Exercice 68  3681   

On note d(n) le nombre de diviseurs de n*. Montrer

1nk=1nd(k)=k=1n1k+bn

avec (bn) une suite bornée.

 
Exercice 69  3725    

(Théorème d’Aubry)

Soient N un entier strictement positif et 𝒞 le cercle d’équation x2+y2=N.

On suppose que le cercle 𝒞 possède un point (x0,y0) à coordonnées rationnelles. On introduit (x0,y0) un point à coordonnées entières obtenues par arrondis des coordonnées de (x0,y0). En étudiant, lorsque cela a un sens, l’intersection du cercle 𝒞 avec la droite joignant (x0,y0) et (x0,y0), montrer que ce cercle contient un point à coordonnées entières.

[<] Études arithmétiques[>] Petit théorème de Fermat

 
Exercice 70  5930  Correction  

Soient a,b et p un nombre premier. On suppose qu’il existe α* tel que pα divise le ppcm de a et b. Établir que pα divise a ou b.

Solution

Notons vp(n) la valuation p-adique n*:

vp(n)=max{k|pkn}.

On sait

vp(ab)=max(vp(a),vp(b)).

Si pα divise ab, alors max(vp(a),vp(b))α et donc vp(a)α ou vp(b)α. On en déduit que pα divise a ou b.

 
Exercice 71  1226   Correction  

Pour p𝒫 et n, on note vp(n) l’exposant de la plus grande puissance de p divisant n.

  • (a)

    Montrer que v2(1 000!)=994.

  • (b)

    Plus généralement, calculer vp(n!). On rappelle que

    x,pxp=x.

Solution

  • (a)

    v2(1 000!)=500+v2(500!) car 1000!=2500×500!×k avec k produit de nombres impairs.
    v2(1 000!)=500+250+125+62+31+15+7+3+1=994.

  • (b)

    En isolant les multiples de p dans le produit décrivant p!, on obtient

    vp(n!)=np+vp(np!)

    puis

    vp(n!)=np+n/pp+vp(n/pp!)

    or

    pxp=x

    avec x=n/p2 donne

    n/pp=np2

    puis finalement

    vp(n!)=np+np2++npk

    avec

    k=ln(n)ln(p).
 
Exercice 72  4412   

(Formule de Legendre)

  • (a)

    Soient p un nombre premier et n. Établir

    vp(n!)=i=1rnpi avec r=ln(n)ln(p).
  • (b)

    Application : Soient a,b. Montrer

    (2a)!(2b)!a!b!(a+b)!.
 
Exercice 73  2370      CENTRALE (MP)Correction  

On note 𝒫 l’ensemble des nombres premiers. Pour tout entier n>0, on note vp(n) l’exposant de p dans la décomposition de n en facteurs premiers. On note x la partie entière de x. On note π(x) le nombre de nombres premiers au plus égaux à x.

  • (a)

    Montrer

    vp(n!)=k=1+npk.
  • (b)

    Montrer que (2nn) divise p𝒫;p2npln(2n)ln(p).

  • (c)

    Montrer que (2nn)(2n)π(2n).

  • (d)

    Montrer que xln(x)=O(π(x)) quand x+

Solution

  • (a)

    Pour k suffisamment grand n/pk=0, la somme évoquée existe donc car elle ne comporte qu’un nombre fini de termes non nuls. n!=1×2××n, parmi les entiers allant de 1 à n, il y en a exactement n/p divisibles par p, n/p2 divisibles par p2, etc…donc

    vp(n!)=k=1+npk.
  • (b)

    On a

    (2nn)=(2n)!(n!)2.

    Pour tout p𝒫,

    vp((2n)!(n!)2)=k=1(2npk-2npk)

    or 2x-2x=0 ou 1 donc

    k=1(2npk-2npk)Card{k*|2n/pk>0}ln(2n)ln(p).

    De plus, les nombres premiers diviseurs de (2nn)=(2n)!(n!)2 sont diviseurs d’un entier inférieur à 2n (lemme d’Euclide) et sont donc eux-mêmes inférieur à 2n. Il en découle

    (2nn)p𝒫;p2npln(2n)ln(p)

    car toutes les puissances de nombres premiers intervenant dans la décomposition de (2nn) divisent p𝒫;p2npln(2n)ln(p).
    Notons qu’en fait ce produit désigne

    ppcm(1,2,,2n).
  • (c)

    On a

    (2nn)p𝒫;p2npln(2n)ln(p)p𝒫;p2npln(2n)ln(p)p𝒫;p2n(2n)=(2n)π(2n).
  • (d)

    En passant au logarithme:

    k=12nln(k)-2k=1nln(k)π(2n)ln(2n).

    À l’aide d’une comparaison intégrale on obtient

    1nln(t)dtk=1nln(k)1(n+1)ln(t)dt

    donc

    nln(n)-n+1k=1nln(k)(n+1)ln(n+1)-n

    donc

    k=1nln(k)=n+nln(n)-n+O(ln(n)).

    Par suite,

    k=12nln(k)-2k=1nln(k)=n+2nln(2n)-2n-2(nln(n)-n)+O(ln(n))

    puis

    k=12nln(k)-2k=1nln(k)n+ln(2)(2n).

    On en déduit

    2nln(2n)=n+O(π(2n)).

    Ajoutons

    xln(x)n+2x/2ln(2x/2)

    par calculs et π(x)π(2x/2) car π(x) et π(2x/2) ne différent qu’au plus d’une unité et π(x)+.
    Finalement, une certaine satisfaction.

 
Exercice 74  5689   Correction  

Soit n*. Si n=εpεp-1ε0¯ est l’espression de n en base 2 on note

s(n)=ε0++εpetv(n) la valuation de n en base 2
  • (a)

    Écrire une fonction calculant v(n) et s(n).

  • (b)

    Si n{2,,104}, vérifier numériquement que v(n)=s(n-1)-s(n)+1.

  • (c)

    Prouver que pour tout n2, v(n)=s(n-1)-s(n)+1.

  • (d)

    Calculer v(n!) en fonction de n et s(n).

  • (e)

    Soit n*. Montrer que n est une puissance de 2 si, et seulement si, (nk) est un entier pair pour tout k=1,,n-1.

Solution

  • (a)

    Tant qu’une puissance de 2 divise n, on passe à la puissance suivante:

    def v(n):
        k = 0
        p = 1
        while n % (2*p) == 0:
            k = k + 1
            p = 2 * p
        return k
    

    Pour calculer s(n), une solution récursive est possible:

    def s(n):
        if n == 0:
            return 0
        elif n % 2 == 0:
            return s(n//2)
        else:
            return 1 + s((n-1) // 2)
    
  • (b)

    On vérifie qu’aucune valeur n’échoue

    for n in range(2, 10**4+1):
        if v(n) != s(n-1) - s(n) + 1:
            print(f"Echec pour la valeur {n}")
    
  • (c)

    Posons p la valuation de n en base 2. L’écriture en base 2 de n se termine par 100¯ avec un nombre de zéro égal à p. L’écriture de n-1 commence par les mêmes chiffres mais se termine par 011¯. On en déduit s(n-1)-s(n)=p-1=v(n)-1.

  • (d)

    Pour p,q*, v(pq)=v(p)+v(q) donc

    v(n!)=k=1nv(k)=v(1)+k=2n(s(k-1)-s(k)+1)=n-s(n)
  • (e)

    Cas: n=1 ou n=2. C’est immédiat.

    Cas: n3. Soit k{1,,n-1}. On remarque

    v((nk))=v(n!)-v(k!)-v((n-k)!)=s(k)+s(n-k)-s(n)

    Si n vaut 2p, son écriture en base de 2 est de la forme 100¯ avec p chiffres 0. Pour k{1,,n-1}, les chiffres de l’écriture en base 2 de n-k sont les «  inverses  » des chiffres en base de 2 de k puisque k+(n-k)=n. En particulier, s(k)+s(n-k)=p. On a donc s(k)+s(n-k)-s(n)=p-1>0. Le coefficient binomial (nk) est pair.

    Si n n’est pas une puissance de 2, on peut écrire avec n=εpεq+1100¯. Considérons alors k=2q. On a s(k)=1 et s(n-k)=εp++εq+1 donc s(k)+s(n-k)=s(n). Par conséquent, la valuation en base 2 du coefficient binomial (nk) est nulle: c’est entier est impair.

[<] Valuation p-adique

 
Exercice 75  1222  Correction  

Soit p un nombre premier.

  • (a)

    Montrer

    k{1,2,,p-1},p(pk).
  • (b)

    En déduire que

    n,npn[p].

Solution

  • (a)

    On a

    (pk)=pk(p-1k-1)

    donc

    k(pk)=p(p-1k-1).

    Par suite, pk(pk).
    Or p est premier et k<p donc kp=1 puis p(pk) en vertu du théorème de Gauss.

  • (b)

    Par récurrence finie sur n{0,1,,p-1}
    Pour n=0: ok
    Supposons la propriété établie au rang n{0,1,,p-2}
    Par la formule du binôme

    (n+1)p=np+k=1p-1(pk)nk+1n+1[p]

    car pour 1kp-1.

    (pk)0[p].

    Récurrence établie.
    Pour tout n, il existe r{0,1,,p-1} tel que nr[p] et

    nprprn[p].
 
Exercice 76  3636  Correction  

Soit n2 un entier. On suppose

a{1,,n-1},an-11[n].

Montrer que n est un nombre premier

Solution

Pour tout a{1,,n-1}, a est premier avec n. En effet, un diviseur commun à a et n est diviseur de an-1-1 et donc de 1.
On en déduit que n est premier puisque premier avec chaque naturel strictement inférieur à lui-même.

 
Exercice 77  204   Correction  

(Nombres de Carmichael)

Soit n un entier supérieur à 2.
On suppose que n pour tout facteur premier p de n, p2 ne divise pas n mais p-1 divise n-1.
Établir

a,ana[n].

Solution

Par hypothèse, on peut écrire n=p1p2pr avec p1,,pr nombres premiers deux à deux distincts.
Soit a. Considérons i{1,,r}.
Si pi ne divise pas a, le petit théorème de Fermat assure api-11[pi].
Puisque pi-1 divise n-1, on a encore an-11[pi] et donc ana[pi]
Si pi divise a alors pi divise aussi an et donc an0a[pi].
Enfin, chaque pi divisant an-a et les pi étant deux à deux premiers entre eux, n=p1pr divise an-a et finalement ana[n].
La réciproque de ce résultat est vraie.
Ce résultat montre que le petit théorème de Fermat ne caractérise pas les nombres premiers. Les nombres non premiers satisfaisant le petit théorème de Fermat, sont les nombres de Carmichael. Le plus petit d’entre eux est 561, le suivant 1105.

 
Exercice 78  3686    

On désire établir qu’il existe une infinité de nombres premiers de la forme 4n+1. Pour cela, on raisonne par l’absurde et l’on suppose que ceux-ci sont en nombre fini. On pose N le produit de ceux-ci et l’on introduit

M=(2N)2+1.
  • (a)

    On suppose qu’il existe un facteur premier q de M de la forme 4n+3. Établir

    (2N)q-1-1[q].
  • (b)

    Conclure en exploitant le petit théorème de Fermat.



Édité le 22-11-2024

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