[ Page principale - Bibliographie - Annales - Liens ]
[ Olympiades : française - internationales - académiques ]
[ Clubs : Thèmes - Universités d'été - Coordonnées ]

Petit cours d'arithmétique

(Rédigé par André Deledicq.)

Division euclidienne

Dans $\N$, soient a et b deux entiers. Il existe un entier unique q (le quotient) et un entier unique r (le reste de la division de a par b) tels que $a=bq+r$ avec $0\leq r \leq b-1$.

On note : $a \equiv r [b]$ et on lit : « a est congru à r modulo b ».

Compatibilité avec l'addition et la multiplication :

\begin{eqnarray*} \left\{\begin{array}{l}a \equiv a' \\ b\equiv b'\end{array}\right. & \Rightarrow & \left\{\begin{array}{l}a+b \equiv a'+b' \\ ab\equiv a'b'\end{array}\right. \end{eqnarray*}

En particulier :

  • le reste de la division d'une somme par un nombre ne change pas quand on remplace chaque terme de la somme par le reste de sa division par le nombre ;
  • le reste de la division d'un produit de facteurs par un nombre ne change pas quand on remplace un facteur quelconque par le reste de sa division par ce nombre.

Divisibilité

a divise b $\Leftrightarrow a \equiv 0 [b] \Leftrightarrow \exists c, ac=b \Leftrightarrow$ b est multiple de a.

Un nombre qui divise plusieurs autres nombres divise aussi la somme de ces nombres.

Périodicité des restes de puissances. Quand on divise les puissances successives d'un nombre par un même nombre, les restes obtenus se reproduisent périodiquement.

Exemples :

  • Modulo 10, les puissances successives de $2$ sont $2, 4, 8, 6, 2 \ldots$ et les puissances successives de $3$ sont $3, 9, 7, 1, 3 \ldots$
  • Modulo 10, on a $a^5 \equiv a$.

Premiers. On appelle entier premier, tout entier ayant exactement deux diviseurs dans $\N$ : lui-même et $1$.

Décomposition

Tout naturel, autre que $0$ ou $1$, s'écrit de manière unique comme produit de nombres premiers :

\[ n=p_1^{\alpha_1} p_2^{\alpha_2} p_3^{\alpha_3} \ldots p_k^{\alpha_k} = \prod_{j=1}^k p_j^{\alpha_j} \]

Exemples :

  • $5040 = 7! = 2^4 \times 3^2 \times 5 \times 7$
  • $1001 = 7 \times 11 \times 13$
  • $10101 = 3 \times 7 \times 13 \times 37$
  • $111= 3 \times 37$
  • $1024= 2^{10}$
  • $51=17 \times 3$

Tout naturel n, non premier, admet au moins un diviseur premier p tel que $p^2 \leq n$.

Le nombre de diviseurs de n est $\displaystyle \prod_{j=1}^k (1+\alpha_j)$.

La somme des diviseurs de n est $\displaystyle \prod_{j=1}^k \frac{p_j^{\alpha+1}-1}{p_j-1}$.

Si les N premiers nombres premiers sont $\pi_1, \pi_2, \ldots \pi_N$, alors le nombre $(\pi_1 \times \pi_2 \times \ldots \times \pi_N)+1$ a un diviseur premier supérieur à $\pi_N$. Cela entraîne que l'ensemble des nombres premiers est infini. (Mais attention, le nombre $(\pi_1 \times \pi_2 \times \ldots \times \pi_N)+1$ peut ne pas être premier, par exemple $(2\times 3 \times 5 \times 7 \times 11 \times 13)+1 = 30031=59\times 509$.)

Théorème de Dirichlet
   Pour a et b naturels premiers entre eux, il y a une infinité de nombres premiers de la forme $ak+b$.

Théorème de Wilson
   n ($\geq 2$) est premier $\Leftrightarrow$ n divise $1+ (n-1)!$

Indicateur d'Euler. On note $\Phi(n)$ le nombre d'entiers, inférieurs à n, premiers avec n.
$\Phi(1)=1$, $\Phi(6)=2$.
Si p est premier, alors pour tout k positif : $\Phi(p^k)=p^{k-1}(p-1)$.
Si m et n sont premiers entre eux, on a $\Phi(mn)=\Phi(m)\Phi(n)$.
Avec les mêmes notations que ci-dessus, on a $\Phi(n)=\displaystyle n \prod_{j=1}^k (1-\frac{1}{p_j})$ et $\displaystyle \sum_{d\, \mathrm{ divise }\, n} \Phi(d) = n$.

Diviseurs communs

Diviseurs. Notation : l'ensemble des diviseurs de a est noté $D_a$.
Si a est un diviseur de b, alors $D_a \subset D_b$.

Le plus grand élément de $D_a \cap D_b$ est noté $\pgcd(a,b)$.

On dit que a et b sont premiers entre eux si $\pgcd(a,b)=1$.

L'ensemble des diviseurs communs à a et à b est l'ensemble des diviseurs de leur pgcd.

Le pgcd s'obtient par l'« algorithme d'Euclide » grâce au théorème : si r est le reste de la division euclidienne de a par b, alors $\pgcd(a,b)=\pgcd(b,r)$.

Multiples. Si c est multiple de a, alors l'ensemble des multiples de c est inclus dans l'ensemble des mutliples de a : $c\Z \subset a\Z$.
Tout multiple d'un multiple de a est un pultiple de a. Autrement dit, si $z \in a\Z$ alors $\lambda z \in a\Z$ pour tout $\lambda \in \Z$. On traduit cette propriété en disant que $a\Z$ est un idéal pour l'anneau $\Z$.
Le plus petit élément de $a\Z \cap b\Z$ est noté $\ppcm(a,b)$. L'ensemble des multiples communs à a et b est l'ensemble des multiples de leur ppcm.

$\pgcd(a,b)\times \ppcm(a,b)=a\times b$.

Premiers. Si a et b sont premiers entre eux, il en est de même de leur somme et de leur produit.
Les nombres $a/\pgcd(a,b)$ et $b/\pgcd(a,b)$ sont premiers entre eux.

Théorème de Gauss
   Si a divise le produit bc et si a est premier avec b, alors a divise c.

(Petit) Théorème de Fermat
   Si p est premier, alors $a^p \equiv a [p]$.
Par conséquent, si a est premier avec p, alors p divise $a^{p-1}-1$. Par ailleurs p divise $\mathrm{C}_p^k$ ($1 \leq k \leq p-1)$, ainsi que $(1-a)^p-1-a^p$, et $a^p-a$.

Théorème de Bézout
   a et b sont premiers entre eux $\Leftrightarrow$ il existe deux entiers $x, y$ tels que $ax+by=1$.
Ou encore : les nombres $a\Z+b\Z$ sont exactement les multiples de $\pgcd(a,b)$.
Si a et b sont premiers entre eux, les solutions entières de $ax+by=1$ sont de la forme $(x_0+\lambda b, y_0 - \lambda a)$.

D'où les solutions de $ax+by=c$, en fonction de $\pgcd(a,b)$.

Théorème chinois
   Si $n_1, n_2, \ldots, n_k$ sont premiers entre eux deux à deux, alors les équations simultanées $x\equiv c_j [n_j]$ ($1\leq j \leq k$) ont une unique solution modulo $\prod n_j$.
Les astronomes chinois s'intéressaient aux conjonctions de planètes de périodicités différentes tournant sur leurs orbites.
Exemple. Si u et b sont premiers entre eux, le système $\{x \equiv a [u] , y \equiv b [v]\}$ a une et une seule solution, donnée par $x = \alpha ub+\beta va [uv]$, où $\alpha$ et $\beta$ sont des entiers tels que $\alpha u + \beta v=1$.

Triplets de Pythagore

Les solutions entières de l'équation $a^2+b^2=c^2$ sont les multiples des triplets $(a,b,c)$ donnés par : $a=2mn, b=m^2-n^2, c=m^2+n^2$ ($m>n$), où les entiers m et n sont premiers entre eux.

Numération

Le naturel a étant la « base de numération » ($a>1$), tout naturel n s'écrit de manière unique sous forme polynomiale : $n= \alpha_n a^n + \alpha_{n-1} a^{n-1} + \ldots +\alpha_2 a^2 + \alpha_1 a + \alpha_0$ avec $0 \leq \alpha_j \leq a-1$.

Développement décimal illimité

Le développement décimal illimité d'un rationnel s'obtient en pratique par la « technique de division ». Les valeurs des restes partiels obtenus dans cette technique, étant plus petits que le diviseur, ne peuvent être plus nombreux que lui ; les valeurs de ces restes se répètent donc obligatoirement et les chiffres du développement décimal illimité, obtenu au quotient, aussi. D'où le résultat : les chiffres du développement décimal illimité d'un rationnel $a/b$ se répètent périodiquement et la longueur de la période est inférieure à b.

Le rationnel dont le développement décimal illimité est $0,\alpha_1\alpha_2\ldots\alpha_n$, où les chiffres $\alpha_1\alpha_2\ldots\alpha_n$ se répètent indéfiniment, est égal au quotient s'écrivant $\displaystyle \frac{\alpha_1\alpha_2\ldots\alpha_n}{10^n-1}$.

Exemples :

  • $\displaystyle \frac{1}{7}= 0,142857\underline{142857}=\frac{142857}{999999}$
  • $\displaystyle \frac{1}{27}= 0,\underline{037}=\frac{037}{999}$
  • $\displaystyle \frac{1}{37}= 0,\underline{027}=\frac{027}{999}$

Résidus quadratiques

La table suivante donne quelques valeurs de $n^2 [m]$.

On voit dans les colonnes 3, 4, 5 et 8 que :

  • l'équation $x^2\equiv 2 [3]$ n'a pas de solution. Donc aucun carré n'est de la forme $3k+2$ ;
  • l'équation $x^2\equiv 3 [4]$ n'a pas de solution. Donc aucun carré n'est de la forme $4k+3$ ;
  • modulo $5$, les carrés ne peuvent valoir que $0$, $1$ ou $-1$ ;
  • modulo $8$, les carrés d'impairs valent $1$.

Critères de divisibilité

Les seuls entiers divisibles par 2 se terminent par 0, 2, 4, 6 et 8. Les seuls entiers divisibles par 5 se terminent par 0 ou 5. (Résultats analogues, dans la base a, pour tous les diviseurs de a.) Les seuls entiers écrits en base dix, divisibles par 4, se terminent par 00, 04, 08, 12, ..., 96. Les seuls entiers écrits en base dix, divisibles par 25 se terminent par 00, 25, 50, 75.

Un entier naturel, écrit en base 10, est divisible par 3 (ou par 9) si et seulement si la somme de ses chiffres est divisible par 3 (ou par 9). (Résultat analogue en base a pour $a-1$.)

Un critère de divisibilité par 7. On a successivement :

\begin{eqnarray*} 10d+u \equiv 0\, [7] & \Leftrightarrow & 20d+2u \equiv 0\, [7] \\ & \Leftrightarrow & 20d+2u-21d \equiv 0\, [7] \\ & \Leftrightarrow & 2u-d \equiv 0\, [7] \end{eqnarray*}


Donc $10d+u$ est divisible par 7 si et seulement si $d-2u$ est divisible par 7 : un nombre est divisible par 7 si et seulement si en retirant le chiffres des unités et en l'enlevant deux fois au nombre alors écrit, le résultat est aussi divisible par 7. Exemple. 1001 est divisible par 7 : en retirant le dernier chiffre, on obtient 100, en soustrayant deux fois 1 on obtient 98 ; à partir de 98, en retirant le 8 on obtient 9, en soustrayant deux fois 8 on obtient 9-16=-7 qui est divisible par 7.

Une application du système binaire : jeu de Nim. Le jeu de Nim est un jeu dans lequel on dispose de n tas de $x_i$ objets $x_1, x_2,\ldots x_n$ et qui se joue à deux joueurs. Chacun son tour enlève les objets qu'il veut dans un seul des tas. Celui qui prend le dernier objet a gagné.
Dans un tel jeu la stratégie gagnante consiste à laisser à l'autre joueur l'un des états d'un ensemble N tel que les règles du jeu imposent, à celui qui joue, de sortir de N alors que, de tout état hors de N, on peut jouer pour rentrer dans N.
La stratégie dans le jeu de Nim est alors évidente. Écrire les $x_i$ en base 2. L'ensemble N est constitué des états du jeu tels que toutes les sommes des chiffres de même rang des $x_i$ soient paires.

Une application du système ternaire : balance à plateaux. Dans l'écriture en base 3 d'un nombre, on remplace le chiffre 2 par -1. En partant d'un nombre de k chiffres (compris entre $3^{k-1}$ et $3^k-1$), on obtient alors pour résultat un nombre compris entre $-\frac{3^k-1}{2}$ et $\frac{3^k-1}{2}$. L'écriture de ce nombre peut s'interpréter comme le dépôt ou non (0) sur une balance, des « poids de base » ($1, 3, 9 \ldots 3^k$), chacun pouvant être déposé sur le même plateau (-1) que l'objet à peser, ou sur le plateau opposé (1).
Pour $k=4$, par exemple, on voit comment on peut peser tous les objets de 1 à 40 grammes, avec quatre poids de 1, 3, 9 et 27 grammes.

[ Page principale - Bibliographie - Annales - Liens ]
[ Olympiades : française - internationales - académiques ]
[ Clubs : Thèmes - Universités d'été - Coordonnées ]

Association Animath
Institut Henri Poincaré
11 rue Pierre et Marie Curie
75231 Paris cedex 05
animath (at) animath.fr

Pour toute question concernant Animath : animath (at) animath.fr
Pour toute remarque concernant ce site : webmaster (at) animath.fr
Dernière modification : 10 juillet 2004.
Page maintenue par Yann Ollivier.

Copyright
Tous les textes et le matériel figurant sur ces pages sont la propriété de leurs auteurs.
Toute utilisation non commerciale est autorisée, avec mention de la source.
Toute utilisation commerciale est interdite.