Correction de la série de TP 1

Exercice 1.
Algorithme : Représentation d’un entier a dans une base g
Entrées : a (entier positif), g (base entière > 1)
Sorties : representation (liste des chiffres), k (nombre de chiffres)

Algorithm 1 Représenter un entier a dans une base g

1: if g ≤ 1 then
2: Afficher une erreur "Base invalide".
3: end if
4: if a < 0 then
5: Afficher une erreur "Entier invalide".
6: end if
7: if a = 0 then
8: k←1
9: representation ← [0]
10: return representation, k
11: else
12: k ← ⌊logg (a)⌋ + 1
13: representation ← []
14: end if
15: while a > 0 do
16: reste ← a mod g
17: Ajouter reste au début de representation.
18: a ← ⌊a/g⌋
19: end while
20: return representation, k

Code Python : Représentation d’un entier dans une base

1 import math
2

3 def representer_base (a , g ) :
4 # V r i f i c a t i o n des conditions sur les e n t r e s
5 if g <= 1:
6 raise ValueError ( " La base doit tre sup rieure 1. " )
7 if a < 0:
8 raise ValueError ( " L ’ entier convertir doit tre positif . " )
9

10 # Cas particulier : si a est 0

11 if a == 0:
12 return [0] , 1
13

1
14 # Calcul de k
15 k = math . floor ( math . log (a , g ) ) + 1
16

17 # Trouver les coefficients a_i

18 representation = []
19 while a > 0:
20 reste = a % g
21 representation . insert (0 , reste ) # Ajouter au d b u t
22 a //= g
23

24 return representation , k
25

26 # Exemple d ’ utilisation
27 a = 345
28 g = 10
29 representation , k = representer_base (a , g )
30 print ( f " R e p r s e n t a t i o n de { a } en base { g } : { representation } " )
31 print ( f " Nombre de chiffres ( k ) : { k } " )
Listing 1 – Fonction Python pour représenter un entier a dans une base g

exercice 2.
1. Algorithme : Division euclidienne d’un entier a par un entier b
Entrées : - a : un entier (positif ou négatif). - b : un entier non nul.
Sorties : - q : le quotient de la division euclidienne (q = ⌊a/b⌋). - r : le reste de la division
euclidienne (r = a − b · q).

Algorithm 2 Calcul de la division euclidienne

Require: b ̸= 0
Ensure: Retourne q, r
1: if b = 0 then
2: Afficher une erreur "Division par zéro".
3: Arrêter l’algorithme.
4: end if
5: q ← ⌊a/b⌋ ▷ Calcul du quotient entier.
6: r ← a − b · q ▷ Calcul du reste.
7: return q, r

2
 Code Python : Division euclidienne

1 def divisio n _ e u c l i d i e n n e (a , b ) :
2 # V r i f i c a t i o n de l ’ e n t r e
3 if b == 0:
4 raise ValueError ( " Division par z r o non permise . " )
5

6 # Calcul du quotient et du reste

7 q = a // b # Quotient entier
8 r = a % b # Reste
9

10 return q , r
11

12 # Exemple d ’ utilisation
13 a = 17
14 b = 5
15 quotient , reste = d i v i s i o n _ e u c l i d i e n n e (a , b )
16 print ( f " Division euclidienne de { a } par { b } : " )
17 print ( f " Quotient : { quotient } , Reste : { reste } " )
Listing 2 – Fonction Python pour calculer la division euclidienne

2. Algorithme : Calcul du PGCD et des coefficients de Bézout

Entrées : - a et b : deux entiers.
Sorties : - PGCD(a, b) : le plus grand commun diviseur de a et b. - u et v : les coefficients associés
dans le théorème de Bézout, c’est-à-dire u et v tels que :

PGCD(a, b) = u · a + v · b

Algorithm 3 Calcul du PGCD et des coefficients de Bézout

1: Initialiser r0 ← a, r1 ← b, u0 ← 1, u1 ← 0, v0 ← 0, v1 ← 1
2: while r1 ̸= 0 do
3: Calculer q ← ⌊r0 /r1 ⌋
4: Mettre à jour r0 ← r1 , r1 ← r0 − q · r1
5: Mettre à jour u0 ← u1 , u1 ← u0 − q · u1
6: Mettre à jour v0 ← v1 , v1 ← v0 − q · v1
7: end while
8: return r0 , u0 , v0

3
 Code Python : Calcul du PGCD et des coefficients de Bézout

1 def pgcd_et_bezout (a , b ) :
2 # Initialisation des valeurs
3 r0 , r1 = a , b
4 u0 , u1 = 1 , 0
5 v0 , v1 = 0 , 1
6

7 # Algorithme d ’ Euclide tendu

8 while r1 != 0:
9 # Calcul du quotient
10 q = r0 // r1
11

12 # Mise jour des restes

13 r0 , r1 = r1 , r0 - q * r1
14

15 # Mise jour des coefficients de B z o u t

16 u0 , u1 = u1 , u0 - q * u1
17 v0 , v1 = v1 , v0 - q * v1
18

19 # Retourner le PGCD et les coefficients de B z o u t

20 return r0 , u0 , v0
21

22 # Exemple d ’ utilisation
23 a = 56
24 b = 15
25 pgcd , u , v = pgcd_et_bezout (a , b )
26 print ( f " PGCD ({ a } , { b }) = { pgcd } " )
27 print ( f " Coefficients de B z o u t : u = { u } , v = { v } " )
Listing 3 – Fonction Python pour calculer le PGCD et les coefficients de Bézout

Exercice 3. Algorithme pour trouver toutes les solutions de l’équation diophan-

tienne ax + by = n
Entrées : - a, b, n : trois entiers donnés.
Sorties : - Solutions paramétriques sous forme de x = x0 + k · db , y = y0 − k · ad , où k est un
entier quelconque.

Algorithm 4 Trouver toutes les solutions de ax + by = n

1: Calculer PGCD(a, b) = d en utilisant l’algorithme d’Euclide étendu
2: if d ne divise pas n then
3: return "Pas de solution"
4: else
5: Calculer la solution particulière x0 = u · nd , y0 = v · nd
6: Retourner les solutions paramétriques : x = x0 + k · db , y = y0 − k · a
d
7: end if

4
 Code Python : Trouver toutes les solutions de l’équation diophantienne

1 def pgcd_et_bezout (a , b ) :
2 # Initialisation des valeurs
3 r0 , r1 = a , b
4 u0 , u1 = 1 , 0
5 v0 , v1 = 0 , 1
6

7 # Algorithme d ’ Euclide tendu

8 while r1 != 0:
9 q = r0 // r1
10 r0 , r1 = r1 , r0 - q * r1
11 u0 , u1 = u1 , u0 - q * u1
12 v0 , v1 = v1 , v0 - q * v1
13

14 return r0 , u0 , v0 # PGCD , u , v
15

16 def t r o u v e r _ s o l u t i o n s _ d i o p h a n t i e n n e s (a , b , n ) :
17 # Calcul du PGCD et des coefficients de B z o u t
18 d , u , v = pgcd_et_bezout (a , b )
19

20 # V r i f i e r si le PGCD divise n
21 if n % d != 0:
22 return " Pas de solution " # Aucune solution si PGCD ne divise n
23

24 # Calculer la solution p a r t i c u l i r e
25 x0 = u * ( n // d )
26 y0 = v * ( n // d )
27

28 # Toutes les solutions : x = x0 + k * ( b / d ) , y = y0 - k * ( a / d )

29 def solutions ( k ) :
30 x = x0 + k * ( b // d )
31 y = y0 - k * ( a // d )
32 return x , y
33

34 return solutions
Listing 4 – Fonction Python pour trouver toutes les solutions de ax + by = n

Exercice 4.
1. Algorithme pour tester si un entier n est premier
Entrées : - n : un entier.
Sortie : - Vrai si n est premier, sinon faux.

5
 Algorithm 5 Tester si un entier n est premier
1: if n ≤ 1 then
2: return Non premier
3: end if
√
4: for p = 2 to ⌊ n⌋ do
5: if n mod p = 0 then
6: return Non premier
7: end if
8: end for
9: return Premier

Code Python : Tester si un entier n est premier

1 import math
2

3 def est_premier ( n ) :
4 # Cas particulier : n <= 1 n ’ est pas premier
5 if n <= 1:
6 return False
7

8 # V r i f i c a t i o n de la d i v i s i b i l i t par tous les entiers de 2

sqrt ( n )
9 for p in range (2 , int ( math . sqrt ( n ) ) + 1) :
10 if n % p == 0:
11 return False # n est divisible par p , donc non premier
12

13 return True # n n ’ est divisible par aucun nombre de 2 sqrt ( n ) ,

donc premier
14

15 # Exemple d ’ utilisation
16 n = 29
17 if est_premier ( n ) :
18 print ( f " { n } est premier . " )
19 else :
20 print ( f " { n } n ’ est pas premier . " )
Listing 5 – Fonction Python pour tester si un entier n est premier

2. Algorithme du Crible d’Ératosthène

Entrée : Un entier n.
Sortie : Liste des nombres premiers inférieurs ou égaux à n.

6
 Algorithm 6 Crible d’Ératosthène pour trouver tous les nombres premiers jusqu’à n
1: Créer une liste is_prime de taille n + 1, initialisée à True.
2: Définir is_prime[0] = False et is_prime[1] = False.
√
3: for p = 2 to ⌊ n⌋ do
4: if is_prime[p] = True then
5: for k = p2 to n step p do
6: is_prime[k] = False
7: end for
8: end if
9: end for
10: Retourner la liste des indices i où is_prime[i] = True.

Code Python : Crible d’Ératosthène

1 import math
2

3 def crible_e ra to st he ne ( n ) :
4 # C r e r une liste pour marquer les nombres premiers
5 is_prime = [ True ] * ( n + 1)
6 is_prime [0] = is_prime [1] = False # 0 et 1 ne sont pas premiers
7

8 # Crible d ’ ratosthne
9 for p in range (2 , int ( math . sqrt ( n ) ) + 1) :
10 if is_prime [ p ]: # Si p est un nombre premier
11 for multiple in range ( p * p , n + 1 , p ) : # Marquer les
multiples de p
12 is_prime [ multiple ] = False
13

14 # Renvoyer les nombres premiers

15 primes = [ i for i in range (2 , n + 1) if is_prime [ i ]]
16 return primes
17

18 # Exemple d ’ utilisation
19 n = 30
20 print ( f " Les nombres premiers i n f r i e u r s ou gaux { n } sont : {
crible_e ra to st he ne ( n ) } " )
Listing 6 – Fonction Python pour appliquer le Crible d’Ératosthène

Exercice 5.
Algorithme pour décomposer un entier en produit de ses facteurs premiers
Entrée : Un entier n.
Sortie : Liste des facteurs premiers de n et leurs puissances respectives.

7
 Algorithm 7 Décomposer un entier n en produit de ses facteurs premiers
1: Créer une liste factors vide pour les facteurs premiers.
2: Créer une liste exponents vide pour les puissances des facteurs.
√
3: for i = 2 to ⌊ n⌋ do
4: exponent = 0
5: while n % i == 0 do
6: n = n // i
7: exponent += 1
8: end while
9: if exponent > 0 then
10: Ajouter i à la liste factors
11: Ajouter exponent à la liste exponents
12: end if
13: end for
14: if n > 1 then
15: Ajouter n à la liste factors
16: Ajouter 1 à la liste exponents
17: end if
18: Retourner les listes factors et exponents

Code Python : Décomposition d’un entier en produit de ses facteurs premiers

1 def decomposeur ( n ) :
2 factors = [] # Liste pour les facteurs premiers
3 exponents = [] # Liste pour les puissances des facteurs
4

5 # D c o m p o s e r les facteurs premiers jusqu ’ la racine c a r r e de n

6 i = 2
7 while i * i <= n :
8 exponent = 0
9 while n % i == 0: # Si i divise n
10 n //= i
11 exponent += 1
12 if exponent > 0:
13 factors . append ( i ) # Ajouter le facteur premier
14 exponents . append ( exponent ) # Ajouter sa puissance
15 i += 1
16

17 # Si n est encore plus grand que 1 , c ’ est un facteur premier

18 if n > 1:
19 factors . append ( n )
20 exponents . append (1)
21

22 return factors , exponents

23

24 # Exemple d ’ utilisation
25 n = 60

8
26 factors , exponents = decomposeur ( n )
27 print ( f " D c o m p o s i t i o n de { n } : " )
28 for i in range ( len ( factors ) ) :
29 print ( f " { factors [ i ]}^{ exponents [ i ]} " )
Listing 7 – Fonction Python pour décomposer un entier en facteurs premiers