Arithmétique

Retrouvez toutes les fiches de cours téléchargeables au format pdf en cliquant sur les liens suivants :

• Fiche n° 1 : Algorithme en langage naturel
• Fiche n° 2 : Les variables
• Fiche n° 2 bis : Les listes
• Fiche n° 3 : Les fonctions
• Fiche n° 3 bis : Mathématiques et programmation
• Fiche n° 4 : Les instructions conditionnelles
• Fiche n° 5 : Les boucles bornées
• Fiche n° 6 : Les boucles non bornées

1

Test de primalité optimisé ★☆☆

→ Voir fiche n° 1 : Algorithme en langage naturel
→ Voir fiche n° 2 : Les variables
→ Voir fiche n° 3 : Les fonctions
→ Voir fiche n° 4 : Les instructions conditionnelles
→ Voir fiche n° 5 : Les boucles bornées

1. Compléter la fonction premier qui prend en argument un nombre entier strictement positif et qui retourne True si ce nombre est premier et False sinon.

2. Expliquer la ligne 8 de cette fonction.


3. Justifier pourquoi cette ligne peut être remplacée par for i in range(2, int(sqrt(n)) + 1).


4. À l’aide de l’instruction clock du module time, qui permet de chronométrer un programme, évaluer le gain de temps obtenu avec cette modification sur différents nombres premiers. On pourra par exemple introduire les lignes suivantes.

def premier(n):
  if n == 1:
    return False
  if n == 2:
    return True
  else:
    for i in range(2, n):
      if ... :
        return False
  return True

2

Fréquence des carrés modulo 7 ★★☆

→ Voir fiche n° 2 : Les variables
→ Voir fiche n° 2 bis : Les listes
→ Voir fiche n° 5 : Les boucles bornées

1. À l’aide d’une feuille de calcul, déterminer le reste dans la division euclidienne par $7$ de chacun des carrés des nombres entiers compris entre $0$ et $100$. Certains restes semblent-ils apparaître plus souvent que d’autres ?


2. Le programme suivant calcule la fréquence de chaque congruence modulo 7 parmi les carrés des nombres entiers strictement positifs. Compléter les lignes 4 et 8 de ce programme.

3. Après avoir lancé ce programme, pouvez vous confirmer le résultat de la question 1 ?

N = 1000
congruence = [0, 0, 0, 0, 0, 0, 0]
for i in range(N):
  reste = ...
  congruence[reste] = congruence[reste] + 1

# calcul des fréquences
for k in range(len(congruence)):
  congruence[k] = ...

print(congruence)

3

Calcul du $\text{PGCD}$ par l’algorithme d’Euclide ★☆☆

→ Voir fiche n° 2 : Les variables
→ Voir fiche n° 3 : Les fonctions
→ Voir fiche n° 6 : Les boucles non bornées

Les fonctions euclide_iteratif et euclide_recursif permettent de calculer le $\text{PGCD}$ de deux nombres entiers naturels $a$ et $b$ donnés en arguments.

1. Compléter la fonction euclide_iteratif.

2. Compléter la fonction euclide_recursif.

def euclide_iteratif(a, b):
  a, b = max(a, b), min(a, b)
  reste = b
  while a%b … :
    reste = a%b
    a, b = ... , ...
  return ...
  
def euclide_recursif(a, b):
  a, b = max(a, b), min(a, b)
  if a%b == 0:
    return ...
  else:
    return ...

4

Calcul du $\text{PGCD}$ par balayage ★☆☆

→ Voir fiche n° 2 : Les variables
→ Voir fiche n° 3 : Les fonctions
→ Voir fiche n° 4 : Les instructions conditionnelles
→ Voir fiche n° 5 : Les boucles bornées

La fonction pgcd_balayage renvoie le $\text{PGCD}$ de deux nombres entiers $a$ et $b$ donnés en arguments. Pour ce faire, la fonction teste tous les nombres inférieurs à $a$ et $b$ et conserve, parmi ceux qui divisent $a$ et $b$, le plus grand. Compléter la fonction.

def pgcd_balayage(a, b):
  for i in range(...):
    if a%i == 0 and ... :
      pgcd = ...
  return pgcd

5

Conjectures ★★★

→ Voir fiche n° 2 : Les variables
→ Voir fiche n° 3 : Les fonctions
→ Voir fiche n° 4 : Les instructions conditionnelles

Dans un manuel, Jérôme a lu que, pour tout $n \in \mathbb{N}$, $7n+4$ et $5n+3$ étaient premiers entre eux.

1. À l’aide de la fonction euclide_recursif de l’exercice 3 (à compléter), écrire une fonction permettant de tester cette affirmation pour tous les nombres entiers inférieurs à une valeur $\text{N} \in \mathbb{N}$ donnée en argument.

2. Démontrer cette conjecture.


3. Par ailleurs, Jérôme a lu que, pour tout entier naturel non nul $n$, $\dfrac{2n+1}{n(n+1)}$ est irréductible. En modifiant la fonction de la question 1, estimer la validité de cette conjecture.


4. Prouver cette conjecture.

def euclide_recursif(a, b):
  a, b = max(a, b), min(a, b)
  if a%b == 0:
    return ...
  else:
    return ...

6

Nombre de diviseurs ★★☆

→ Voir fiche n° 1 : Algorithme en langage naturel
→ Voir fiche n° 2 : Les variables
→ Voir fiche n° 3 : Les fonctions
→ Voir fiche n° 4 : Les instructions conditionnelles
→ Voir fiche n° 5 : Les boucles bornées

1. Écrire une fonction nombre_diviseurs qui prend en argument un nombre entier non nul $n$ et qui retourne le nombre de ses diviseurs.

2. Écrire une fonction max_diviseurs qui prend en argument un nombre entier $n$ non nul et qui retourne le nombre entier $k\leqslant n$ ayant le plus grand nombre de diviseurs. Si deux nombres ou plus ont le même nombre de diviseurs, la fonction renverra le plus petit de ces nombres.

3. Modifier le programme pour qu’en cas d’égalité sur le nombre de diviseurs, la fonction retourne le plus grand des nombres concernés.

7

Théorème de Wilson ★★☆

→ Voir fiche n° 2 : Les variables
→ Voir fiche n° 3 : Les fonctions
→ Voir fiche n° 4 : Les instructions conditionnelles

Le théorème de Wilson affirme qu’un entier $p$ strictement plus grand que $1$ est un nombre premier si, et seulement si, il divise $(p -1)! + 1$, c'est-à-dire si, et seulement si, $\displaystyle (p-1)!+1\equiv 0 [p]$.

1. En utilisant éventuellement la fonction factorial du module math, écrire à l’aide du théorème de Wilson, une fonction estPremier qui prend en argument un entier naturel $n$ supérieur ou égal à $2$ et renvoie True si l’entier est premier et False sinon.

2. Vérifier pour les entiers inférieurs ou égaux à $10\,000$ que le test de primalité présenté dans l’exercice 1 et celui du théorème de Wilson donnent les mêmes résultats.

3. Expliquer pourquoi ce test, malgré sa simplicité apparente, n’est pas utilisé dans les tests de primalité informatiques.

8

Nombres pseudo-aléatoires ★☆☆

→ Voir fiche n° 2 : Les variables
→ Voir fiche n° 3 : Les fonctions
→ Voir fiche n° 4 : Les instructions conditionnelles

Pour générer une suite de nombres pseudo‑aléatoires, c’est-à-dire une suite de nombres présentant certaines propriétés du hasard, on peut utiliser des suites d’entiers définies, pour tout entier naturel $n$, par $u_{n+1} = au_n+ c [m]$, où $a$, $c$ et $m$ sont trois nombres entiers appelés respectivement le multiplicateur, l’incrément et le module. Le premier terme $u_0$, nombre entier compris entre $0$ et $m-1$, est appelé graine.

1. Dans cette question, on choisit $a=25$, $c=16$ et $m=256$. En utilisant des graines égales à $125$, $96$, $50$ et $10$, expliquer pourquoi les suites générées ne conviennent pas comme suites de nombres pseudo‑aléatoires.


2. Expliquer pourquoi une suite générée par cette méthode est nécessairement périodique. Préciser quelle valeur la période ne peut pas dépasser.


3. Écrire une fonction Python nommée periode qui prend en arguments $a$, $c$, $m$ et $u_0$ et retourne la période de la suite.

def u(n, a, c, m, u_0):
  if (n == 0):
    return u_0
  else:
    return (a*u(n-1, a, c, m, u_0) + c)%m

9

Décomposition en produit de facteurs premiers ★★★

→ Voir fiche n° 2 : Les variables
→ Voir fiche n° 3 : Les fonctions
→ Voir fiche n° 5 : Les boucles bornées

La fonction decomposition_vers_nombre ci-dessous permet de calculer un nombre à partir de sa décomposition en produit de facteurs premiers.

1. En étudiant la fonction, sous quelle forme doit être écrite la décomposition en produit de facteurs premiers d’un nombre pour que le script fonctionne correctement ?


2. Tester cette fonction avec M=[[2,1],[3,2],[5,3]].

3. Écrire une fonction qui prend en argument un nombre entier naturel inférieur ou égal à $1\,000$ et qui renvoie sa décomposition en produit de facteurs premiers.

def decomposition_vers_nombre(M):
  nombre = 1
  n = len(M)
  for facteur in range(n):
    nombre = nombre * M[facteur][0]**M[facteur][1]
  return nombre
 
liste_nombres_premiers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]

10

Divisibilité par 24 ★★★

→ Voir fiche n° 2 : Les variables
→ Voir fiche n° 3 : Les fonctions
→ Voir fiche n° 4 : Les instructions conditionnelles
→ Voir fiche n° 5 : Les boucles bornées

1. Démontrer que si $p$ est un nombre premier supérieur ou égal à $5$, alors $p^2-1$ est un multiple de $24$.

2. On choisit un nombre entier naturel $n$ inférieur ou égal à $1\,000$ tel que $n^2-1$ soit divisible par $24$. Estimer à l’aide d’une fonction Python la probabilité que $n$ soit un nombre premier.

11

$\text{PPCM}$ ★★★

→ Voir fiche n° 2 : Les variables
→ Voir fiche n° 3 : Les fonctions
→ Voir fiche n° 4 : Les instructions conditionnelles
→ Voir fiche n° 5 : Les boucles bornées

Le code ci-dessous permet de déterminer le $\text{PGCD}$ de deux nombres dont on donne la décomposition en produit de facteurs premiers. Utiliser ce code pour écrire une fonction Python permettant de calculer le $\text{PPCM}$ de deux nombres donnés.

def pgcd(nb1, nb2):
  n1 = len(nb1)
  n2 = len(nb2)
  
  out = []
 
  liste1 = []
  for i in range(n1):
    liste1.append(nb1[i][0])
  
  liste2 = []
  for j in range(n2):
    liste2.append(nb2[j][0])
  
  for facteur in range(n1):
    if liste1[facteur] in liste2:
      index = liste2.index(liste1[facteur])
      exposant = min(nb1[facteur][1], nb2[index][1])
      out.append([liste1[facteur], exposant])
  
  return out
 
a = [[2,5],[5,3],[7,1]]
b = [[2,3],[3,2],[5,4]]

12

Nombres de Fermat ★☆☆

→ Voir fiche n° 2 : Les variables
→ Voir fiche n° 3 : Les fonctions
→ Voir fiche n° 4 : Les instructions conditionnelles
→ Voir fiche n° 6 : Les boucles non bornées

Pour tout entier naturel $n$, on appelle $n$-ième nombre de Fermat le nombre $F_n=2^{2^n}+1$.
Pierre de Fermat émit la conjecture que ces nombres étaient tous premiers.
Vérifier cette conjecture à l’aide d’un programme Python.

13

Nombres de Mersenne ★☆☆

→ Voir fiche n° 2 : Les variables
→ Voir fiche n° 2 bis : Les listes
→ Voir fiche n° 3 : Les fonctions
→ Voir fiche n° 4 : Les instructions conditionnelles
→ Voir fiche n° 5 : Les boucles bornées
→ Voir fiche n° 6 : Les boucles non bornées

Pour tout entier naturel non nul $n$, on appelle $n$-ième nombre de Mersenne le nombre $\text{M}_n=2^n-1$.
Pour que le nombre de Mersenne $\text{M}_n$ soit premier, il est nécessaire, mais pas suffisant, que $n$ soit lui-même premier.
Dresser la liste des huit premiers nombres de Mersenne premiers à l’aide d’une fonction Python.