L’ensemble \(\mathbb{N}\)

Dieu a fait les nombres entiers, tout le reste est l’œuvre de l’homme.

Leopold Kronecker

Les axiomes de Peano

L’ensemble \(\mathbb{N}\) est défini axiomatiquement par les axiomes de Peano (1889) :

1. \(0 \in \mathbb{N}\).

2. Tout entier \(n\) possède un successeur \(S(n) \in \mathbb{N}\).

3. \(0\) n’est le successeur d’aucun entier : \(\forall n \in \mathbb{N},\ S(n) \neq 0\).

4. \(S\) est injective : \(S(m) = S(n) \implies m = n\).

5. Principe de récurrence : Toute partie de \(\mathbb{N}\) contenant \(0\) et stable par \(S\) est égale à \(\mathbb{N}\) tout entier.

Le cinquième axiome est précisément le principe de récurrence : si \(A \subseteq \mathbb{N}\), \(0 \in A\), et \(n \in A \implies S(n) \in A\), alors \(A = \mathbb{N}\).

Remarque 17

On pose \(S(0) = 1\), \(S(1) = 2\), etc. L’axiome 4 garantit que la suite \(0, 1, 2, \ldots\) ne bouclera jamais. L’axiome 3 garantit que \(0\) est le « premier » élément. Ces axiomes caractérisent \(\mathbb{N}\) à isomorphisme près.

Principes de récurrence

Proposition 29 (Récurrence simple)

Soit \(P(n)\) un prédicat sur \(\mathbb{N}\), \(k \in \mathbb{N}\). Si \(P(k)\) est vraie (initialisation) et si \(\forall n \geq k,\ P(n) \implies P(n+1)\) (hérédité), alors \(P(n)\) est vraie pour tout \(n \geq k\).

Proof. L’ensemble \(A = \{n \in \mathbb{N} \mid n < k\} \cup \{n \geq k \mid P(n)\}\) contient \(0\) (car \(0 < k\) ou \(P(0)\) vraie) et est stable par \(S\) (l’hérédité assure que si \(n \in A\), alors \(n+1 \in A\)). Par l’axiome 5, \(A = \mathbb{N}\), donc \(P(n)\) est vraie pour tout \(n \geq k\).

Proposition 30 (Récurrence forte)

Si \(\forall n \in \mathbb{N},\ \bigl(\forall k < n,\ P(k)\bigr) \implies P(n)\), alors \(P(n)\) est vraie pour tout \(n \in \mathbb{N}\).

Proof. Posons \(Q(n) = \forall k \leq n,\ P(k)\). Alors \(Q(0)\) est vraie si \(P(0)\) l’est (qui suit de l’hypothèse avec \(n = 0\), la prémisse \(\forall k < 0\) étant vacuement vraie). Si \(Q(n)\) est vraie, l’hypothèse avec \(n+1\) donne \(P(n+1)\), donc \(Q(n+1)\) est vraie. Par récurrence simple, \(Q(n)\) est vraie pour tout \(n\), donc \(P(n)\) aussi.

Proposition 31 (Descente infinie (Fermat))

Il n’existe pas de suite strictement décroissante d’entiers naturels.

Corollaire : tout prédicat \(P\) vérifiant « \(\lnot P(n) \implies \exists m < n,\ \lnot P(m)\) » est vrai pour tout \(n\).

Proof. Supposons par l’absurde qu’il existe \((a_n)\) strictement décroissante dans \(\mathbb{N}\). L’ensemble \(A = \{a_n \mid n \in \mathbb{N}\}\) est non vide dans \(\mathbb{N}\), donc admet un minimum \(m = a_N\) (par le principe du bon ordre, voir ci-dessous). Mais \(a_{N+1} < a_N = m\), contredisant la minimalité.

Proposition 32 (Principe du bon ordre)

Toute partie non vide de \(\mathbb{N}\) admet un plus petit élément.

Proof. Soit \(A \subseteq \mathbb{N}\) non vide. Posons \(P(n) = \lnot(\exists k \leq n,\ k \in A)\) (aucun entier \(\leq n\) n’est dans \(A\)). Si \(P(n)\) est vraie pour tout \(n\), alors \(A = \varnothing\), contradiction. Donc \(P(n)\) est fausse pour un certain \(n\), c’est-à-dire il existe \(k \leq n\) avec \(k \in A\). Le minimum d’un tel \(k\) est le plus petit élément de \(A\).

Exemple 18

Récurrence forte : Montrons que tout entier \(n \geq 2\) possède un diviseur premier.

Pour \(n = 2\) : \(2\) est premier, donc diviseur premier de lui-même.

Si \(n \geq 3\) : soit \(n\) est premier (c’est lui-même), soit \(n = ab\) avec \(2 \leq a, b < n\). Par hypothèse de récurrence forte, \(a\) possède un diviseur premier \(p\). Comme \(p \mid a\) et \(a \mid n\), \(p \mid n\).

Show code cell source

Hide code cell source

import math
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
from matplotlib.patches import FancyBboxPatch

sns.set_theme(style="whitegrid", palette="muted", font_scale=1.1)

Show code cell source

Hide code cell source

# Visualisation : récurrence et quelques suites classiques
fig, axes = plt.subplots(3, 1, figsize=(9, 14))

n_max = 20
n = np.arange(1, n_max + 1)

# Somme des n premiers entiers
sommes = n * (n + 1) // 2
factorielles = np.array([math.factorial(k) for k in n])

# Figure 1 : somme 1+2+...+n
ax = axes[0]
ax.bar(n, sommes, color='#3498db', alpha=0.7, label=r'$S_n = \frac{n(n+1)}{2}$')
ax.plot(n, n * (n + 1) / 2, 'r--', lw=2, label='Formule $n(n+1)/2$')
ax.set_xlabel('$n$'); ax.set_ylabel('$S_n$')
ax.set_title(r'Somme $\sum_{k=1}^n k = \frac{n(n+1)}{2}$' '\n(prouvé par récurrence)', fontsize=10)
ax.legend(fontsize=9)

# Figure 2 : inégalité de Bernoulli (1+h)^n >= 1+nh, h=0.2
h = 0.2
bernoulli_left  = (1 + h)**n
bernoulli_right = 1 + n * h

ax2 = axes[1]
ax2.plot(n, bernoulli_left, 'o-', label=r'$(1+h)^n$, $h=0.2$', color='#e74c3c')
ax2.plot(n, bernoulli_right, 's--', label=r'$1+nh$', color='#3498db')
ax2.fill_between(n, bernoulli_right, bernoulli_left, alpha=0.2, color='green',
                 label='Écart')
ax2.set_xlabel('$n$'); ax2.set_ylabel('Valeur')
ax2.set_title('Inégalité de Bernoulli\n$(1+h)^n \\geq 1 + nh$', fontsize=10)
ax2.legend(fontsize=9)

# Figure 3 : comparaison n!, 2^n, n^2
ax3 = axes[2]
n_comp = np.arange(1, 13)
fact_c = np.array([math.factorial(k) for k in n_comp])
pow2_c = 2.0**n_comp
nsq_c  = n_comp**2

ax3.semilogy(n_comp, fact_c, 'o-', label='$n!$', color='#e74c3c', lw=2)
ax3.semilogy(n_comp, pow2_c, 's--', label='$2^n$', color='#3498db', lw=2)
ax3.semilogy(n_comp, nsq_c, '^:', label='$n^2$', color='#2ecc71', lw=2)
ax3.set_xlabel('$n$'); ax3.set_ylabel('(échelle log)')
ax3.set_title('Comparaison $n!$, $2^n$, $n^2$\n($n! \\geq 2^n$ pour $n \\geq 4$)', fontsize=10)
ax3.legend(fontsize=9)
ax3.axvline(x=4, color='gray', linestyle=':', alpha=0.7)

plt.tight_layout()
plt.show()

Opérations sur \(\mathbb{N}\)

Définition 38 (Addition, multiplication, puissance)

On définit par récurrence, pour \(m, n \in \mathbb{N}\) :

Addition : \(m + 0 = m\), \(m + S(n) = S(m + n)\)

Multiplication : \(m \cdot 0 = 0\), \(m \cdot S(n) = m \cdot n + m\)

Puissance : \(m^0 = 1\), \(m^{S(n)} = m^n \cdot m\)

Proposition 33 (\((\mathbb{N}, +, \cdot)\) est un demi-anneau commutatif)

• \((\mathbb{N}, +)\) est un monoïde commutatif (neutre \(0\))

• \((\mathbb{N}, \cdot)\) est un monoïde commutatif (neutre \(1\), absorbant \(0\))

• Distributivité : \(m(n + p) = mn + mp\)

Remarque 18

\((\mathbb{N}, +)\) n’est pas un groupe : \(1\) n’a pas d’opposé dans \(\mathbb{N}\). C’est cette limitation qui motive la construction de \(\mathbb{Z}\).

Ordre sur \(\mathbb{N}\)

Définition 39 (Ordre naturel)

\(m \leq n \iff \exists k \in \mathbb{N},\ n = m + k\)

Proposition 34 (\((\mathbb{N}, \leq)\) est un ordre total bien fondé)

• Ordre total : \(\forall m, n,\ m \leq n \lor n \leq m\)

• Bien fondé (bon ordre) : toute partie non vide admet un minimum

Divisibilité et arithmétique

Définition 40 (Divisibilité)

\(a \mid b\) (« \(a\) divise \(b\) ») s’il existe \(k \in \mathbb{N}\) tel que \(b = ak\).

Proposition 35 (Division euclidienne)

Pour tout \(a \in \mathbb{N}\) et \(b \in \mathbb{N}^*\), il existe un unique couple \((q, r) \in \mathbb{N}^2\) tel que

\[a = bq + r \quad \text{et} \quad 0 \leq r < b\]

Proof. Existence : Par récurrence forte sur \(a\).

• Si \(a < b\) : \(q = 0\), \(r = a\).

• Si \(a \geq b\) : appliquer l’hypothèse à \(a - b\) (qui est dans \(\mathbb{N}\) car \(a \geq b\)) : \(a - b = bq' + r'\), d’où \(a = b(q'+1) + r'\).

Unicité : Si \(bq_1 + r_1 = bq_2 + r_2\), alors \(b|q_1 - q_2| = |r_2 - r_1| < b\), donc \(q_1 = q_2\) et \(r_1 = r_2\).

Définition 41 (PGCD et PPCM)

Le PGCD de \(a, b\) (non tous deux nuls) est le plus grand diviseur commun, noté \(\pgcd(a, b)\) ou \(a \wedge b\). Le PPCM de \(a, b \in \mathbb{N}^*\) est le plus petit multiple commun non nul, noté \(\ppcm(a, b)\) ou \(a \vee b\).

Proposition 36 (Algorithme d’Euclide)

Si \(a = bq + r\), alors \(\pgcd(a, b) = \pgcd(b, r)\).

L’algorithme d’Euclide calcule \(\pgcd(a, b)\) en \(O(\log \min(a,b))\) divisions.

Proof. Tout diviseur commun de \(a\) et \(b\) divise \(r = a - bq\), donc divise \(b\) et \(r\). Réciproquement. Donc l’ensemble des diviseurs communs de \((a,b)\) et \((b,r)\) est le même.

Proposition 37 (Relation entre PGCD et PPCM)

\[\pgcd(a, b) \cdot \ppcm(a, b) = a \cdot b\]

Proof. Soient \(d = \pgcd(a,b)\), \(a = da'\), \(b = db'\) avec \(\pgcd(a', b') = 1\). Le ppcm est \(da'b' = \frac{ab}{d}\).

Nombres premiers

Définition 42 (Nombre premier)

Un entier \(p \geq 2\) est premier s’il n’admet comme diviseurs positifs que \(1\) et \(p\).

Proposition 38 (Infinité des nombres premiers (Euclide))

Il existe une infinité de nombres premiers.

Proof. Si \(p_1, \ldots, p_k\) sont tous les premiers, alors \(N = p_1 \cdots p_k + 1\) est divisible par un premier \(p\). Mais \(p \neq p_i\) pour tout \(i\) (sinon \(p \mid 1\)). Contradiction.

Proposition 39 (Théorème fondamental de l’arithmétique)

Tout entier \(n \geq 2\) s’écrit de façon unique comme produit de nombres premiers (à l’ordre près) :

\[n = p_1^{\alpha_1} \cdots p_k^{\alpha_k}, \quad p_1 < p_2 < \cdots < p_k \text{ premiers}, \quad \alpha_i \geq 1\]

Proof. Existence : par récurrence forte (cf. exemple précédent).

Unicité : Supposons \(n = p_1^{\alpha_1} \cdots = q_1^{\beta_1} \cdots\). Alors \(p_1 \mid q_1^{\beta_1} \cdots q_l^{\beta_l}\). Par le lemme d’Euclide (voir chapitre 5), \(p_1 \mid q_j\) pour un \(j\). Comme \(q_j\) est premier, \(p_1 = q_j\). On simplifie par \(p_1\) et on conclut par récurrence sur \(\sum \alpha_i\).

Définition 43 (Valuation \(p\)-adique)

Pour \(p\) premier et \(n \in \mathbb{N}^*\), la valuation \(p\)-adique \(v_p(n)\) est l’exposant de \(p\) dans la décomposition de \(n\) :

\[n = \prod_p p^{v_p(n)}\]

Remarque 19

On a les formules :

\[v_p(\pgcd(a,b)) = \min(v_p(a), v_p(b)), \quad v_p(\ppcm(a,b)) = \max(v_p(a), v_p(b))\]

\[\pgcd(a,b) \cdot \ppcm(a,b) = a \cdot b \text{ (car }\min + \max = \text{somme)}\]

Show code cell source

Hide code cell source

# Algorithme d'Euclide visualisé + crible d'Ératosthène
fig, axes = plt.subplots(2, 1, figsize=(9, 11))

# --- Algorithme d'Euclide ---
def euclide_steps(a, b):
    steps = []
    while b:
        q, r = divmod(a, b)
        steps.append((a, b, q, r))
        a, b = b, r
    return steps, a

a0, b0 = 252, 198
steps, gcd_val = euclide_steps(a0, b0)

ax = axes[0]
y_pos = np.arange(len(steps), 0, -1)
colors_step = plt.cm.Blues(np.linspace(0.4, 0.9, len(steps)))

for i, ((a, b, q, r), y, col) in enumerate(zip(steps, y_pos, colors_step)):
    ax.add_patch(FancyBboxPatch((0.05, y - 0.38), 0.9, 0.72,
                 boxstyle='round,pad=0.03', facecolor=col, alpha=0.7, edgecolor='black'))
    ax.text(0.5, y,
            f'${a} = {b} \\times {q} + {r}$',
            ha='center', va='center', fontsize=11,
            color='white' if i > len(steps)//2 else 'black')

ax.add_patch(FancyBboxPatch((0.15, 0.12), 0.7, 0.5,
             boxstyle='round,pad=0.05', facecolor='#2ecc71', alpha=0.8))
ax.text(0.5, 0.37, f'$\\mathrm{{pgcd}}({a0}, {b0}) = {gcd_val}$',
        ha='center', va='center', fontsize=13, fontweight='bold', color='white')

ax.set_xlim(0, 1); ax.set_ylim(0, len(steps) + 0.8)
ax.axis('off')
ax.set_title(f'Algorithme d\'Euclide\n$\\mathrm{{pgcd}}({a0}, {b0}) = {gcd_val}$', fontsize=11)

# --- Crible d'Ératosthène ---
N = 100
is_prime = np.ones(N + 1, dtype=bool)
is_prime[0] = is_prime[1] = False
for i in range(2, int(N**0.5) + 1):
    if is_prime[i]:
        is_prime[i*i::i] = False

grid = is_prime[1:N+1].reshape(10, 10).astype(float)

ax2 = axes[1]
im = ax2.imshow(grid, cmap='RdYlGn', vmin=0, vmax=1)
for i in range(10):
    for j in range(10):
        n_val = i * 10 + j + 1
        color = 'white' if is_prime[n_val] else 'black'
        weight = 'bold' if is_prime[n_val] else 'normal'
        ax2.text(j, i, str(n_val), ha='center', va='center',
                fontsize=9, color=color, fontweight=weight)

ax2.set_xticks([]); ax2.set_yticks([])
ax2.set_title(f'Crible d\'Ératosthène (1 à {N})\n(vert = premier, rouge = composé)', fontsize=10)

n_primes = np.sum(is_prime[1:N+1])
ax2.text(5, 10.5, f'{n_primes} premiers $\\leq {N}$', ha='center', fontsize=10)

plt.tight_layout()
plt.show()

Show code cell source

Hide code cell source

# Distribution des nombres premiers : théorème des nombres premiers
fig, axes = plt.subplots(2, 1, figsize=(9, 9))

N_max = 1000
is_prime_arr = np.ones(N_max + 1, dtype=bool)
is_prime_arr[0] = is_prime_arr[1] = False
for i in range(2, int(N_max**0.5) + 1):
    if is_prime_arr[i]:
        is_prime_arr[i*i::i] = False

primes = np.where(is_prime_arr)[0]
x_vals = np.arange(2, N_max + 1)

# Pi(x) vs x/ln(x)
pi_x = np.cumsum(is_prime_arr[2:N_max+1])
approx_tnp = x_vals / np.log(x_vals)

ax = axes[0]
ax.plot(x_vals, pi_x, 'b-', lw=2, label=r'$\pi(x)$ (comptage exact)')
ax.plot(x_vals, approx_tnp, 'r--', lw=2, label=r'$x / \ln x$ (approx. TNP)')
ax.set_xlabel('$x$'); ax.set_ylabel('Nombre de premiers $\\leq x$')
ax.set_title('Théorème des nombres premiers\n$\\pi(x) \\sim x / \\ln x$', fontsize=10)
ax.legend()

# Gaps entre premiers consécutifs
gaps = np.diff(primes)
ax2 = axes[1]
ax2.scatter(primes[:-1], gaps, s=10, alpha=0.5, color='#e74c3c')
ax2.set_xlabel('Nombre premier $p$')
ax2.set_ylabel('Écart $p_{n+1} - p_n$')
ax2.set_title('Écarts entre nombres premiers consécutifs\n(Jumeaux : écart = 2)', fontsize=10)
twin_primes = primes[:-1][gaps == 2]
ax2.scatter(twin_primes, np.full_like(twin_primes, 2), s=30, color='#2ecc71',
           label=f'{len(twin_primes)} paires de jumeaux $\\leq {N_max}$', zorder=5)
ax2.legend(fontsize=9)

plt.tight_layout()
plt.show()

Formules sommatoires classiques

Proposition 40 (Sommes de référence)

Pour tout \(n \in \mathbb{N}\) :

\[\sum_{k=0}^{n} k = \frac{n(n+1)}{2}, \qquad \sum_{k=0}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}, \qquad \sum_{k=0}^{n} k^3 = \left(\frac{n(n+1)}{2}\right)^2\]

\[\sum_{k=0}^{n} q^k = \frac{1-q^{n+1}}{1-q}\ (q \neq 1), \qquad \binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{n} = 2^n\]

Définition 44 (Coefficients binomiaux)

\[\binom{n}{k} = \frac{n!}{k!(n-k)!} \quad (0 \leq k \leq n)\]

Proposition 41 (Triangle de Pascal et formule du binôme)

• Relation de Pascal : \(\binom{n+1}{k+1} = \binom{n}{k} + \binom{n}{k+1}\)

• Formule du binôme de Newton : \((a+b)^n = \displaystyle\sum_{k=0}^{n} \binom{n}{k} a^k b^{n-k}\)

Proof. Relation de Pascal : par un argument combinatoire (on choisit si le \((n+1)\)-ième élément est dans le sous-ensemble ou non) ou par calcul direct.

Binôme : par récurrence sur \(n\), en utilisant la relation de Pascal pour passer de \((a+b)^n\) à \((a+b)^{n+1} = (a+b)(a+b)^n\).

Show code cell source

Hide code cell source

# Triangle de Pascal et formule du binôme
fig, axes = plt.subplots(2, 1, figsize=(9, 11))

# Triangle de Pascal
n_pascal = 10
pascal = [[math.comb(i, j) for j in range(i+1)] for i in range(n_pascal)]

ax = axes[0]
ax.axis('off')
for i, row in enumerate(pascal):
    for j, val in enumerate(row):
        x = j - i/2
        y = -i
        color = plt.cm.Blues(val / max(max(r) for r in pascal))
        ax.add_patch(plt.Circle((x, y), 0.4, color=color, alpha=0.8))
        ax.text(x, y, str(val), ha='center', va='center',
                fontsize=9 if val < 100 else 7,
                color='white' if val > 20 else 'black')

ax.set_xlim(-5.5, 5.5); ax.set_ylim(-n_pascal, 1)
ax.set_title('Triangle de Pascal\n$\\binom{n+1}{k} = \\binom{n}{k-1} + \\binom{n}{k}$', fontsize=11)

# Formule du binôme : (1+x)^n pour n=0,...,5
ax2 = axes[1]
x = np.linspace(-0.9, 1.5, 300)
colors_n = plt.cm.viridis(np.linspace(0.1, 0.9, 6))
for n_val, col in zip(range(6), colors_n):
    ax2.plot(x, (1 + x)**n_val, color=col, lw=2, label=f'$n={n_val}$')

ax2.axhline(0, color='black', lw=0.5)
ax2.axvline(0, color='black', lw=0.5)
ax2.set_xlabel('$x$'); ax2.set_ylabel('$(1+x)^n$')
ax2.set_title('Formule du binôme : $(1+x)^n$\n(développement en somme de monômes)', fontsize=10)
ax2.legend(fontsize=9); ax2.set_ylim(-1, 8)
ax2.grid(True, alpha=0.3)

plt.tight_layout()
plt.show()

Quelques inégalités fondamentales

Proposition 42 (Inégalité de Bernoulli)

Pour tout \(h \geq -1\) et \(n \in \mathbb{N}\) :

\[(1 + h)^n \geq 1 + nh\]

Proof. Par récurrence sur \(n\).

• \(n = 0\) : \(1 \geq 1\). ✓

• Hérédité : \((1+h)^{n+1} = (1+h)^n(1+h) \geq (1+nh)(1+h) = 1 + (n+1)h + nh^2 \geq 1 + (n+1)h\).

Proposition 43 (Inégalité arithmético-géométrique (IAG))

Pour tous \(a_1, \ldots, a_n \geq 0\) :

\[\frac{a_1 + \cdots + a_n}{n} \geq (a_1 \cdots a_n)^{1/n}\]

avec égalité si et seulement si \(a_1 = \cdots = a_n\).

Proof. Par récurrence sur \(n\) (preuve de Cauchy par « récurrence en avant et en arrière »).

• \(n = 2\) : \((a_1 - a_2)^2 \geq 0 \implies a_1^2 + a_2^2 \geq 2a_1 a_2 \implies \frac{a_1 + a_2}{2} \geq \sqrt{a_1 a_2}\).

• \(n = 2^k\) : si vrai pour \(n\), alors vrai pour \(2n\) en groupant par paires.

• \(n \to n-1\) : si vrai pour \(n\) avec \(a_n = \frac{a_1 + \cdots + a_{n-1}}{n-1}\), on obtient l’inégalité pour \(n-1\).

Remarque 20

Cette inégalité a de nombreuses applications : optimisation, preuves d’inégalités classiques, convergence de suites récurrentes.