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

É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$.

$n$ désigne un entier naturel.

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

Code de déblocage de la correction :

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

Code de déblocage de la correction :

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

Code de déblocage de la correction :

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 $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]$.

Code de déblocage de la correction :

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

Code de déblocage de la correction :

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

Code de déblocage de la correction :

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 de $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$.

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.

3. 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.

4. 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 ?

2. 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$.

3. 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

4. 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.

5. 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$

6. 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 :

• les sept premiers chiffres composant l'ISSN sont des chiffres caractérisant la publication : chaque publication a une série de sept chiffres différente des autres publications existantes dans le Monde.

• le dernier caractère, situé à la huitième position, est la clé de contrôle. Cette clé de contrôle, déterminée à partir de sept premiers chiffres, permet de vérifier qu'il n'y a probablement pas d'erreur dans le numéro de série apparaisssant sur la publication.

• La clé de contrôle est prise dans la liste des 11 caractères suivants : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 et X (X représente en fait le nombre 10 : pensez à l'écriture des chiffres romains)

  Pour déterminer cette clé de contrôle :

  1. on calcule le nombre $S=8a+7b+6c+5d+4e+3f+2g$,

  2. on détermine ensuite le reste de la division euclidienne de $-S$ par 11 : ce reste constitue la clé de contrôle.

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.

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$.

• Le premier chiffre informe du genre de la personne : $1$ signifie que c'est un homme, $2$ que c'est une femme.

• Les deux suivants informent de l'année de naissance.

• Les quatrième et cinquième chiffres informent du mois de naissance.

• Les sixième et septième chiffres informent du numéro de département.

• Les huitième, neuvième et dizième chiffres informent du numéro INSEE de la commune de naissance.

• Les onzième, douzième et treizième chiffres permettent de différencier tous les individus nés la même année, le même mois, dans la même commune : le nombre formé correspond à l'ordre d'enregistrement de la personne dans l'État Civil.

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

• une femme

• née en $2003$

• en septembre

• dans la Marne

• à Reims (ville de numéro INSEE $454$)

• positionnée comme $678^{ème}$ dans l'État Civil

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

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

5. 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]$.

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

7. 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$.

8. 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)
    

9. En déduire le numréo INSEE cherché.