Chapitre 138 minDébutant
Aide-mémoire d'arithmétique
Par Josselyn C., prof de BTS SIO. Mis à jour le .
À la fin de ce chapitre, tu sauras
- retrouver en un coup d'œil une table, une méthode ou une propriété ;
- éviter les erreurs qui coûtent le plus de points.
Cet aide-mémoire rassemble sur une page ce qu'il faut savoir par cœur pour l'arithmétique de l'E3 du BTS SIO : les tables des puissances et des chiffres hexadécimaux, les méthodes de conversion, les définitions et propriétés de la division euclidienne, du PGCD et des congruences, les formules du chiffrement affine, les fonctions Python utiles et les erreurs qui coûtent le plus de points. Chaque ligne renvoie au chapitre qui l'explique.
Les tables à connaître
Puissances de 2 (chapitre 1) :
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 16 | 32 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 2ⁿ | 1 | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 | 512 | 1 024 | 65 536 | 4 294 967 296 |
Puissances négatives de 2 (chapitre 3) : 2⁻¹ = 0,5 ; 2⁻² = 0,25 ; 2⁻³ = 0,125 ; 2⁻⁴ = 0,0625 ; 2⁻⁵ = 0,031 25.
Puissances de 16 : 16⁰ = 1 ; 16¹ = 16 ; 16² = 256 ; 16³ = 4 096 ; 16⁴ = 65 536.
Chiffres hexadécimaux :
| Hexadécimal | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Décimal | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| Binaire | 0000 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 | 1011 | 1100 | 1101 | 1110 | 1111 |
Octets de masque : 0, 128, 192, 224, 240, 248, 252, 254, 255 (0 à 8 bits à 1 en partant de la gauche).
Nombres premiers inférieurs à 100 : 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.
Inverses modulo 26 (chapitre 9) :
| a | 1 | 3 | 5 | 7 | 9 | 11 | 15 | 17 | 19 | 21 | 23 | 25 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| a' | 1 | 9 | 21 | 15 | 3 | 19 | 7 | 23 | 11 | 5 | 17 | 25 |
Multiples de 26 : 26, 52, 78, 104, 130, 156, 182, 208, 234, 260.
Numération : les méthodes
| Conversion | Méthode | Chapitre |
|---|---|---|
| Base b → base 10 | Somme des chiffres × poids (ou Horner : × b puis + chiffre) | 2 |
| Base 10 → base b (entier) | Divisions successives par b, restes lus de bas en haut, jusqu'au quotient 0 | 2 |
| Base 10 → base 2 (de tête) | Retirer les plus grandes puissances de 2 possibles | 2 |
| Base 2 ↔ base 16 | Paquets de 4 bits depuis la virgule (complétés par des 0 aux extrémités) | 2 |
| Partie fractionnaire, base 10 → base b | Multiplications successives par b, parties entières lues de haut en bas | 3 |
| Arrondi au plus près en base 2 | Premier bit supprimé à 1 → par excès ; à 0 → par défaut | 3 |
| × 2ᵏ et ÷ 2ᵏ en base 2 | Décalage de k rangs ; les k bits sortis à droite forment le reste | 4 |
Retenir aussi :
- n bits codent 2ⁿ valeurs, de 0 à 2ⁿ − 1 ; un octet va de 0 à 255, soit de (00)₁₆ à (FF)₁₆ ;
- addition : retenue dès que la somme d'une colonne atteint la base (2 ou 16) ;
- seuls les nombres de la forme entier ÷ 2ᵏ ont une écriture binaire finie : 0,1 et 0,2 n'en ont pas ;
- un ordinateur stocke les réels en virgule flottante (IEEE 754, double précision : environ 15 à 17 chiffres significatifs) : ne compare jamais deux flottants avec
==.
Arithmétique modulaire : définitions et propriétés
| Notion | Ce qu'il faut savoir | Chapitre |
|---|---|---|
| Division euclidienne | a = b × q + r avec 0 ≤ r < b ; q et r uniques | 5 |
| Diviseur | b divise a ⇔ le reste de a par b est nul | 5 |
| Nombre premier | Exactement deux diviseurs, 1 et lui-même ; 1 n'est pas premier | 6 |
| Test de primalité | Aucun diviseur premier ≤ √n ⇒ n premier | 6 |
| Nombre de diviseurs | n = p₁^a₁ × … × pₖ^aₖ a (a₁ + 1)…(aₖ + 1) diviseurs | 6 |
| PGCD par décomposition | Facteurs communs, avec le plus petit exposant | 7 |
| Algorithme d'Euclide | PGCD(a, b) = PGCD(b, r) ; le PGCD est le dernier reste non nul | 7 |
| Premiers entre eux | PGCD(a, b) = 1 | 7 |
| Congruence | a ≡ b [n] ⇔ n divise a − b ⇔ même reste modulo n | 8 |
| Compatibilité | On peut additionner, multiplier, élever à une puissance ; jamais diviser | 8 |
| Multiples modulo n | Ce sont les multiples de d = PGCD(a, n) ; il y en a n ÷ d | 9 |
| Liste circulaire | Sauts de a sur n éléments : exhaustif ⇔ PGCD(a, n) = 1 | 9 |
| Inverse modulo n | a × a' ≡ 1 [n] ; existe ⇔ PGCD(a, n) = 1 | 9 |
| a × x ≡ b [n] | Si a inversible : x ≡ a' × b. Sinon : solutions ⇔ PGCD(a, n) divise b | 9 |
Chiffrement
| Chiffrement | Codage | Décodage | Clés |
|---|---|---|---|
| César, clé k | y ≡ x + k [26] | x ≡ y − k [26] | 26 (dont la clé nulle) |
| Affine, clé (a, b) | y ≡ ax + b [26] | x ≡ a'(y − b) [26], a' inverse de a | a premier avec 26 : 12 × 26 = 312 |
A = 0, B = 1, …, Z = 25 (vérifie la table du sujet). Pour casser : force brute, ou analyse de fréquences (E est la lettre la plus fréquente en français) et deux lettres connues donnent un système de deux congruences (chapitre 10).
Python en une table
| Besoin | Python | Résultat |
|---|---|---|
| Écrire en binaire, en hexadécimal | bin(156), hex(2026) | '0b10011100', '0x7ea' |
| Écrire sur n bits | format(10, '08b'), format(255, '02X') | '00001010', 'FF' |
| Lire une écriture en base b | int('7EA', 16) | 2026 |
| Quotient, reste | 2026 // 7, 2026 % 7, divmod(2026, 7) | 289, 3, (289, 3) |
| Décalages | 11 << 2, 45 >> 2 | 44, 11 |
| ET, OU, XOR bit à bit | a & b, a | b, a ^ b | |
| PGCD, PPCM | math.gcd(84, 126), math.lcm(6, 8) | 42, 24 |
| Puissance modulaire | pow(3, 2026, 7) | 4 |
| Inverse modulaire | pow(7, -1, 26) | 15 |
| Comparer des flottants | math.isclose(0.1 + 0.2, 0.3) | True |
Les algorithmes à savoir écrire (conversion, Euclide, test de primalité, crible, décomposition, inverse) sont au chapitre 11.