Mathématique discrètes

Soient a, b ∈ Z avec a ≠ 0. On dit que a divise b, noté a | b ssi

∃c ∈ Z ; b \= ac

Algorithme de division d'Euclide

Soient a ∈ Z et d ∈ N_0. Il existe deux uniques entiers q et r tels que 0 ≤ r < d et a \= dq + r

Congruence

Soient a, b ∈ Z et n ∈ N_0. On dit que a est congru à b modulo n si et seulement si n divise (a − b). On note alors a ≡ n b.

Un nombre p ∈ N est dit premier si

Il admet exactement deux diviseurs naturels distincts (qui sont 1 et p)

Théorème fondamental de l'arithmétique

Tout naturel n ≥ 2 peut-être écrit comme un produit de nombres premiers d'une unique façon, à l'ordre près des facteurs.

pgcd(a,b)

Soient a, b ∈ Z tels que a ≠ 0 ou b ≠ 0.

Le plus grand naturel d tel que **d | a et d | b** est appellé plus grand commun diviseur de a et b

ppcm(a,b)

Soient a, b ∈ N_0. Le plus petit commun multiple de a et b est le plus petit naturel d tel que a | d et b | d.

Représentation des naturels en base b

Soient b ∈ N tel que b ≥ 2 et n ∈ N, on peut écrire n de façon unique sous la forme

n = a_k b^k + a_k−1. b^(k−)1 + · · · + a₁ b¹ + a₀ b⁰ ,

où 0 ≤ ak, ak−1, . . . , a₁, a¹ ≤ b − 1. On dit que (a_k a_k−1...a₁ a₀)₀ est la représentation de n en base b.

Petit théorème de fermat

Soient n un nombre premier et a un nombre entier non divisible par p, on a aⁿ ≡ₙ a

Relation binaire entre deux ensembles A et B

Soit R ⊆ A × B une relation binaire entre A et B.

Soient a ∈ A et b ∈ B. Si (a, b) ∈ R, on dira que a est en relation avec b, noté; a R b.

Relation binaire sur un ensemble

Soit A un ensemble. Une relation binaire sur A est un sous-ensemble de A × A

Relation réfléxive

Soit R ⊆ A × A. On dit que R est réflexive ssi \n ∀a ∈ A **aRa**

Relation symétrique

Soit R ⊆ A × A. On dit que R est symétrique ssi

∀a ∈ A ∀b ∈ A **aRb ⇒ bRa**

Relation transitive

Soit R ⊆ A × A. On dit que R est transitive ssi ∀a ∈ A ∀b ∈ A ∀c ∈ A **(aRb ∧ bRc) ⇒ aRc**

Relation antisymétrique

Soit R ⊆ A × A. On dit que R est antisymétrique ssi ∀a ∈ A ∀b ∈ A **(aRb ∧ bRa) ⇒ a = b.**

Relation inverse

Soit R ⊆ A × B une relation binaire. La relation inverse, notée R−1 , est définie par R-¹ \= {(b, a) ∈ B × A | aRb}

Relation d’équivalence

Soit R ⊆ A x A.

On dit que R est une relation d’équivalence ssi

R est **réfléxive**, **symétrique** et **transitive**

Classe d’équivalence

Soit R ⊆ A × A une relation d’´equivalence, soit a ∈ A.

[a]R = {b ∈ A | aRb}.

Soit A un ensemble. Soit P = {Ai | Ai ⊆ A} un ensemble de sous-ensembles de A. On dit que P est une partition de l’ensemble A ssi

1) ∪ Ai∈P **Ai = A**

2) ∀Ai ∈ P ∀Aj ∈ P **Ai ≠ Aj ⇒ Ai ∩ Aj = ∅.**

Soit R ⊆ A × A une relation d’équivalence sur A. Soient a ∈ A et b ∈ A. Les trois affirmations suivantes sont équivalentes

aRb ↔ [a]_R = [b]_R ↔ [a]_R ∩ [b]_R ≠ ∅

Soit R ⊆ A × A. On dit que R est une relation d’ordre ssi

R est réflexive, antisymétrique et transitive

Soit (A, R) un ensemble ordonné. Soient a, b ∈ A. On dit que les éléments a et b sont **comparables** (pour l’ordre R) ssi

**aRb ou bRa**

Soit (A, R) un ensemble ordonn´e. On dit que (A, R) est totalement ordonné ssi

toute paire d’éléments de A est comparable, i.e. **∀a ∈ A ∀b ∈ A aRb ∨ bRa**.

Soit (A, ≼) un ensemble ordonné. Soient a ∈ A et b ∈ A. On dit que b est un successeur immédiat de a ssi

a ≺ b ∧ ¬(∃c ∈ A a ≺ c ≺ b).

Maximum (dans A, ≼)

∀b ∈ A b ≼ a

Minimum (dans A, ≼)

∀b ∈ A a ≼ b

Maximal (dans A, ≼)

¬(∃b ∈ A a ≺ b)

Minimal (dans A, ≼)

¬(∃b ∈ A b ≺ a)

borne supérieure de X pour (A, ≼)

∀b ∈ X b ≼ a

borne inférieure de X pour (A, ≼)

∀b ∈ X a ≼ b

supremum de X pour (A, ≼)

a est le minimum de l’ensemble des bornes supérieures de X pour (A, ≼)

l’infimum de X pour (A, ≼)

a est le maximum de l’ensemble des bornes inférieures de X pour (A, ≼)

Soit (A, ≼) un ensemble ordonn´e. On dit que (A, ≼) est un treilli ssi

toute paire d’éléments {a, b} ⊆ A possède un infimum et un supremum

Soit (A, ) un ensemble totalement ordonnée. On dit que (A, ≼ ) est **bien** **ordonné** ssi

tout sous-ensemble non vide de A admet un minimum

Soit (A, R) un ensemble ordonn´e. Soit ≼ ⊆ A × A un ordre total sur A. On dit que ≼ est compatible avec R ssi

∀a ∈ A ∀b ∈ A **aRb ⇒ a ≼ b**

Soit (A, ≼) un ensemble ordonné ordre strict, l’ordre strict ≺

a ≼ b ∧ a ≠ b

Composition de relations de R1 ◦ R2

{ (a, c) ∈ A × C | ∃b ∈ B aR1b ∧ bR2c }