CRMEF OUJDA Année universitaire : 2022/2023
Filière mathématique
Y. Derfoufi ............. TP : Arithmétique en Python .......
1 Rappel
— Un élément k̄ de Z/nZ est inversible si et seulement si k ∧ n = 1
— Z/nZ est un corps si et seulement si n est premier.
— (Bezout) deux entiers a et b sont premiers entre eux si et seulement s’il existe deux entiers u et v tels que : ua + vb = 1
— Si d = a ∧ b alors dZ = aZ + bZ
— Si p est un nombre premier et a ∈ Z non multiple de p alors ap−1 ≡ 1[p]
— Si p est un nombre premier et a, b ∈ Z alors (a + b)p ≡ ap + bp [p]
— Équation dans Z/nZ. Pour tout a, b, n ∈ Z , l’équation ax ≡ b[n] admet des solution si et seulement si d = a ∧ n divise b
— Soient a, b ∈ Z∗ et c ∈ Z alors l’équation diophantienne ax + by = c admet une solution si et seulement si c est un
multiple de d = a ∧ b
— Pour tout n ∈ Z∗ on pose φ(n) =| Z∗ | appelé indicateur d’Euler on a alors φ(n) = card{m ∈ N∗ /m ≤ n et m ∧ n = 1}
— Si m ∧ n = 1 alors φ(mn) = φ(m)φ(n)
— Si p est un nombre premier, alorsP on a φ(p) = p − 1 et φ(pk ) = pk−1 (p − 1) pour tout entier k > 0
— Pour tout entier n > 0 on a n = φ(d)
d/n
— Pour tout entier n > 0 et pour tout a ∈ N∗ si a ∧ n = 1 alors aφ(n) ≡ 1[n]
2 TD d’arithmétique en Python
Exercice 1. Écrire un programme en Python permettant de calculer le pgcd de deux nombres entiers > 0.
Exercice 2. Écrire un programme en Python sous forme de fonction qui prend en paramètre un couple d’entiers m, n > 0 et
qui renvoie True si m ∧ n = 1 et False si non.
Exercice 3. Écrire un programme en Python sous forme de fonction qui prend en paramètre un nombre entier n > 0 et qui
renvoie True si le nombre n est premier et False si non.
Exercice 4. Écrire un programme en Python sous forme de fonction qui prend en paramètre un nombre entier n > 0 et qui
renvoie la liste des nombre premiers qui sont inférieur à n.
Exercice 5. Écrire un programme en Python sous forme de fonction qui prend en paramètre un nombre entier n > 0 et qui
renvoie le plus petit nombre premier strictement supérieur à n.
Exercice 6. Écrire un algorithme en Python sous forme de fonction qui prends deux nombres m et n en paramètres (m<n) et
qui renvoie une liste formée de tous les nombres premiers compris entre m et n. Exemple pour m = 10 et n = 20 la fonction doit
renvoyer [11, 13, 17, 19]
Exercice 7. Écrire un algorithme en python qui renvoie la liste des entiers positifs composés de de deux chiffres de la forme pq
tel que le produit des chiffres p*q est un multiple de leur somme p + q (avec p et q sont non nuls).
Exercice 8. Ecrire un programme en python permettant de trouver la liste des diviseurs premiers d’un nombre entier.
Exercice 9. Ecrire un algorithme en python qui détermine pour un entier n donné les couples (p , q) avec p ≤ n et q ≤ n
dont le plus grand diviseurs commun pgcd(p,q) est premier.
Exercice 10. Écrire un programme en Python sous forme de fonction qui prend en paramètre un nombre entier n > 0 et qui
renvoie la liste des nombres k < n et premiers avec n. En déduire un algorithme qui calcul φ(n) (n 7→ φ(n) désigne la fonction
indicatrice d’Euler).
3 Approximation des réels en Python
+∞ 2n+1
(−1)n x2n+1 , donner
P
Exercice 11. En utilisant le développement en série entière de la fonction arctangente : arctan(x) =
n=0
un algorithme en Python qui permet d’approximer le nombre π.
+∞
xn
Exercice 12. Même question pour le nombre e en utilisant le développement en série entière de l’exponentielle ex =
P
n! .
n=0
√
Exercice 13. En utilisant
√ le développement en fraction continue de 2 = [1, 2, 2, 2, ..., 2, ... donner un algorithme en python
permettant d’approximer 2
