Fonctions entières et théorie élémentaire des nombres
Les fonctions entières et la théorie élémentaire des nombres regroupent plusieurs notions fondamentales utilisées pour manipuler, comparer et analyser les nombres entiers. Elles interviennent dans de nombreux domaines de la programmation, notamment l'analyse des algorithmes, la cryptographie, les structures de données, le calcul scientifique, les systèmes de numération et l'arithmétique modulaire. Ces notions permettent notamment d'arrondir des valeurs, de calculer des restes, de déterminer des diviseurs, de rechercher des nombres premiers ou d'étudier les relations existant entre différents entiers.
Contrairement aux opérations sur les nombres réels, les fonctions entières produisent généralement des résultats appartenant à l'ensemble des entiers. Elles sont particulièrement importantes en informatique, puisque les ordinateurs manipulent fréquemment des indices, des tailles de tableaux, des adresses mémoire, des compteurs et des quantités discrètes. La théorie élémentaire des nombres fournit quant à elle les outils nécessaires pour étudier la divisibilité, les nombres premiers, le plus grand commun diviseur, le plus petit commun multiple et les congruences modulaires.
Les fonctions entières
Une fonction entière est une fonction dont le résultat est un nombre entier ou dont le comportement dépend principalement de la partie entière d'une valeur.
Parmi les fonctions les plus courantes figurent :
- la fonction plancher ;
- la fonction plafond ;
- la troncature ;
- l'arrondi ;
- la partie fractionnaire ;
- la fonction signe ;
- les fonctions quotient et reste.
Ces fonctions sont utilisées pour convertir des nombres réels en entiers, déterminer des intervalles, calculer des indices ou répartir des valeurs en groupes.
La fonction plancher
La fonction plancher, souvent appelée floor, retourne le plus grand entier inférieur ou égal à une valeur donnée.
Elle est notée :
| ⌊x⌋ |
Par exemple :
|
⌊4,8⌋ = 4 ⌊4⌋ = 4 ⌊-2,3⌋ = -3 |
Dans le dernier exemple, le résultat vaut -3, car il s'agit du plus grand entier inférieur ou égal à -2,3.
Cette fonction ne doit donc pas être confondue avec une simple suppression de la partie décimale.
La fonction plafond
La fonction plafond, souvent appelée ceiling ou ceil, retourne le plus petit entier supérieur ou égal à une valeur donnée.
Elle est notée :
| ⌈x⌉ |
Par exemple :
|
⌈4,2⌉ = 5 ⌈4⌉ = 4 ⌈-2,3⌉ = -2 |
La fonction plafond est souvent utilisée lorsqu'une quantité doit être arrondie vers le haut.
Par exemple, si un fichier de 10 001 octets doit être divisé en blocs de 4 096 octets, le nombre de blocs nécessaires est :
| ⌈10001 / 4096⌉ = 3 |
La troncature
La troncature consiste à supprimer la partie fractionnaire d'un nombre sans effectuer d'arrondi.
Par exemple :
|
Troncature(4,9) = 4 Troncature(-4,9) = -4 |
La troncature se rapproche d'un déplacement vers zéro.
Elle diffère donc de la fonction plancher pour les nombres négatifs :
|
⌊-4,9⌋ = -5 Troncature(-4,9) = -4 |
Cette distinction est importante dans les langages de programmation, car les conversions de nombres réels vers des entiers utilisent souvent la troncature plutôt qu'un plancher mathématique.
L'arrondi
L'arrondi permet de remplacer une valeur réelle par l'entier le plus proche.
Par exemple :
|
Arrondi(3,2) = 3 Arrondi(3,8) = 4 |
Le traitement des valeurs exactement situées entre deux entiers, comme 2,5, dépend de la convention utilisée.
Les principales conventions sont :
| Méthode | Description |
|---|---|
| Arrondi arithmétique | Arrondit généralement 2,5 vers 3. |
| Arrondi vers zéro | Supprime la partie décimale. |
| Arrondi vers l'infini positif | Utilise le plafond. |
| Arrondi vers l'infini négatif | Utilise le plancher. |
| Arrondi bancaire | Arrondit vers l'entier pair le plus proche. |
L'arrondi bancaire est employé dans plusieurs langages et logiciels financiers afin de limiter les biais statistiques produits par une succession d'arrondis.
La partie fractionnaire
La partie fractionnaire d'un nombre correspond à la différence entre le nombre et son plancher.
Elle peut être définie par :
| {x} = x - ?x? |
Par exemple :
| {4,75} = 0,75 |
Pour un nombre négatif :
|
{-2,3} = -2,3 - (-3) = 0,7 |
La partie fractionnaire est donc toujours comprise entre 0 inclusivement et 1 exclusivement selon cette définition.
La fonction signe
La fonction signe, souvent appelée signum, indique si un nombre est négatif, nul ou positif.
Elle est généralement définie ainsi :
|
-1 si x < 0 sgn(x) = 0 si x = 0 1 si x > 0 |
Par exemple :
|
sgn(-8) = -1 sgn(0) = 0 sgn(15) = 1 |
Cette fonction est utile pour déterminer une direction, une orientation, le sens d'un déplacement ou le signe d'un résultat.
Quotient et reste
La division entière de deux entiers produit généralement deux résultats :
- un quotient entier ;
- un reste.
La relation fondamentale est :
| a = bq + r |
où :
- a est le dividende ;
- b est le diviseur ;
- q est le quotient ;
- r est le reste.
Le reste doit généralement respecter :
| 0 ≤ r < |b| |
Par exemple :
| 17 = 5 × 3 + 2 |
Ainsi :
|
17 DIV 5 = 3 17 MOD 5 = 2 |
Division entière dans les langages de programmation
La syntaxe varie selon les langages.
| Langage | Division entière | Reste |
|---|---|---|
| Pascal | DIV | MOD |
| Visual Basic | \ | Mod |
| Python | // | % |
| C, C++, Java, C# | / avec des entiers | % |
| JavaScript | Troncature nécessaire | % |
Exemple en Pascal :
- Quotient := 17 DIV 5;
- Reste := 17 MOD 5;
Exemple en Python :
- quotient = 17 // 5
- reste = 17 % 5
Attention aux nombres négatifs
Le comportement de la division entière et du reste peut varier selon le langage lorsque les opérandes sont négatifs.
Par exemple, selon la convention utilisée :
| -17 ÷ 5 |
peut produire un quotient de -3 ou de -4.
Avec une troncature vers zéro :
| -17 = 5 × (-3) + (-2) |
Avec une division fondée sur le plancher :
| -17 = 5 × (-4) + 3 |
Il est donc important de consulter les règles du langage lorsqu'un algorithme manipule des nombres négatifs.
Théorie élémentaire des nombres
La théorie des nombres est la branche des mathématiques consacrée principalement à l'étude des entiers.
La théorie élémentaire des nombres s'intéresse notamment :
- à la divisibilité ;
- aux nombres premiers ;
- aux diviseurs ;
- au plus grand commun diviseur ;
- au plus petit commun multiple ;
- à l'arithmétique modulaire ;
- aux congruences ;
- à la factorisation.
Ces notions jouent un rôle essentiel dans la cryptographie, les générateurs pseudoaléatoires, les fonctions de hachage et de nombreux algorithmes.
La divisibilité
Un entier a est divisible par un entier non nul b lorsqu'il existe un entier k tel que :
| a = bk |
On écrit :
| b | a |
et on lit :
| b divise a |
Par exemple :
| 3 | 12 |
car :
| 12 = 3 × 4 |
En revanche :
| 5 ∤ 12 |
car aucun entier multiplié par 5 ne produit 12.
Les diviseurs
Un diviseur d'un nombre entier est une valeur qui le divise sans produire de reste.
Les diviseurs positifs de 12 sont :
| 1, 2, 3, 4, 6 et 12 |
On peut vérifier un diviseur à l'aide de l'opérateur modulo :
|
SI nombre MOD diviseur = 0 ALORS Le nombre est divisible FIN SI |
Propriétés de la divisibilité
La divisibilité possède plusieurs propriétés importantes.
Si :
| a | b |
et :
| a | c |
alors :
| a | (b + c) |
et :
| a | (b - c) |
De même, si :
| a | b |
alors, pour tout entier k :
| a | kb |
Enfin, si :
| a | b |
et :
| b | c |
alors :
| a | c |
Cette dernière propriété est appelée transitivité de la divisibilité.
Les nombres pairs et impairs
Un entier est pair lorsqu'il est divisible par 2.
Il peut alors s'écrire :
| n = 2k |
Un entier est impair lorsqu'il peut s'écrire :
| n = 2k + 1 |
Dans un programme, la parité peut être déterminée par :
|
SI n MOD 2 = 0 ALORS n est pair SINON n est impair FIN SI |
La parité est fréquemment utilisée dans les algorithmes de tri, de partitionnement, de cryptographie et de traitement de signaux.
Les nombres premiers
Un nombre premier est un entier naturel supérieur à 1 possédant exactement deux diviseurs positifs :
| 1 et lui-même |
Les premiers nombres premiers sont :
| 2, 3, 5, 7, 11, 13, 17, 19, 23, ... |
Le nombre 2 est le seul nombre premier pair.
Les autres nombres entiers supérieurs à 1 qui ne sont pas premiers sont appelés nombres composés.
Test naïf de primalité
Une méthode simple pour déterminer si un nombre est premier consiste à tester tous les diviseurs possibles.
|
MODULE EstPremier(n) SI n < 2 ALORS RETOURNER FAUX FIN SI POUR i ← 2 JUSQU'A n - 1 SI n MOD i = 0 ALORS RETOURNER FAUX FIN SI FIN POUR RETOURNER VRAI |
Cette méthode est correcte, mais elle est peu efficace pour les grands nombres.
Optimisation du test de primalité
Il suffit de tester les diviseurs jusqu'à la racine carrée de n.
En effet, si n possède un diviseur supérieur à sa racine carrée, il possède nécessairement un autre diviseur inférieur à celle-ci.
|
MODULE EstPremier(n) SI n < 2 ALORS RETOURNER FAUX FIN SI POUR i ← 2 JUSQU'A ?√n? SI n MOD i = 0 ALORS RETOURNER FAUX FIN SI FIN POUR RETOURNER VRAI |
Cette amélioration réduit considérablement le nombre de divisions nécessaires.
Décomposition en facteurs premiers
Tout entier naturel supérieur à 1 peut être écrit comme un produit de nombres premiers.
Par exemple :
| 60 = 22 × 3 × 5 |
Cette représentation est appelée décomposition en facteurs premiers.
Elle est unique, à l'ordre des facteurs près.
Ce résultat est connu sous le nom de théorème fondamental de l'arithmétique.
Plus grand commun diviseur
Le plus grand commun diviseur, abrégé PGCD, de deux entiers est le plus grand entier positif divisant ces deux nombres.
Par exemple, les diviseurs de 18 sont :
| 1, 2, 3, 6, 9, 18 |
Les diviseurs de 24 sont :
| 1, 2, 3, 4, 6, 8, 12, 24 |
Le plus grand diviseur commun est :
| PGCD(18,24) = 6 |
Algorithme d'Euclide
L'algorithme d'Euclide permet de calculer efficacement un PGCD.
Il repose sur l'identité suivante :
| PGCD(a,b) = PGCD(b, a MOD b) |
Algorithme :
|
MODULE PGCD(a,b) TANT QUE b ≠ 0 reste → a MOD b a → b b → reste FIN TANT QUE RETOURNER a |
Exemple :
|
PGCD(48,18) 48 MOD 18 = 12 18 MOD 12 = 6 12 MOD 6 = 0 PGCD = 6 |
Cet algorithme est l'un des plus anciens algorithmes encore utilisés aujourd'hui.
Nombres premiers entre eux
Deux nombres sont dits premiers entre eux lorsque leur PGCD vaut 1.
Par exemple :
| PGCD(8,15) = 1 |
Ainsi, 8 et 15 sont premiers entre eux.
Cela ne signifie pas que chacun des deux nombres est premier. Cela signifie uniquement qu'ils ne possèdent aucun diviseur commun supérieur à 1.
Cette notion est très importante en cryptographie et en arithmétique modulaire.
Plus petit commun multiple
Le plus petit commun multiple, abrégé PPCM, de deux entiers est le plus petit entier positif qui est un multiple de ces deux nombres.
Par exemple :
| PPCM(6,8) = 24 |
Le PPCM peut être calculé à partir du PGCD :
| PPCM(a,b) = |ab| / PGCD(a,b) |
Cette relation permet d'éviter de rechercher directement les multiples successifs.
Arithmétique modulaire
L'arithmétique modulaire étudie les restes produits par les divisions entières.
On écrit :
| a ≡ b (mod n) |
lorsque a et b produisent le même reste dans une division par n.
Cela signifie également que :
| n | (a - b) |
Par exemple :
| 17 ≡ 5 (mod 12) |
car :
| 17 MOD 12 = 5 |
et :
| 5 MOD 12 = 5 |
Exemple avec une horloge
Une horloge constitue un exemple courant d'arithmétique modulaire.
Si l'heure actuelle est 10 heures et que l'on ajoute 5 heures :
| 10 + 5 = 15 |
Sur une horloge de 12 heures :
| 15 MOD 12 = 3 |
Il sera donc 3 heures.
Ce calcul peut être écrit :
| 10 + 5 ≡ 3 (mod 12) |
Propriétés des congruences
Si :
| a ≡ b (mod n) |
et :
| c ≡ d (mod n) |
alors :
| a + c ≡ b + d (mod n) |
De même :
| a - c ≡ b - d (mod n) |
et :
| ac ≡ bd (mod n) |
Ces propriétés permettent d'effectuer les calculs sur des valeurs réduites modulo n, ce qui évite de manipuler des nombres inutilement grands.
Exponentiation modulaire
L'exponentiation modulaire consiste à calculer :
| ab MOD n |
sans calculer directement la puissance complète.
Par exemple :
| 3100 MOD 7 |
produirait une valeur intermédiaire gigantesque si l'on calculait directement 3100.
Une méthode plus efficace repose sur l'exponentiation rapide :
|
MODULE PuissanceModulaire(base, exposant, modulo) résultat ← 1 base ← base MOD modulo TANT QUE exposant > 0 SI exposant est impair ALORS résultat ← (résultat × base) MOD modulo FIN SI exposant ← exposant DIV 2 base ← (base × base) MOD modulo FIN TANT QUE RETOURNER résultat |
Cette méthode est fondamentale dans les systèmes cryptographiques comme RSA.
Fonctions entières en programmation
Les langages proposent généralement plusieurs fonctions associées aux entiers.
| Fonction | Description |
|---|---|
| floor(x) | Retourne le plancher de x. |
| ceil(x) | Retourne le plafond de x. |
| round(x) | Retourne une valeur arrondie. |
| trunc(x) | Supprime la partie décimale. |
| abs(x) | Retourne la valeur absolue. |
| div ou / | Calcule le quotient entier selon le langage. |
| mod ou % | Calcule le reste. |
| sign(x) | Retourne le signe de x. |
La syntaxe exacte dépend du langage et de sa bibliothèque mathématique.
Exemple en Java
L'exemple suivant calcule le PGCD et le PPCM de deux entiers :
- public class TheorieNombres {
-
- public static int pgcd(int a, int b) {
- a = Math.abs(a);
- b = Math.abs(b);
-
- while (b != 0) {
- int reste = a % b;
- a = b;
- b = reste;
- }
-
- return a;
- }
-
- public static int ppcm(int a, int b) {
- if (a == 0 || b == 0) {
- return 0;
- }
-
- return Math.abs(a / pgcd(a, b) * b);
- }
-
- public static void main(String[] args) {
- int a = 18;
- int b = 24;
-
- System.out.println("PGCD = " + pgcd(a, b));
- System.out.println("PPCM = " + ppcm(a, b));
- }
- }
Le programme retourne :
PGCD = 6PPCM = 72
Applications
Les fonctions entières et la théorie élémentaire des nombres sont utilisées dans de nombreux domaines :
- analyse des algorithmes ;
- cryptographie ;
- génération de nombres pseudoaléatoires ;
- fonctions de hachage ;
- compression de données ;
- gestion de tableaux ;
- pagination ;
- traitement du signal ;
- calcul scientifique ;
- programmation de jeux ;
- calendriers et horloges ;
- systèmes distribués ;
- correction d'erreurs.
Elles sont également indispensables dans l'étude des permutations, des coefficients binomiaux et de l'analyse de complexité.
Avantages
Ces notions présentent plusieurs avantages :
- elles permettent de manipuler précisément des valeurs discrètes ;
- elles simplifient les calculs sur les indices et les tailles ;
- elles fournissent des algorithmes efficaces comme celui d'Euclide ;
- elles constituent la base de nombreuses méthodes cryptographiques ;
- elles facilitent l'analyse et la démonstration des algorithmes ;
- elles permettent de réduire des calculs complexes grâce à l'arithmétique modulaire.
Limites et précautions
Plusieurs précautions doivent toutefois être prises :
- le comportement du modulo avec des nombres négatifs varie selon les langages ;
- une division entière élimine la partie fractionnaire ;
- une multiplication intermédiaire peut provoquer un dépassement de capacité ;
- les tests de primalité naïfs deviennent rapidement trop lents ;
- les nombres très grands exigent des types multiprécision ;
- les arrondis doivent respecter une convention clairement définie ;
- il faut toujours vérifier qu'un diviseur est différent de zéro.
Remarque
Les fonctions entières et la théorie élémentaire des nombres constituent un ensemble d'outils essentiels pour relier les mathématiques discrètes à la programmation. Les fonctions plancher et plafond permettent de gérer des quantités discrètes, tandis que la divisibilité, le PGCD, les nombres premiers et l'arithmétique modulaire fournissent les bases de nombreux algorithmes modernes. Ces notions sont particulièrement importantes avant d'aborder la cryptographie, les permutations, les factorielles, les coefficients binomiaux et l'analyse avancée des algorithmes.