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

 
Exercice 1  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 2  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 3  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 4  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 5  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 6  4399   

Soient a,b et k des entiers. Établir

ab=(a+kb)b.
 
Exercice 7  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 8  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 9  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 10  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 11  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.

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



Édité le 08-11-2019

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