Modulo

[yves-chevallier]

Add some properties of Modulo

z(x%m)==rx%zm

And other useful properties in mathematics useful in progamming

---

Voici une liste de propriétés et d'identités mathématiques particulièrement utiles en programmation, allant des propriétés du modulo à des lois comme celles de De Morgan, en passant par des astuces sur les puissances de 2 et autres concepts essentiels :

---

1. Propriétés du Modulo

• Distributivité sur l'addition :
  [
  (a + b) % n = [(a % n) + (b % n)] % n
  ]
• Distributivité sur la soustraction :
  [
  (a - b) % n = [(a % n) - (b % n) + n] % n
  ]
  (On ajoute ( n ) pour éviter des résultats négatifs.)
• Distributivité sur la multiplication :
  [
  (a \times b) % n = [(a % n) \times (b % n)] % n
  ]
• Puissance modulaire (utilisé dans les algorithmes comme RSA) :
  [
  (a^b) % n = \text{(calculé efficacement par exponentiation modulaire)}.
  ]
• Comparaison :
  Si ( a % n = b % n ), alors ( a ) et ( b ) sont congruents modulo ( n ) :
  [
  a \equiv b \mod n
  ]
• Division par un nombre co-prime à ( n ) (l'inverse modulaire) :
  Si ( \text{pgcd}(b, n) = 1 ), alors il existe ( b^{-1} ) tel que :
  [
  (a \times b^{-1}) % n = (a / b) % n
  ]

---

2. Lois de De Morgan (Logique Booléenne)

• Transformation des expressions logiques pour simplifier ou optimiser :
  [
  \neg (A \land B) \equiv (\neg A) \lor (\neg B)
  ]
  [
  \neg (A \lor B) \equiv (\neg A) \land (\neg B)
  ]
  Utile pour inverser les conditions dans les algorithmes.

---

3. Opérations sur les Puissances de 2

• Tester si un nombre est une puissance de 2 :
  [
  x \ &\ (x - 1) = 0
  ]
  (Cela fonctionne uniquement si ( x > 0 ).)
• Vérifier si un bit ( k ) est activé :
  [
  x \ &\ (1 \ll k) \neq 0
  ]
• Activer le bit ( k ) :
  [
  x \ | \ (1 \ll k)
  ]
• Désactiver le bit ( k ) :
  [
  x \ &\ \sim (1 \ll k)
  ]
• Isoler le bit de poids faible :
  [
  x \ &\ (-x)
  ]

---

4. Propriétés des Divisions Entières

• Pour ( a ), ( b ), ( q ), et ( r ) :
  [
  a = b \times q + r
  ]
  Avec ( r = a % b ) et ( q = a // b ) (division entière).

• Troncature de la division pour des calculs négatifs :
  [
  a // b = \lfloor a / b \rfloor
  ]
  sauf pour des comportements spécifiques en Python/C.

---

5. Astuces sur les Nombres Pair/Impair

• Tester si un nombre est pair :
  [
  x % 2 == 0 \quad \text{ou} \quad x & 1 == 0
  ]
• Tester si un nombre est impair :
  [
  x % 2 \neq 0 \quad \text{ou} \quad x & 1 \neq 0
  ]

---

6. Optimisations par Manipulations Binaires

• Arrondi au multiple de ( 2^n ) le plus proche (vers le bas) :
  [
  x \ &\ \sim (n - 1)
  ]
• Arrondi au multiple de ( 2^n ) le plus proche (vers le haut) :
  [
  (x + (n - 1)) \ &\ \sim (n - 1)
  ]

---

7. Manipulations sur les Suites Arithmétiques et Géométriques

• Somme d'une suite arithmétique :
  [
  S = \frac{n}{2} \times (a_1 + a_n)
  ]
• Produit d'une suite géométrique :
  [
  P = a_1 \times r^{n-1}
  ]

---

8. Notions sur les Combinaisons et Factoriels

• Coefficient binomial (( C(n, k) )) :
  [
  C(n, k) = \frac{n!}{k! \times (n - k)!}
  ]
  (Utilisé dans la génération de sous-ensembles ou pour optimiser des calculs récursifs.)

---

Ces identités et propriétés sont particulièrement utiles pour :

• Optimiser des algorithmes (en réduisant la complexité).
• Simplifier des conditions logiques.
• Travailler efficacement avec des nombres dans des systèmes à base binaire.
• Résoudre des problèmes mathématiques ou des énigmes dans des compétitions de programmation.

Si tu souhaites plus d'exemples ou une application pratique, n'hésite pas à demander ! 😊