Lipsum.dev

Introduction à l'arithmétique

11 avril 2020 — Introduction, Python

Les entiers naturels, pour compter avec nos doigts

Les entiers naturels N\N, c’est l’ensemble des nombres suivants : 0,1,2,3,...0, 1, 2, 3, ...

Ils portent plutôt bien leur nom, car ils sont effectivement très intuitifs et tout le monde comprend leur sens : ce sont ceux que l’on utilise pour compter des objets.

💡 Mathématiquement, ils peuvent être définis à partir des cinq axiomes de Peano, que je mentionne sans plus de détails car l’intuition naturelle qu’on a des entiers sera suffisante pour cet article.

Divisibilité

On dit qu’un entier aa est divisible par un entier b,b0b, b \neq 0 s’il existe un entier kk tel que a=k×ba = k \times b.

On peut visualiser ce concept comme la possibilité de regrouper par lots. Par exemple, 66 est divisible par 2 et par 3 :

🍋🍋🍋🍋🍋🍋=🍋🍋+🍋🍋+🍋🍋=🍋🍋🍋+🍋🍋🍋🍋🍋🍋🍋🍋🍋 = 🍋🍋+🍋🍋+🍋🍋 = 🍋🍋🍋+🍋🍋🍋

Les nombres premiers

Parmi ces nombres, certains ont une propriété particulière.

Un nombre premier est un nombre qui ne se casse pas quand on le laisse tomber par terre. (P. Erdős)

Un entier nNn \isin \N est dit premier s’il n’admet que deux diviseurs : 11 et nn lui-même (11 n’est pas considéré premier).

Par exemple, les nombres 2,3,5,7,112, 3, 5, 7, 11 sont premiers : pour vous en convaincre, essayez de ranger cinq 🍋 en lots de 22, 33 ou 44.

La division euclidienne

Si vous prenez un nombre aa d’objets, et essayez de les répartir entre bb personnes, il n’est pas sûr que vous puissiez y arriver. Par exemple, si a=8{a = 8} et b=3{b = 3}, vous allez en donner un au premier, le suivant au second, etc. et il va vous en rester deux dans les mains après avoir partagé les six premiers, car 8=3×2+2{8 = 3 \times 2 + 2}.

La division euclidienne généralise ce procédé.

aa et bb étant des entiers naturels, avec b0b \neq 0, il existe des entiers naturels qq (quotient) et rr (reste) uniques vérifiant :
a=b×q+ra = b \times q + r et 0r<b0 \leq r \lt b

Je laisse le lecteur vérifier que si une telle décomposition existe, alors elle est unique. Pour montrer son existence, une approche est de décrire un algorithme pour obtenir qq et rr.

💻 L’algorithme Python ci-dessous permet d’obtenir cette décomposition (note: cet algorithme n’est pas optimal).

def euclidean_division(a, b):
q, r = 0, a
while r >= b:
r -= b
q += 1
return (q, r)
>>> euclidean_division(8, 3)
(2, 2) # 8 = 3 * 2 + 2
>>> euclidean_division(2020, 51)
(39, 31) # 2020 = 51 * 39 + 31

On vérfie que l’égalité a=b×q+ra = b \times q + r est un invariant de boucle car à chaque itération rr décroit de bb et qq augmente de 11.

Ceci permet de prouver que cet algorithme termine après un nombre fini d’itérations et donne un résultat vérifiant les conditions requises. Mathématiquement, c’est une preuve de l’existence pour notre théorème de division euclidienne.

Questions Python :
  • Que se passe-t-il si on exécute euclidean_division(42, 0) ?
    Quelle exception Python pourrait-on utiliser pour gérer ce cas ?
  • Quels opérateurs natifs de Python peut-on utiliser pour obtenir q et r ?

Les entiers relatifs Z\Z

Comme vous le savez, nous utilisons aussi des nombres négatifs.

💡 D’un point de vue axiomatique, ces nombres peuvent être définis comme des différences : 3-3 est le nombre qui permet de passer de 1010 à 77, ou de façon équivalente de 2525 à 2222 (en savoir plus).

On note l’ensemble des nombres entiers relatifs (positifs, négatifs ou nuls) Z\Z :
Z={...,3,2,1,0,1,2,3,...}\Z = \{..., -3, -2, -1, 0, 1, 2, 3, ...\}

Les entiers relatifs contiennent les entiers naturels, ce qu’on note : NZ\N \subset \Z.

La division euclidienne existe toujours dans Z\Z, mais le quotient peut être négatif.

💻 En exercice, vous pouvez essayer d’adapter la fonction euclidean_division précédente pour qu’elle fonctionne avec a,bZa, b \isin \Z.

Les bases numériques

Nous avons l’habitude d’écrire les nombres en base 10, avec dix chiffres différents 0,1,2,3,4,5,6,7,8,90, 1, 2, 3, 4, 5, 6, 7, 8, 9.

Ce choix est pratique, il permet de compter avec ses mains.

Pour des raisons qui relèvent principalement de l’électronique, le choix de la base 22 (binaire) s’est imposé pour représenter les nombres en informatique (en mémoire, dans les canaux d’échange, etc.).

Ce choix a des conséquences importantes sur lesquelles nous reviendrons.

Le programme ci-dessous permet d’afficher la liste des chiffres d’un entier nNn \isin \N, en base décimale, en commençant par le poids le plus faible. Il n’a évidemment pas d’intérêt autre que didactique, cette fonctionnalité étant native dans tous les langages.

def show_decimals(n):
while n > 0:
n, r = euclidean_division(n, 10)
yield r
>>> print(list(show_decimals(123)))
[3, 2, 1]

Questions :

  • Pourquoi ce programme termine bien ?
  • Modifier le programme pour obtenir la décomposition d’un nombre en base héxadécimale (base 16 avec les chiffres 0123456789abcdef)

Le cas de la base 64

Pour coder des données binaires dans un document texte (par exemple, des images directement dans le code HTML), le codage base64 est souvent utilisé. Concrètement, cela consiste à utiliser les 64 caractères suivant comme chiffres, chacun pouvant encoder 6 bits d’information (64=2664 = 2^6) :

ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/

Le flux de données à encoder étant généralement des octets, l’implémentation présente toutefois quelques subtilités :

  • Les octets sont regroupés par blocs de 3, c’est-à-dire 24 bits (car 24 est le plus petit multiple simultané de 8 et 6…)
  • Chacun de ces blocs est représenté par 4 caractères base64
  • Lorsque les données à encoder ne peuvent pas être regroupées par paquets de 3 octets (ex.: 4 caractères ASCII, sur 4 octets), un symbole = est ajouté à la fin de la chaîne encodée pour chaque octet manquant (pour arriver à un nombre multiple de 3)
  • Une conséquence de ce fonctionnement, est que le contenu encodé en base64 prend plus de place en mémoire que le contenu d’origine, d’un facteur moyen 4/34 / 3

Par exemple, en utilisant la librairie b64encode :

from base64 import b64encode
>>> b64encode(b"foo")
'Zm9v'
>>> b64encode(b"Je pense donc je suis.")
'SmUgcGVuc2UgZG9uYyBqZSBzdWlzLg=='

Questions :

  • Combien de symboles = y aura-t-il en fin de chaîne pour b64encode(b"a") ?

  • Même question avec b64encode("à".encode("utf-8")) ?

  • L’algorithme Base85 encode les séquence de 32 bits en séquences de NN caractères, utilisant un alphabet de 8585 caractères.
    Quelle est la valeur minimale pour NN ?

    Une variante de cet algorithme est utilisée par (ZeroMQ).

PGCD et identité de Bézout

On appelle PGCD (plus grand commun diviseur) de deux entiers non nuls aa et bb (noté gcd(a,b)\gcd(a,b)) le plus grand entier qui divise simultanément aa et bb.

Par exemple :

  • gcd(2,4)=2\gcd(2, -4) = 2
  • gcd(24,40)=8\gcd(24, 40) = 8
  • gcd(2020,13)=1\gcd(2020, 13) = 1 (1313 est premier)

Le résultat qui suit est plus compliqué que la division euclidienne. Si vous avez des difficultés à l’appréhender, c’est tout à fait normal. Il est néanmoins à la base d’une bonne partie de l’arithmétique des entiers et sa preuve peut aussi se faire via un algorithme, raison de plus pour en parler ici 😊

Identité de Bézout

Il existe deux nombres u,vZ{u, v \isin \Z} tels que : u×a+v×b=gcd(a,b){u \times a + v \times b = \gcd(a, b)}

Par exemple : 3×24+2×40=8=gcd(24,40){ -3 \times 24 + 2 \times 40 = 8 = \gcd(24, 40)}

L’algorithme d’Euclide permet de calculer le PGCD de deux nombres par une méthode itérative, et l’analyse de son fonctionnement met en évidence l’identité de Bézout.

En voici une implémentation en Python :

def gcd(a, b):
while b != 0:
q, r = euclidean_division(a, b)
a, b = b, r
return a

Analyse de l’algorithme :

  • À chaque étape de la boucle, aa et bb prennent de nouvelles valeurs an+1a_{n+1} et bn+1b_{n+1}, avecan+1=bnbn+1=anbn×qa_{n+1} = b_n \newline b_{n+1} = a_n - b_n \times qOn en déduit en particulier qu’à chaque iteration :
    • 0bn+1<bn0 \leq b_{n+1} < b_n
    • gcd(an+1,bn+1)=gcd(an,bn)\gcd(a_{n+1}, b_{n+1}) = \gcd(a_n, b_n) — vérifier que tout diviseur commun d’une paire l’est aussi pour l’autre
    • ana_n et bnb_n sont de la forme u×a+v×b{u \times a + v \times b}unu_n et vnv_n sont des entiers
  • Ceci nous permet de conclure que l’algorithme termine (bn+1=0b_{n+1} = 0 se produit en un nombre fini d’itérations), que la valeur retournée est bien de la forme u×a+v×b{u \times a + v \times b}.
    Il s’agit bien du PGCD car on a alors gcd(an+1,0)=gcd(a,b)\gcd(a_{n+1}, 0) = \gcd(a, b).

Quelques résultats d’arithmétique

Pour finir, nous allons énoncer deux résultats fondamentaux sur la structure des nombres entiers. Un lemme préalable est utile pour les démontrer.

Lemme d’Euclide

Si un nombre premier pp divise a×ba \times b, alors pp divise aa ou pp divise bb.

Ce lemme peut se prouver à l’aide de l’identité de Bézout, en supposant que pp ne divise pas aa (on montre alors qu’il divise forcément bb). Comme pp est premier, on a alors gcd(p,a)=1{gcd(p, a) = 1} et on peut construire des entiers u,vZ{u, v \isin \Z} vérifiant : u×p+v×a=1{u \times p + v \times a = 1}

On en déduit u×p×b+v×a×b=bu \times p \times b + v \times a \times b = b, et donc pp divise bb car il divise chacun des deux termes de la somme.

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

Tout nombre entier nNn \isin \N peut s’écrire de façon unique comme produit de nombres premiers.

Par exemple :

  • 10=2×510 = 2 \times 5
  • 2020=25×5×1012020 = 2^5 \times 5 \times 101
  • 289674=2×32×7×112×19289674 = 2 \times 3^2 \times 7 \times 11^2 \times 19

L’algorithme suivant permet d’obtenir cette décomposition (il est cependant assez inefficace) :

def prime_factors(n):
f = 2
while n > 1:
q, r = euclidean_division(n, f) # n = q * f + r
if r == 0:
yield f
n = q
else:
f += 1
>>> print(list(prime_factors(289674)))
[2, 3, 3, 7, 11, 11, 19]

Cet algorithme fonctionne sur le principe suivant :

  • La variable ff va tester tous les facteurs possibles à partir de 2
  • Lorsqu’un facteur ff est trouvé, on continue à décomposer le quotient qq. Le lemme d’Euclide nous autorise en effet à chercher les facteurs premiers de n=f×q{n = f \times q} parmi les facteurs de qq.
  • À chaque étape, nn n’est divisible par aucun nombre premier strictement inférieur à ff, donc en particulier pas par ff si ff n’est pas premier. Le résultat est donc le même que si ff ne prenait que des nombres premiers comme valeurs.

Question : Montrer que la décomposition obtenue est unique, c’est-à-dire que chaque nombre premier apparaît toujours le même nombre de fois dans la décomposition en produit.

Il existe une infinité de nombres premiers.

Ce résultat peut se prouver en raisonnant par l’absurde.

On suppose qu’il existe seulement un nombre fini kk de nombres premiers p1,p2,...pkp_1, p_2, ... p_k, et on note N=p1×p2×...×pk+1{N = p_1 \times p_2 \times ... \times p_k + 1}.

NN n’est divisible par aucun de ces kk nombres (le reste de la division euclidienne est toujours 11), ce qui est en contradiction avec l’existence d’une décomposition de NN en produit de nombres premiers.

💻 On pourra d’ailleurs illustrer cette démonstration en utilisant Python, la décomposition de NN avec différentes valeurs pour p1,p2,...pkp_1, p_2, ... p_k pouvant être mise en évidence :

>>> print(list(prime_factors(2*3 + 1)))
[7]
>>> print(list(prime_factors(2*5*13*19 + 1)))
[7, 353]
>>> print(list(prime_factors(3*5*13*19 + 1)))
[2, 17, 109]

Et après ?

Comme vous le savez, les nombres ne s’arrêtent pas aux entiers 😉

Je vous propose de continuer avec cet article sur la construction des nombres réels, toujours illustré avec Python.



Maths et applications, avec les mains et avec du code 💻
Suivre sur Twitter

© 2020 Lipsum.dev — Contactez-moi (questions, remarques, etc.)