[>] 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.

[<] Divisibilité[>] Calculs en congruence

 
Exercice 8  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 9  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 10  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 11  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 12  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 13  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 14  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 15  1194   

Soient x et y deux entiers. Montrer

7x et 7y7x2+y2.
 
Exercice 16  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 17  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 18  4398  

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

 
Exercice 19  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 20  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 21  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 22  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 23  4399   

Soient a,b et k des entiers. Établir

ab=(a+kb)b.
 
Exercice 24  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 25  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 26  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 27  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 28  4409    

(Suite de Fibonacci)

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

φ0=0,φ1=1etn,φn+2=φn+1+φ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 29  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 30  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 31  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 32  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 33  1205  Correction  

Montrer que pour tout entier n*, n+1 et 2n+1 sont premiers entre eux.
En déduire

n+1(2nn).

Solution

2×(n+1)-1×(2n+1)=1 donc (n+1)(2n+1)=1.
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 34  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 35  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 36  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 37  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 38  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.

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

 
Exercice 39  2653    ENTPE

Soit p un nombre premier supérieur à 5. Montrer que p2-1 est divisible par 24.

 
Exercice 40  3209    ENTPECorrection  

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 41  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 42  4402  

Soient p un nombre premier et a un entier. Montrer

paoup et a sont premiers entre eux.
 
Exercice 43  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 44  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 45  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

Si n=ab avec a,b* alors

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

donc 2a-12n-1 d’où 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 est premier.

 
Exercice 46  1220   

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

 
Exercice 47  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 48  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 49  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 50  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 51  2654      MINES (MP)

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

 
Exercice 52  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 53  1211  

Soient a et b deux entiers relatifs. Montrer

aba2b2.
 
Exercice 54  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 55  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 56  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 57  3669   Correction  

On étudie l’équation algébrique

(E):xn+an-1xn-1++a1x+a0=0

d’inconnue x et où les coefficients a0,a1,,an-1 sont supposés entiers.
Montrer que les solutions réelles de (E) sont entières ou irrationnelles.

Solution

Supposons x=p/q une racine rationnelle de l’équation (E) avec p et q premiers entre eux.
En réduisant au même dénominateur, on obtient

pn+an-1qpn-1++a1pqn-1+a0qn=0.

Puisque q divise an-1qpn-1++a1pqn-1+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 entières.

 
Exercice 58  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 59  1229   Correction  

Soit n{0,1} et n=k=1Npkαk sa décomposition primaire.
Quel est le nombre de diviseurs positifs de n?

Solution

Les diviseurs positifs 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 60  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 des nombres premiers distincts.

 
Exercice 61  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 62  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 63  4408   

(Théorème RSA)

Soient p et q deux nombres premiers distincts, n=pq et e un entier naturel premier avec le produit (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 entier x.

 
Exercice 64  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 cette situation.

  • (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 pair.

  • (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 65  4411    

(Formule d’inversion de Möbius)

Pour n* on pose

μ(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.

En particulier, μ(1)=1. Enfin, pour n*, on pose11 1 La somme introduite porte sur les entiers d diviseurs positifs de n.

s(n)=dnμ(d).
  • (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 66  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 67  3725    

(Théorème d’Aubry)

Soit 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 68  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 69  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 70  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.

[<] Valuation p-adique

 
Exercice 71  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 72  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 73  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 74  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 08-11-2019

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