Chapitre 3 — Arithmétique

\(\mathcal{D}(123)\) — l'ensemble des diviseurs de 123 :

On cherche tous les entiers qui divisent 123. On décompose : \(123 = 3 \times 41\). Donc :

Vérification : \(123 = 1 \times 123 = 3 \times 41\). Ce sont bien les seuls diviseurs.

\(21\mathbb{Z}\) — l'ensemble des multiples de 21 :

On prend tous les entiers relatifs \(k\) et on calcule \(21k\) :

Ce sont tous les entiers de la forme \(21k\) avec \(k \in \mathbb{Z}\).

• \(3 \mid 12\) et \(5 \nmid 12\).
• \(\mathcal{D}(12) = \{1, 2, 3, 4, 6, 12\}\).
• Tous les entiers divisent \(0\) : \(\mathcal{D}(0) = \mathbb{N}\).
• \(0\) n'est diviseur d'aucun entier non nul : \(0\mathbb{Z} = \{0\}\).
• \(a \mid b \Longleftrightarrow b\mathbb{Z} \subset a\mathbb{Z}\).
• Un multiple de \(2\) est un nombre pair ; les autres sont les impairs, de la forme \(2k+1\), \(k \in \mathbb{N}\).

Si \(a \in \mathbb{Z}\) divise \(3n + 2\) et \(n - 3\), alors \(a \mid 11\).

En effet, \(a\) divise alors \((3n+2) - 3(n-3) = 11\).

La division euclidienne d'un entier naturel \(n\) par \(2\) donne \(0\) ou \(1\) pour reste, ce qui permet d'obtenir par disjonction :

• un entier naturel \(n\) pair de la forme \(n = 2k\), avec \(k \in \mathbb{N}\),
• ou un entier naturel \(n\) impair de la forme \(n = 2k+1\), avec \(k \in \mathbb{N}\).

• \(0 \notin \mathbb{P}\) : il admet une infinité de diviseurs.
• \(1 \notin \mathbb{P}\) : il n'admet qu'un seul diviseur.
• \(2 \in \mathbb{P}\) : seul nombre premier pair.
• \(2^{136\,279\,841} - 1\) (plus de 41 millions de chiffres) est le plus grand nombre premier connu, découvert le 11 octobre 2024 par le GIMPS.
• Le polynôme \(P(n) = n^2 - n + 41\) donne des premiers pour \(n = 0\) à \(39\) mais \(P(40) = 41^2\).

from math import *
n = int(input("n="))
d = 3
while d**2 <= n and n%d != 0:
    d = d + 2
if d*d > n and n > 1:
    print("n=", n, "est premier")
else:
    print("n=", n, "non premier")
    print("d=", d, "est le plus petit diviseur")

Exemples numériques :

• \(n = 853661\) → non premier, \(d = 41\) est le plus petit diviseur
• \(n = 131071\) → premier

Soient \(a = 4116\) et \(b = 5632\). On a :

Simplification de \(\sqrt{a}\) et \(\sqrt{b}\) :

Calcul du pgcd : on prend les facteurs communs avec le plus petit exposant :

Fraction irréductible :

\(a\) est-il un carré parfait ? Non, car dans la décomposition de \(a = 2^2 \times 3^1 \times 7^3\), les exposants de \(3\) et \(7\) sont impairs.

Plus petit carré multiple de \(b\) : il faut rendre tous les exposants pairs dans \(b = 2^9 \times 11\). On multiplie par \(2 \times 11\) :

Pour tout entier naturel \(n\), considérons la fraction \(\dfrac{2n+3}{2n+1}\).

Le programme Python suivant calcule \(\text{pgcd}(2n+3, 2n+1)\) pour les \(N+1\) premières valeurs de \(n\) :

from math import *

def pgcd(a, b):
    while b != 0:
        r = a % b
        a = b
        b = r
    return a

def fracirrec(n):
    L = []
    for k in range(0, n):
        d = pgcd(2*k+3, 2*k+1)
        L.append(d)
    return L

En l'exécutant pour \(N = 20\) :

fracirrec(20)
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

Ce résultat nous autorise à conjecturer que cette fraction est irréductible quel que soit \(n\). La preuve sera donnée en exercice corrigé.

On a \(10 < \sqrt{109} < 11\). On teste les premiers \(< 11\) : \(2, 3, 5, 7\).

• Règles de divisibilité : \(109\) n'est divisible ni par \(2\), ni par \(3\), ni par \(5\).
• Division euclidienne : \(109 = 7 \times 15 + 4\), donc \(7 \nmid 109\).

Conclusion : \(109\) est premier.

Pour dresser la liste des premiers entre \(2\) et \(100\) : écrire tous les entiers, puis éliminer successivement les multiples de \(2\), de \(3\), etc.

def eratosthene(n):
    L = [i for i in range(2, n+1)]
    P = []
    while len(L) != 0:
        P.append(L[0])
        i = L[0]
        for k in L:
            if k % i == 0:
                del(L[L.index(k)])
    return P

On obtient : \(16758 = 2 \times 3^2 \times 7^2 \times 19\).

• \(\text{pgcd}(24;18) = 6\)
• \(\text{pgcd}(27;140) = 1\)
• \(\text{pgcd}(60;84) = 12\)
• \(\text{pgcd}(150;240) = 30\)

Le principe est basé sur le Théorème 5 : \(\text{pgcd}(a,b) = \text{pgcd}(b,r)\). On itère jusqu'à ce que le reste soit nul.

from math import *
a = int(input("a="))
b = int(input("b="))
while b != 0:
    r = a % b
    a = b
    b = r
print("pgcd(a,b)=", a)

Exemples numériques :

• \(a = 4116\) et \(b = 720\) → \(\text{pgcd}(4116, 720) = 12\)
• \(a = 22231\) et \(b = 574\) → \(\text{pgcd}(22231, 574) = 1\) : ces entiers sont premiers entre eux

Version synthétique — fonction Python (Jean Wacksmann) :

from math import *
def pgcd(a, b):
    while b != 0:
        r = a % b
        a = b
        b = r
    return a

Exemple : pgcd(15330, 350) → 70.

Conclusion : \(\text{pgcd}(4539 ; 1958) = 89\).

• \(510510 \wedge 80000 = (2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17) \wedge (2^7 \times 5^4) = 2 \times 5 = 10\)
• \(9100 \wedge 1848 = (2^2 \times 5^2 \times 7 \times 13) \wedge (2^3 \times 3 \times 7 \times 11) = 2^2 \times 7 = 28\)

• \(\text{ppcm}(18;12) = 36\)
• \(\text{ppcm}(11;17) = 187\)
• \(\text{ppcm}(24;40) = 120\)

\(\text{pgcd}(42;60) = 6\). Si \(m = \text{ppcm}(42;60)\), alors \(6m = 42 \times 60\), donc \(m = 420\).