Pour trouver l'inverse de 29 modulo 53, nous cherchons un entier 
𝑥
x tel que :

29
×
𝑥
≡
1
(
m
o
d
53
)
29×x≡1(mod53)

Méthode : Algorithme d'Euclide étendu
Nous utilisons l'algorithme d'Euclide étendu pour trouver 
𝑥
x.

Étape 1 : Application de l'algorithme d'Euclide
Nous cherchons les coefficients de Bézout 
𝑥
x et 
𝑦
y tels que :

29
𝑥
+
53
𝑦
=
1
29x+53y=1

Calculons les restes successifs :

53
=
1
×
29
+
24
53=1×29+24
29
=
1
×
24
+
5
29=1×24+5
24
=
4
×
5
+
4
24=4×5+4
5
=
1
×
4
+
1
5=1×4+1
4
=
4
×
1
+
0
4=4×1+0

Le PGCD est 1, donc l'inverse existe.

Étape 2 : Remontée pour exprimer 1 comme combinaison linéaire
En remontant les calculs :

1
=
5
−
1
×
4
1=5−1×4
4
=
24
−
4
×
5
4=24−4×5

Donc 
1
=
5
−
1
×
(
24
−
4
×
5
)
=
5
×
5
−
1
×
24
1=5−1×(24−4×5)=5×5−1×24

5
=
29
−
1
×
24
5=29−1×24

Donc 
1
=
5
×
(
29
−
1
×
24
)
−
1
×
24
=
5
×
29
−
6
×
24
1=5×(29−1×24)−1×24=5×29−6×24

24
=
53
−
1
×
29
24=53−1×29

Donc 
1
=
5
×
29
−
6
×
(
53
−
1
×
29
)
=
11
×
29
−
6
×
53
1=5×29−6×(53−1×29)=11×29−6×53

Nous obtenons :

11
×
29
−
6
×
53
=
1
11×29−6×53=1

Ainsi, 
𝑥
=
11
x=11 est une solution.

Étape 3 : Vérification
Calculons 
29
×
11
m
o
d
53
29×11mod53 :

29
×
11
=
319
29×11=319


319
m
o
d
53
=
319
−
6
×
53
=
319
−
318
=
1
319mod53=319−6×53=319−318=1

Donc, 
11
11 est bien l'inverse de 
29
29 modulo 
53
53.

Résultat
L'inverse de 29 modulo 53 est 11.