Le cours en version imprimable est A2 téléchargeable ici.

Division euclidienne

Division euclidienne dans $\mathbb{N}$

Division euclidienne dans $\mathbb{N}$.

Soit $a \in \mathbb{N}$ et $b \in \mathbb{N}^*$, alors il existe un unique couple d'entiers naturels $(q;r)$ tel que $a=bq+r$ avec $0 \leq r < b$.

Vocabulaire

$a$ est le dividende, $b$ est le diviseur, $q$ est le quotient et $r$ est le reste.

$b$ divise $a$ si, et seulement si, le reste de la division euclidienne de $a$ par $b$ est nul.

Existence du couple $(q;r)$

Soit $q$ la partie entière du quotient $\dfrac{a}{b}$. L'entier $q$ est défini par l'encadrement $\ldots\ldots \leq \dfrac{a}{b}$ < $\ldots\ldots\ldots$

Puisque $b>0$, on en déduit que $\ldots\ldots\ldots \leq a $< $\ldots\ldots\ldots\ldots$*

On pose alors $r=a-bq$. Ainsi $a=\ldots\ldots\ldots\ldots$ et d'après *, $\ldots\ldots\ldots\ldots\ldots \leq a-bq$ < $\ldots\ldots\ldots\ldots\ldots\ldots$

soit $\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots$

Unicité du couple $(q;r)$

On suppose qu'il existe deux couples d'entiers naturels $(q;r)$ et $(q';r')$ vérifiant simultanément :

$a=bq+r = bq'+r'$ avec $0 \leq r<b$ et $0 \leq r' <b$.

On en déduit que $r-r' = \ldots\ldots\ldots\ldots\ldots\ldots = \ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots$ donc $r-r'$ est multiple de $\ldots\ldots$

Or, $0 \leq r < b$ et $\ldots\ldots < -r' \leq \ldots\ldots$ donc, par addition membre à membre, on obtient $\ldots\ldots < r-r'<\ldots\ldots$

Le seul multiple de $b$ dans $]-b;b~[$ est $\ldots\ldots$ donc $r-r'=\ldots\ldots$ soit $\ldots\ldots\ldots\ldots\ldots\ldots$

Comme $r-r'=b(q'-q)$ avec $b \neq 0$, alors $\ldots\ldots\ldots\ldots = 0$ soit $\ldots\ldots\ldots\ldots\ldots\ldots$, d'oùl'unicité.

Code de déblocage de la correction :

Division euclidienne dans $\mathbb{Z}$

Division euclidienne dans $\mathbb{Z}$.

Soit $a \in \mathbb{Z}$ et $b \in \mathbb{Z}^*$, alors il existe un unique couple d'entiers $(q;r)$ avec $q \in \mathbb{Z}$ et $r \in \mathbb{N}$ tel que $a=bq+r$ avec $0 \leq r < |b|$.

Vocabulaire

$a$ est le dividende, $b$ est le diviseur, $q$ est le quotient et $r$ est le reste.

Effectuer la division euclidienne de $a$ par $b$, c'est déterminer le couple d'entiers $(q;r)$ tel que $a=bq+r$ avec $0 \leq r < |b|$.

Effectuez les divisions euclidiennes de $a$ par $b$ pour chacun des cas suivants :

  1. $ a=1776$ par $b=7$.

  2. Code de déblocage de la correction :

  3. $a=1776$ par $b=-7$.

  4. Code de déblocage de la correction :

  5. $a=-1776$ par $b=7$.

  6. $a=-1776$ par $b=-7$.

Code de déblocage de la correction :

Congruence dans $\mathbb{Z}$

$a$ est congru à $b$ modulo $n$

Soit $n \in \mathbb{N}^*$, on dit que $a$ et $b$ sont congrus modulo $n$ lorsque $a$ et $b$ ont le même reste dans la division euclidienne par $n$.

Notation :

On écrit $a \equiv b~(n)$ ou $a \equiv b~[n]$ ou encore $a \equiv b \pmod n$. On lit "$a$ est congru à $b$ modulo $n$".

Pour tout entier $n \geq 2$ on a : $\quad a \equiv b~[n]$ si, et seulement si, $n$ divise $a-b$.

Démontrer le théorème précédent.

Code de déblocage de la correction :

$168-138 = 30 = 2 \times 15$ donc $168 \equiv 138~[15]$ .

$a \equiv b~[n]$ si et seulement s'il existe $k\in\mathbb{Z}$ tel que $a=b+nk$

Vrai ou Faux :

  1. $24 \equiv 1~[5]$
  2. $1 \equiv -1~[2]$
  3. $10 \equiv 0~[5]$
  4. $9 \equiv 2~[2]$
  5. Code de déblocage de la correction :

$a \equiv r~[n]$ avec $0 \leq r < n$ si, et seulement si, $a$ a pour reste $r$ dans la division euclidienne de $a$ par $n$.

Démontrer la propriété précédente.

Code de déblocage de la correction :

$b$ divise $a$ si, et seulement si, le reste de la division de $a$ par $b$ est nul c'est-à-dire que $a \equiv 0~[b]$.

Transitivité

Soit $n$ un entier naturel non nul. Pour tous entiers relatifs $a$, $b$ et $c$, si $a \equiv b~[n]$ et $b \equiv c~[n]$ alors $a \equiv c~[n]$.

Démontrer le théorème précédent.

Code de déblocage de la correction :

Congruences et opérations

Soit $n$ un entier naturel non nul et $a$, $a'$, $b$ et $b'$ des entiers relatifs.

Si $a \equiv b~[n]$ et $a' \equiv b'~[n]$ alors

Si $a \equiv b~[n]$ alors :

Démontrer que pour tout entier naturel $n$ non nul, $2^{3n}\equiv 1~[7]$.

Code de déblocage de la correction :

Soit $n$ un entier naturel et $A=n(n^2+5)$. Le but est de démontrer que $A$ est divisible par 3.

  1. Quels sont les restes possibles dans une division par 3 ?

  2. Reproduire et compléter le tableau suivant de congruence modulo 3 en précisant dans chaque cellule le reste de la division euclidienne par 3.

    Reste de la division de $n$ par 3 0 1 2
    Reste de la division de $n^2$ par 3 $\quad$ $\quad$ $\quad$
    Reste de la division de $n^2+5$ par 3 $\quad$ $\quad$ $\quad$
  3. En déduire que $A=n(n^2+5)$ est divisible par 3 quel que soit l'entier $n$.

Code de déblocage de la correction :

Déterminer l'ensemble des valeurs entières $n$ pour lesquelles $A=n^2-3n+10$ est divisible par 4.

Code de déblocage de la correction :

Exercices

Division euclidienne

Vrai ou Faux- Justifier

  1. Si le reste de la division euclidienne de $a$ par 70 est égal à 0, alors $a$ est un diviseur de 70.

  2. Tout nombre impair est premier.

  3. Tout entier relatif peut s'écrire sous la forme de $2k$ ou $2k+1$ où $k$ est un entier relatif quelconque.

  4. L'égalité $37=3\times 9 +10$ traduit la division euclidienne de 37 par 3 ou par 9.

  5. L'égalité $37=5\times7+2$ traduit la division euclidienne de 37 par 5 ou par 7.

Déterminer le quotient et le reste de la division euclidienne de $a$ par $b$.

  1. $a=351$ ; $b=12$.

  2. $a=-1001$ et $b=31$.

  3. $a=-654$ et $b=-13$.

  4. $a=-601$ et $b=12$.

On divise l'entier 256 par $b$, on trouve comme quotient 15 et comme reste $r$.

Quelles sont les valeurs possibles de $b$ et de $r$?

Quels sont les restes possibles dans la division euclidienne d'un entier naturel impair par 4?

Écrire un algorithme qui prend comme argument $a$ et $b$ entiers naturels et qui renvoie le quotient et le reste de la division euclidienne de $a$ par $b$.

Congruence

  1. Soient $a$ et $b$ deux entiers tels que $a\equiv 3[7]$ et $b\equiv 1[7]$. Démontrer que $2a+b^2$ est un multiple de $7$.

  2. Soient $a$ et $b$ deux entiers tels que $a\equiv 2[5]$ et $b\equiv 3[5]$. Déterminer le reste de la division euclidienne de $a^2+2b^2$ par 5.

Démontrer que $35^{228}+84^{501} \equiv 0[17]$

  1. Quel est le reste de la division euclidienne de $6^{943}$ par 7 ?

  2. Quel est le reste de la division euclidienne de $247^{349}$ par 7 ?

  1. Quel est le reste de la division euclidienne de $8^{2020}$ par 5 ?

  2. Code de déblocage de la correction :

    1. Soit $n\in \mathbb{N}$. On pose $a = 3^{2n+1} + 2^{n+2}$. Démontrer que $a \equiv 0 [7]$.

    2. Que peut-on en déduire en terme de divisibilité ?

  3. Code de déblocage de la correction :

$n$ désigne un entier naturel.

  1. Quels sont les restes possibles de la division euclidienne de $3^n$ par 11 ?

  2. Code de déblocage de la correction :

  3. Quels sont les restes possibles de la division euclidienne de $n$ par 5 ?

  4. Code de déblocage de la correction :

  5. En déduire que $3^n + 7 \equiv 0 [11]$ si, et seulement si, $n = 5k + 4$ avec $k\in\mathbb{N}$.

  6. Code de déblocage de la correction :

$x$ et $y$ sont deux entiers naturels tels que $x \equiv 7 [9]$ et $y\equiv 4[9]$

Déterminer les restes dans la division euclidienne par 9 de :

  1. $3x+4y$
  2. $x^2+y^2$
  3. $2x^2-5y^2$

Déterminer les valeurs de $n$ pour lesquels l'entier $6^n+4^n$ est divisible par 5.

Un rep-unit (répétition de l'unité) est un entier qui est formé uniquement de 1. Par exemple, le nombre $1111111$.

  1. Déterminer le reste de la division euclidienne de $1111111$ par 5, par 9 et par 11.

  2. Déterminer le reste de la division euclidienne de $(1111111)^8$ par 5, par 9 et par 11.

On cherche à résoudre dans $\mathbb{Z}$ l'équation: $$3x\equiv 5[7]$$

  1. Quels sont les restes possibles de la division euclidienne d'un entier $x$ par 7 ?

  2. En déduire les restes possibles de la division euclidienne de la division euclidienne de $3x$ par 7.

  3. Quel est l'ensemble solution ?

Résoudre dans $\mathbb{Z}$ l'équation suivante : $$x^2+2\equiv 0[9]$$

Résoudre dans $\mathbb{Z}$ l'équation suivante : $$x^2-x+4\equiv 0[6]$$

  1. Résoudre dans $\mathbb{N}$ l'équation suivante : $21^n-12\equiv 1[17]$.

  2. Résoudre dans $\mathbb{Z}$ l'équation suivante : $2\times n^2-n+3 \equiv 6[7]$.

  3. Résoudre dans $\mathbb{N}$ l'équation suivante : $13^n\equiv 4[15]$.

Synthèse

  1. On considère la suite géométrique $(v_n)$ de premier terme $v_0=13$ et de raison $q=5$.
    Pour tout entier naturel $n$, déterminer le reste de la division euclidienne $v_n$ par 4.

  2. On considère la suite $(u_n)$ définie par $u_0=14$ et, pour tout entier naturel $n$, $u_{n+1}=5u_n-6$.

    1. Démontrer que, pour tout entier naturel $n$ : $$u_{n+2}\equiv u_n[4]$$

    2. Démonter que, pour tout entier naturel $n$ : $$2u_n=5^{n+2}+3$$

    3. Déduire de la question précédente qu'aucun terme de cette suite n'est divisible par 3.

Critère de divisibilité par 11.

Partie A

  1. Vérifier que les nombres $34+43$, $57+75$, $93+39$ sont divisibles par 11.

  2. On suppose que l'écriture décimale d'un entier $x$ est $\overline{ab}$ avec $a\ne 0$, c'est à dire $x=10a+b$.
    On note$y$ l'entier obtenu en intervertissant les chiffres de $x$.
    Démontrer que $x+y$ est divisible par 11.

  3. Un entier $x$ comportant quatre chiffres s'écrit dans le système décimal $\overline{abcd}$ avec $a\ne 0$.
    En utilisant les congruences modulo $11$, démontrer que $x\equiv 0[11]$ si, et seulement si $-a+b-c+d\equiv 0[11]$.

  4. En déduire que les entiers de quatre chiffres dont l'écriture décimale est de la forme $\overline{abba}$ avec $a\ne0$ sont divisibles par 11.

Partie B

On considère un entier a définie par dont écriture décimale $a=\overline{a_na_{n-1}...a_0}$ avec $a_n\ne 0$: $$a=a_n\times10^n+a_{n-1}\times 10^{n-1}+...+a_1\times 10+a_0$$ On dira que le rang du chiffre $a_k$ est égal à $k$.

  1. Démontrer qu'un entier est divisible par 11 si, et seulement si, la somme de ses chiffres de rang pair diminuée par la somme de ses chiffres de rang impair est divisible par 11.

  2. L'entier $15 374 876 926 816$ est-il divisible par 11 ?

On considère les suites $(x_n)$ et $(y_n)$ définies par $x_0=1$, $y_0=8$ et pour tout entier naturel $n$ :

$$\left \{ \begin{array}{l} x_{n+1} = \frac73x_n+\frac13y_n+1 \\ y_{n+1} = \frac{20}3x_n+\frac83y_n+5 \\ \end{array} \right. $$

  1. Montrer par récurrence que, dans un repère du plan, les points de coordonnées $(x_n;y_n)$ sont sur la droite dont une équation est $5x-y+3=0$.
    En déduire que, pour tout $n\in\mathbb{N}$, $x_{n+1}=4x_n+2$.

    1. Montrer par récurrence que, pour tout $n\in\mathbb{N}$ , $x_n$ est un entier naturel.

    2. En déduire que, pour tout $n\in\mathbb{N}$, $y_n$ est un entier naturel.

    1. Montrer que $x_n$ est divisible par 3 si, et seulement si, $y_n$ est divisible par 3.

    2. Montrer que si $x_n$ et $y_n$ ne sont pas divisibles par 3 alors ils n'ont pas de facteur premier commun dans leur décomposition en produit de facteurs premiers.

    1. Montrer par récurrence que, pour tout $n\in\mathbb{N}$ : $$x_n=\frac13(4^n\times5-2).$$

    2. En déduire que, pour tout entier naturel $n$, $4^n\times 5 -2$ est un multiple de 3.

Les nombres de Mersenne.

Pour $n$ entier naturel non nul, on note $M_n$ l'entier $M_n=2^n-1$.

  1. Pour $1\leq n\leq 15$, quels sont les nombres $M_n$ premiers ?

    1. Soit $k$ un entier naturel non nul et $a$ entier quelconque. Montrer que $a-1$ divise $a^k-1$. ( utiliser un résultat sur les suites géométriques)

    2. En déduire que, si $d$ divise $n$, alors $2^d-1$ divise $M_n$.

  2. Déduire de la question 2 que, si $M_n$ est premier, alors $n$ est premier. La réciproque est-elle vraie ?

Racine carrées et irrationnels

On considère un entier $n$ qui n'est pas un carré parfait (c'est à dire qui n'est pas le carré d'un autre entier).

  1. Justifier que dans la décomposition de $n$ en produit de facteur premiers il existe un ombre premier $p$ dont l'exposant est impair.

  2. On suppose que $\sqrt{n}$ est rationnel , c'est à dire qu'il existe des entiers naturels $a$ et $b$ avec $b\ne 0$ tels que $\sqrt{n}=\frac{a}{b}$, on suppose également que cette fraction est irréductible.

    1. Quelle est la parité de l'exposant de $p$ dans la décomposition de $nb^2$

    2. Quelle est la parité de tous les exposants dans la décomposition de $a^2$ ?

    3. Que dire alors de l'égalité $\sqrt{n}=\frac{a}{b}$ ?

  3. Conclure.

Le but de l'exercice est de trouver l'ensemble des entiers naturels $n$ tels que $27^n \equiv 1 [37]$.

Partie A : conjecturer à l'aide d'un programme :

  1. Compléter la fonction ci-dessous de sorte qu'elle renvoie la liste de tous les entiers naturels $m$ inférieurs ou égaux à $n$ tels que $27^m \equiv 1 [37]$.

    def est_congru(n):
        """n est un entier naturel
        renvoie la liste de tous les entiers naturels m
        inférieurs ou égaux à $n$ tels que 27^m est congru à 1 modulo 37.$
        """
        L = []
        for .........................
            ...
            ...
        return ...
     

    En langage Python :

    • a//b renvoie le quotient de la division euclidienne de $a$ par $b$.

    • a%b renvoie le reste de la division euclidienne de $a$ par $b$.

  2. Tester la fonction est_congru.

  3. Quelle conjecture pouvez-vous émettre sur l'ensemble des entiers naturels $n$ tels que $27^n \equiv 1 [37]$.

Partie B : démontrer la conjecture

  1. En vous aidant de la fonction est_congru, proposer un programme en langage Python que affiche les restes successifs de $27^n$ par 37 lorsque $n$ varie entre 0 et 6.

  2. Compléter le tableau suivant à l'aide du programme précédent :

    Reste de la division de $n$ par 6 0 1 2 3 4 5
    Reste de la division de $27^n$ par 37 $\quad$ $\quad$ $\quad$ $\quad$ $\quad$
  3. En déduire une démonstration de la conjecture émise.

Les publications en série, comme les journaux et les périodiques, sont identifiées par un numéro ISSN (International Standard Serial Number) . Sur ces publications, quelles soient en format papier ou numérique, il est obligatoire d'apposer ce numéro ISSN.

Tout numéro ISSN est composé de deux groupes de quatre chiffres ou caractère séparés par un tiret : $abcd$-$efgh$.

Par exemple, le New York Times, version papier, a pour ISSN 0362-4331 tandis que le New York Times, version numérique, a pour ISSN 1553-8095. (Source : ISSN International Center )

Explications :

  1. Les sept premiers numéros ISSN du New York Times version papier sont 0362-433.

    Calculer la clé de contrôle en détaillant les différentes étapes.

  2. Vous lisez le journal Le monde en version papier. Cependant un des caractères ISSN est illisible ; On note $n$ ce caractère. Vous pouvez ainsi lire $03n5$-$2037$.

    1. Déterminer $S$ en fonction de $n$.

    2. En déduire que $6n \equiv 10 [11]$.

    3. En déduire la valeur de $n$.

  3. Vous avez en main une revue. Vous n'arrivez à lire que les sept derniers chiffres du numéro ISSN : $362$-$4337$. Quel est le premier chiffre de ce numéro ?

    Une fois que vous avez trouvé le numéro ISSN complet, vous pouvez trouver des informations sur cette revue à cette adresse.

  4. Dans les exmples précédents, vous avez pu retrouver par calcul un chiffre manquant. Est-il possible de corriger l'impossibilité de lire deux chiffres du numéro ISSN ? Justifier.

  5. On suppose que les sept premiers chiffres d'un numéro ISSN sont écrits dans une liste liste_ISSN7.

    Par exemple, pour l'édition papier du New York Times de numéro ISSN 0362-4331, on aurait : liste_ISSN7 = [0,3,6,2,4,3,3]

    Porposer une fonction nommée get_cle écrite en langage Python qui :

    • prend en paramètre la liste liste_ISSN7,

    • renvoie la clé de contrôle associée à cette liste_ISSN7. (Attention à ne bien traiter le cas où la clé est le caractère X.

    Par exemple, get_cle([0,3,6,2,4,3,3]) doit renvoyer 1 puisque le numéro ISSN du New York Times est 0362-4331.

Code de déblocage de la correction :

Chaque citoyen.ne français.e est identifié par un numéro INSEE composé de 13 chiffres suivis de deux chiffres servant de clé de contrôle.

Voici un exemple de numéro INSEE : $203095145467833$.

Par exemple, le numéro INSEE de $203095145467833$ correspond à :

Partie A : définition de la clé de contrôle

Notons $N$ le nombre formé par les treize premiers chiffres du numéro INSEE.
Notons $r$ le reste de la division euclidienne de $N$ par $97$. La clé de contrôle du numéro INSEE est K-r$.

  1. Justifier que la clé de contrôle de associée à $2030951454678$ est $33$.

  2. Prouver que la clé de contrôle associée à n'importe quel nombre $N$ est un nombre entier non nul s'écrivant avec au plus deux chiffres.

  3. Proposer une fonction cle_controle qui prend en paramètre un nombre entier naturel $n$ à $13$ chiffres et qui renvoie la clé de contrôle associée à ce nombre.

Partie B : utilisation de la clé de contôle

  1. Déterminer le reste de la division euclidienne de $100$ par $97$.

  2. Soit $A$ un nombre à treize chiffres dont la clé de contrôle est $K$.
    Ce nombre peut être décomposé sous la forme $A=G\times 10^{10}+F\times 10^8+E\times 10^6+D\times 10^4+C\times 10^2+B$ avec $B$, $C$, $D$, $E$, $F$ des nombres entiers naturels compris entre $0$ et $99$ et $G$ un nombre entier naturel tels que $G\lt 10^3$.
    Démontrer que $G\times 49+F\times 81+E\times 27+D\times 9+C\times 3+B \equiv 97-K [97]$.

  3. Déterminer à la main la clé de contrôle associée au numéro $2450319387091$.

  4. Dans cette question, on considère un numéro INSEE dans lequel un chiffre est illisible.
    Ce numéro INSEE est $15312673a026911$.

    1. Justifier que $a$ est solution de l'équation $50+9a\equiv 86 [97]$.

    2. Déterminer à l'aide d\'un tableau l'ensemble des solutions comprises entre 0 et 9 de l'équation $50+9a\equiv 86 [97]$.

    3. En déduire la valeur du chiffre $a$.

Partie C : création d'un script Python

    On considère le numéro INSEE $2108a39b45678$ dans lequel deux chiffres sont illisibles et remplacés actuellement par les lettres $a$ et $b$.

  1. Compléter le script suivant afin que la liste L contienne à la fin le ou les couples de chiffres $(a,b)$ tel(s) que le numéro $2108a39b456$ ait bien pour clé $78$.

    L=[]
    for a in range(10):
        ...
        ...
        ...
        ...
    print(L)
     
  2. En déduire le numréo INSEE cherché.

Code de déblocage de la correction :

Vous êtes allés à quatre à un casino.
Après avoir perdu de l'argent aux jeux de hasard, un de vos amis décide d'aller à un jeu ne dépendant pas du hasard.
À ce jeu, il y a 60 boutons colorés. Chaque bouton peut prendre trois couleurs : rouge, vert et bleu.
Pour gagner à ce jeu, il faut que les 60 boutons aient la même couleur.
À chaque coup, le joueur doit appuyer sur deux boutons.

Pour jouer un coup le joueur doit payer 1€.
En cas de victoire, le joueur remporte la somme de tous les euros dépensés par chacun des joueurs.

Lorsque vous arrivez devant les 60 boutons, il y a 20 boutons rouges, 18 bleus et 22 verts.

Votre ami demande votre avis en tant que quatrième membre du groupe : doit-il joueur ou non à ce jeu ? Si non pourquoi et si oui quelle combinaison de coup doit-il suivre ?
Détailler rigoureusement votre avis pour le convaincre.

Code de déblocage de la correction :

Demander le programme !

Licence Creative Commons
Les différents auteurs mettent l'ensemble du site à disposition selon les termes de la licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International