Les scripts du chapitre

Quatre programmes, un par grande scène du chapitre. Chacun se copie tel quel dans votre éditeur ; aucun ne demande de bibliothèque à installer, cmath et math étant fournis avec Python. Toutes les sorties affichées ici sont des sorties réelles, recopiées de la console sans retouche.

1. La formule de del Ferro-Cardan, exécutée

Le cours démontre que, pour tous $p \in \mathbb{R}$ et $q \in \mathbb{R}$, le réel $\sqrt[3]{\dfrac{q}{2}+\sqrt{\Delta_C}} + \sqrt[3]{\dfrac{q}{2}-\sqrt{\Delta_C}}$ résout $x^3 = px+q$ lorsque $\Delta_C = \left(\dfrac{q}{2}\right)^2 - \left(\dfrac{p}{3}\right)^3$ est positif ou nul, et que le cas $\Delta_C < 0$ est précisément celui où l’équation possède trois racines réelles distinctes. C’est le paradoxe fondateur du chapitre : la formule réclame une racine carrée de nombre négatif exactement quand la réponse est la plus abondamment réelle.

Le programme ci-dessous ne le contourne pas, il l’assume. Il utilise cmath.sqrt, la racine carrée des nombres complexes, qui ne proteste jamais. Et plutôt que de calculer deux racines cubiques indépendamment, au risque de tomber sur un couple qui ne convient pas, il en calcule une et impose l’autre par la condition $3uv = p$, celle que la note de marge du cours désigne comme la clé de la démonstration.

import cmath


def cardan(p, q, trace=False):
    """Une racine de l'equation x^3 = p x + q,
    par la formule de del Ferro-Cardan."""
    delta = (q / 2) ** 2 - (p / 3) ** 3      # le critere du cours
    u3 = q / 2 + cmath.sqrt(delta)           # racine carree COMPLEXE : toujours definie
    u = u3 ** (1 / 3)                        # une racine cubique, au choix
    v = p / (3 * u)                          # la condition 3uv = p, imposee
    if trace:
        print(f"   Delta_C = {delta:+.0f}   u = {u:.6f}   v = {v:.6f}")
    return u + v


for p, q in [(9, 28), (30, 36)]:
    print(f"x^3 = {p}x + {q}")
    x = cardan(p, q, trace=True)
    print(f"   x = {x:.6f}")
    print(f"   controle : x^3 - {p}x - {q} = {x**3 - p*x - q:.1e}")

print()
print("(3+i)^3 =", (3 + 1j) ** 3)

Les deux équations testées sont celles des exercices $24$ et $25$ de l’Atelier.

x^3 = 9x + 28
   Delta_C = +169   u = 3.000000+0.000000j   v = 1.000000+0.000000j
   x = 4.000000+0.000000j
   controle : x^3 - 9x - 28 = 0.0e+00+0.0e+00j
x^3 = 30x + 36
   Delta_C = -676   u = 3.000000+1.000000j   v = 3.000000-1.000000j
   x = 6.000000-0.000000j
   controle : x^3 - 30x - 36 = 0.0e+00-3.5e-14j

(3+i)^3 = (18+26j)

Lisez les deux blocs l’un contre l’autre. Dans le premier, $\Delta_C = +169$, les quantités intermédiaires $u = 3$ et $v = 1$ sont réelles, et la partie imaginaire de la réponse est nulle au bit près. Dans le second, $\Delta_C = -676$, et les quantités intermédiaires sont $3+i$ et $3-i$ : elles ne sont pas réelles, elles ne peuvent pas l’être, et pourtant leur somme vaut $6$. La partie imaginaire résiduelle, $-3{,}5 \cdot 10^{-14}$, n’est pas un reste de mathématiques mais un reste d’arrondi : elle mesure la précision des flottants, rien d’autre.

La dernière ligne est le contrôle demandé par l’exercice $25$, et Python le confirme sans détour : $(3+i)^3 = 18+26i$. C’est exactement le nombre sous le radical cubique, et reconnaître ce cube est le geste que Bombelli a osé le premier, en $1572$, sur une autre équation : c’est ainsi qu’il a pu écrire la réponse à la main.

2. Cornacchia, ou la fabrication des deux carrés

Le théorème de Noël garantit que tout nombre premier de la forme $4k+1$ est somme de deux carrés, sans jamais les produire. L’algorithme de Cornacchia, expliqué sur la page voisine, les produit : il applique l’algorithme d’Euclide ordinaire au couple $(p\,;m)$, où $m$ est l’entier du résultat R4, celui pour lequel $p$ divise $m^2+1$, et s’arrête au premier reste passé sous $\sqrt{p}$.

from math import isqrt


def racine_de_moins_un(p):
    """Cherche m tel que m^2 + 1 soit divisible par p."""
    for m in range(2, p):
        if (m * m + 1) % p == 0:
            return m
    return None


def cornacchia(p):
    """Ecrit p = x^2 + y^2 pour p premier de la forme 4k+1."""
    m = racine_de_moins_un(p)
    if m is None:
        return None
    a, b = p, m
    limite = isqrt(p)
    while b > limite:
        a, b = b, a % b            # une etape d'Euclide, dans Z
    x = b
    y = isqrt(p - x * x)
    return (x, y) if x * x + y * y == p else None


for p in (61, 89, 97, 101, 1009, 3001):
    x, y = cornacchia(p)
    print(f"{p:>5} = {x}^2 + {y}^2      controle : {x*x + y*y}")

print()
print("trace pour p = 89 :")
a, b = 89, racine_de_moins_un(89)
while b > isqrt(89):
    q = a // b
    print(f"   {a} = {q} x {b} + {a % b}")
    a, b = b, a % b
print("   premier reste sous racine de 89 :", b)

   61 = 6^2 + 5^2      controle : 61
   89 = 8^2 + 5^2      controle : 89
   97 = 9^2 + 4^2      controle : 97
  101 = 10^2 + 1^2      controle : 101
 1009 = 28^2 + 15^2      controle : 1009
 3001 = 51^2 + 20^2      controle : 3001

trace pour p = 89 :
   89 = 2 x 34 + 21
   34 = 1 x 21 + 13
   21 = 1 x 13 + 8
   premier reste sous racine de 89 : 8

Trois divisions pour $89$, une poignée pour $3\,001$. Mais regardez où se cache la dépense réelle : dans racine_de_moins_un, qui balaie tous les entiers jusqu’à $p$. C’est cette fonction, et elle seule, qui empêche le programme de traiter un nombre premier à trente chiffres. L’algorithme de Cornacchia, lui, resterait instantané. La leçon est nette : la difficulté du problème n’est pas là où l’énoncé la place. Une fois $m$ trouvé, les deux carrés ne coûtent presque rien.

3. Suivez un point : le test d’échappement

La pièce n°6 des Coulisses fait suivre l’orbite de $z_{n+1} = z_n^{\,2} + c$ à partir de $z_0 = 0$, et laisse une question en suspens : comment une machine décide-t-elle qu’une orbite s’échappe ? Le critère est annoncé là-bas, et le chapitre C2 l’énoncera dans son langage propre. On peut cependant l’écrire dès maintenant, avec la seule norme du chapitre : l’orbite est perdue dès qu’un terme vérifie $\mathrm{N}(z) > 4$.

def echappe(c, n_max=300):
    """Rang du premier terme de norme superieure a 4, ou None si l'orbite
    reste confinee pendant n_max etapes."""
    z = 0
    for n in range(n_max):
        z = z * z + c
        if z.real ** 2 + z.imag ** 2 > 4:      # N(z) > 4
            return n + 1
    return None


for c in (1, -1, 1j, 0.25, 0.26, -1.5, -2.5, -0.12 + 0.75j, 0.3 + 0.5j):
    print(f"c = {c!s:>12}   ->   {echappe(c)}")

print()
print("orbite de c = i :")
z = 0
for n in range(5):
    z = z * z + 1j
    print("  z_%d = %s" % (n + 1, z))

c =            1   ->   3
c =           -1   ->   None
c =           1j   ->   None
c =         0.25   ->   None
c =         0.26   ->   30
c =         -1.5   ->   None
c =         -2.5   ->   1
c = (-0.12+0.75j)   ->   None
c =   (0.3+0.5j)   ->   None

orbite de c = i :
  z_1 = 1j
  z_2 = (-1+1j)
  z_3 = -1j
  z_4 = (-1+1j)
  z_5 = -1j

Les trois valeurs des Coulisses sont confirmées : $c = 1$ s’échappe au troisième terme, $c = -1$ et $c = i$ ne s’échappent pas, et la seconde moitié de la sortie exhibe le cycle de longueur $2$ calculé à la main dans la pièce, entre $-1+i$ et $-i$.

Les deux lignes à méditer sont celles du milieu. Pour $c = 0{,}25$ l’orbite reste confinée, pour $c = 0{,}26$ elle s’échappe au trentième terme : une variation de quatre centièmes fait basculer le destin, et l’on vient de toucher le bord de l’ensemble de Mandelbrot avec une boucle de six lignes. Notez enfin le sens exact de None : il signifie « pas d’échappement observé en trois cents étapes », et non « orbite confinée ». Le programme constate, il ne démontre pas. C’est le théorème du chapitre C2 qui transformera le seuil $\mathrm{N}(z) > 4$ en certitude, en garantissant qu’une orbite qui franchit ce seuil ne revient jamais.

4. Le tri des sommes de deux carrés

Dernier programme, et il sert à observer un théorème, pas à le démontrer. On trie les entiers d’un intervalle selon qu’ils sont ou non sommes de deux carrés, puis on compare ce tri à celui que prédit le critère sur les facteurs premiers de la forme $4k+3$.

Une précaution sur l’intervalle choisi. Le devoir vous fait explorer les petits entiers, et son annexe vous donne le programme pour le faire ; publier ici la sortie de cette exploration reviendrait à répondre à sa place. On regarde donc la centaine suivante, de $101$ à $200$, où le phénomène est exactement le même et où rien n’est demandé.

from math import isqrt


def deux_carres(n):
    """Force brute : cherche a <= b tels que n = a^2 + b^2."""
    a = 0
    while 2 * a * a <= n:
        reste = n - a * a
        b = isqrt(reste)
        if b * b == reste:
            return (a, b)
        a += 1
    return None


def facteurs(n):
    """Decomposition en facteurs premiers, sous forme {premier: exposant}."""
    d, f = 2, {}
    while d * d <= n:
        while n % d == 0:
            f[d] = f.get(d, 0) + 1
            n //= d
        d += 1
    if n > 1:
        f[n] = f.get(n, 0) + 1
    return f


def critere(n):
    """Tout facteur premier de la forme 4k+3 a-t-il un exposant pair ?"""
    return all(e % 2 == 0 for p, e in facteurs(n).items() if p % 4 == 3)


domaine = range(101, 201)
oui = [n for n in domaine if deux_carres(n) is not None]
print(len(oui), "entiers sur 100 sont sommes de deux carres")
print("les deux tris coincident :",
      all((deux_carres(n) is not None) == critere(n) for n in domaine))

print()
for n in (103, 117, 154, 198):
    print(n, facteurs(n), deux_carres(n))

36 entiers sur 100 sont sommes de deux carres
les deux tris coincident : True

103 {103: 1} None
117 {3: 2, 13: 1} (6, 9)
154 {2: 1, 7: 1, 11: 1} None
198 {2: 1, 3: 2, 11: 1} None

La deuxième ligne est le cœur de l’expérience : sur les cent entiers testés, la recherche par force brute et la lecture des exposants donnent toujours le même verdict. Les quatre exemples détaillés en donnent le grain. Le nombre $103$ est premier et congru à $3$ modulo $4$ : il refuse, et c’est la moitié facile du théorème. Le nombre $117 = 3^2 \times 13$ contient bien un facteur $3$, mais au carré, et il accepte : $117 = 6^2+9^2$. Le nombre $154 = 2 \times 7 \times 11$ cumule deux facteurs congrus à $3$, chacun à l’exposant $1$, et refuse. Le plus instructif est $198 = 2 \times 3^2 \times 11$ : son facteur $3$ est à l’exposant pair, il ne gêne pas, mais le facteur $11$ est seul, et il suffit à tout bloquer. Un exposant impair, un seul, condamne le nombre.

Reste à dire ce que cette sortie ne dit pas. Cent entiers vérifiés ne démontrent rien, et la ligne True n’est pas une preuve : c’est un accord constaté sur un échantillon fini. Le sens facile du critère se démontre en quelques lignes, le sens difficile occupe un devoir entier, et sa réciproque une page de plus. L’ordinateur trie ; il ne conclut pas.

Sources

• Cours C1, section 2, pour la formule de del Ferro-Cardan, le critère $\Delta_C$ et la condition $3uv = p$ ; Atelier C1, exercices $24$ et $25$, pour les deux cubiques et le contrôle $(3+i)^3 = 18+26i$.
• Coulisses C1, pièce n°6, Suivez un point, pour l’itération $z \mapsto z^2+c$, les trois valeurs de $c$ testées à la main et le critère d’échappement annoncé.
• Page voisine, Le PGCD gaussien et l’algorithme de Cornacchia, pour la justification du deuxième programme ; page La descente d’Euler, et la réciproque pour le critère qu’observe le quatrième.
• Tous les scripts de cette page ont été exécutés avant publication, sous Python $3.13$, sans bibliothèque extérieure ; les blocs de sortie sont recopiés de la console.