L2 Informatique Arithmétique, Plateforme en autonomie 2022-2023

Chères étudiantes, chers étudiants, ces exercices sont destinés à vous aider à vous approprier les notions vues
en arithmétique en les programmant en Ocaml. Ces travaux sont à réaliser en autonomie.
Soient a et b deux entiers naturels non-nuls, on notera a ∧ b leur pgcd.

1 Division euclidienne, algorithmes d’Euclide simple et étendu

Exercice 1 Définir une fonction div_eucl telle que let (q,r) = div_eucl(a,b) assigne à q le quotient et
à r le reste de la division euclidienne de a par b pour tout a, b tels que a ≥ b > 0 et qui lève l’exception
failwith "division by 0" pour b = 0. Vérifier que div_eucl(86,17) vaut (5, 1).

Exercice 2 Soient a et b deux entiers naturels non-nuls. En s’appuyant sur l’algorithme d’Euclide, program-
mer une fonction récursive pgcd telle que let d = pgcd (a,b) assigne à d le pgcd de a et b. Pour cela on
remarquera que :

• a∧0=0
• si (q, r) =div_eucl(a, b), alors a ∧ b = b ∧ r.

Vérifier que pgcd(24,21) vaut 3.

Exercice 3 Soient a et b deux entiers naturels non-nuls et d = a ∧ b. On rappelle que les entiers relatifs u et
v sont des coefficients de Bézout de a et b si et seulement si ua + vb = d.
Programmer une fonction récursive xgcd telle que let (d,u,v) = xgcd (a,b) assigne à d le pgcd de a et b et
à (u, v) des coefficients de Bézout de a et b. Pour cela on remarquera que :

• si b = 0, d = a, u = 1 et v = 0 conviennent
• sinon, soient (q, r) =div_eucl(a, b), d′ = b ∧ r et (u′ , v ′ ) des coefficients de Bezout de b et r alors
(v ′ , u′ − qv ′ ) sont des coefficients de Bézout pour a et b.

Vérifier que xgcd(5,7) vaut (1, 3, −2).

2 Arithmétique modulaire
Exercice 4 Programmer la fonction proj_mod telle que, pour tout entier relatif x et pour tout entier naturel n
supérieur à 1, y = proj_mod(x,n) assigne à y l’unique entier de {0, . . . , n − 1} tel que y ≡ x mod n.
Programmer la somme et le produit dans Z/nZ, c’est-à-dire les fonctions somme_mod et prod_mod telles que,
pour tout a, b ∈ {0, . . . , n − 1}, let s = somme_mod(a,b,n) et let p = prod_mod(a,b,n) assigne à s le reste
de la division euclidienne de a + b par n et p le reste de la division euclidienne de a × b par n. Vérifier que
proj_mod(-12,9) vaut 6, que somme_mod(3,5,6) vaut 2 et que prod_mod(3,5,6) vaut 3.

Exercice 5 Programmer la fonction d’inversion dans Z/nZ, c’est-à-dire la fonction inv_mod telle que, pour
tout a ∈ {0, . . . , n − 1} :

• si a est inversible dans Z/nZ, let b = inv_mod(a,n) assigne à b l’entier de {0, . . . , n} tel que a · b = 1
mod n ;
• sinon, la fonction lève l’exception failwith "not invertible"

On rappelle que a est inversible dans Z/nZ si et seulement si a∧n = 1. Dans ce cas, soient u et v des coefficients
de Bézout pour a et n, on a au + nv = 1. Il s’ensuit que l’inverse a−1 de a dans Z/nZ satisfait a−1 ≡ u
mod n (on utilisera proj_mod pour obtenir un entier entre 0 et n − 1).
Vérifier que inv_mod(11,17) vaut 14.

Exercice 6 Écrire une fonction div_mod telle que let q = div_mod(a,b,n) assigne à q le quotient de a par
b modulo n lorsque b est inversible dans Z/nZ et lève l’exception failwith "not invertible" si b n’est pas
inversible.
Vérifier que div_mod(12,5,17) vaut 16.

Pratiques Pédagogiques Diversifiées 1 [email protected]

L2 Informatique Arithmétique, Plateforme en autonomie 2022-2023

Exercice 7 Écrire une fonction récursive build_list telle que let l = build_list (m,r,t) assigne à l la
liste des [m + kt pour k ∈ {0, . . . , r}] puis une fonction solve_mod telle que, pour tout a et b non-nuls modulo
n, let l = solve_mod(a,b,n) assigne à l la liste des solutions x de l’équation ax + b = 0 dans Z/nZ.
Vérifier que solve_mod(12,5,17) vaut [1] et que solve_mod(2,2,4) vaut [1, 3].

3 Équation de Bézout et théorème des restes chinois

Exercice 8 Soient a, b, c des entiers relatifs non-nuls et d = a ∧ b. Écrire une fonction solve telle que :

• si d divise c, let (x,y) = solve(a,b,c) assigne à (x, y) une solution de l’équation ax + by = c (NB :
pour ce faire, on pourra calculer dans un premier temps les coefficients de Bézout de (a, b) puis multiplier
de part et d’autre par c/d) ;
• let (x,y) = solve(a,b,c) lève l’exception failwith "No solution" sinon.

Vérifier que solve(3,5,7) vaut (14, −7), c’est-à-dire que (x, y) = (14, −7) est solution de l’équation 3x+5y = 7.

Exercice 9 Soient n1 et n2 deux entiers supérieurs à 1 premiers entre eux. Soient a1 et a2 deux entiers rela-
tifs. Écrire une fonction solve_multi_mod(a1,n1,a2,n2) telle que let a = solve_multi_mod(a1,n1,a2,n2)
assigne à a une solution du système d’équations :
(
x ≡ a1 mod n1
(1)
x ≡ a2 mod n2

NB : pour trouver a, il suffit de remarquer que (1) se réécrit x = a1 + kn1 = a2 + ln2 pour k, l ∈ Z. Cette
équation, qui peut être réécrite k · n1 − l · n2 = a2 − a1 , est de la forme ak + bl = c avec a = n1 , b = −n2 et
c = a2 − a1 . On pourra donc la résoudre avec solve et conclure avec le Théorème des restes chinois qui énonce
que les équations telles que (1) ont des solutions de la forme x = a + m · n1 n2 pour m ∈ Z.

4 Théorème d’Euler
Exercice 10 Implémenter la fonction indicatrice d’Euler, c’est-à-dire une fonction euler_phi telle que, pour
tout entier n > 1, let h = euler_phi(n) assigne à h le nombre d’entiers entre 1 et n qui sont premiers avec n.
Pour cela, on pourra utiliser une fonction récursive euler_aux telle que let l = euler_aux(n,a) assigne à l
le nombre d’entiers premiers avec n dans l’ensemble {a, a + 1, . . . , n} en se ramenant au test du fait que n et a
sont premiers entre eux ou pas.
Vérifier que euler_phi(39) vaut 24.

Exercice 11 Écrire une fonction pow_mod telle que, pour tout entier n > 1, pour tout entier a premier avec n et
pour tout entier m > 1, let b = pow_mod(a,m,n) assigne à b l’entier de {0, . . . , n − 1} tel que b ≡ am mod n.
Écrire une fonction pow_mod_euler utilisant pow_mod en exploitant, en outre, le théorème d’Euler qui énonce
que aφ(n) ≡ 1 mod n.
En effet, si m est très grand, on pourra ainsi se contenter d’élever à la puissance m mod φ(n) en utilisant le
fait 1 que am ≡ am mod φ(n) mod n.
Vérifier que le chiffre des unités de 7222 vaut 9 en vérifiant que pow_mod(7,222,10) vaut 9, puis vérifier que
les trois derniers chiffres de 321123456789 valent 881 en vérifiant que pow_mod_euler(321,123456789,1000)
vaut 881.

m qφ(n) · ar =

rq et rr le quotient et le reste de la division euclidienne de m par φ(n), on a m = qφ(n) + r donc a = a
1. Soient
q
aφ(n) · a ≡ a mod n

Pratiques Pédagogiques Diversifiées 2 [email protected]