Source Latex
du cours de mathématiques
\documentclass[12pt,onecolumn,a4paper]{article}
\usepackage[french]{babel}
%%\selectlanguage{francais}
\usepackage[utf8]{inputenc}
\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsmath}
\usepackage{enumerate}
\usepackage{array}
\usepackage{calc}
\usepackage{pst-all}
\usepackage{hyperref}
\makeatletter
\renewcommand*\l@section{\vspace*{.2em}\@dottedtocline{1}{.5em}{3em}}
\renewcommand*\l@subsection{\@dottedtocline{2}{1.5em}{1.3em}}
\makeatother
\hypersetup{
pdfauthor={Yoann Morel},
pdfsubject={Cours d'arithmétique},
pdftitle={Arithmétique: division euclidienne et congruences},
pdfkeywords={Mathématiques, maths expertes, terminale générale,
arithmétique, division euclidienne, congruence}
}
\hypersetup{
colorlinks = true,
linkcolor = blue,
anchorcolor = red,
citecolor = blue,
filecolor = red,
urlcolor = red
}
\voffset=-.5cm
% Raccourcis diverses:
\newcommand{\nwc}{\newcommand}
\nwc{\dsp}{\displaystyle}
\nwc{\ct}{\centerline}
\nwc{\bge}{\begin{equation}}\nwc{\ene}{\end{equation}}
\nwc{\bgar}{\begin{array}}\nwc{\enar}{\end{array}}
\nwc{\bgit}{\begin{itemize}}\nwc{\enit}{\end{itemize}}
\nwc{\bgen}{\begin{enumerate}}\nwc{\enen}{\end{enumerate}}
\nwc{\la}{\left\{}\nwc{\ra}{\right\}}
\nwc{\lp}{\left(}\nwc{\rp}{\right)}
\nwc{\lb}{\left[}\nwc{\rb}{\right]}
\nwc{\bgsk}{\bigskip}
\nwc{\vsp}{\vspace{0.1cm}}
\nwc{\vspd}{\vspace{0.2cm}}
\nwc{\vspt}{\vspace{0.3cm}}
\nwc{\vspq}{\vspace{0.4cm}}
\def\N{{\rm I\kern-.1567em N}}
\def\D{{\rm I\kern-.1567em D}}
\def\No{\N_0}
\def\R{{\rm I\kern-.1567em R}}
\def\C{{\rm C\kern-4.7pt
\vrule height 7.7pt width 0.4pt depth -0.5pt \phantom {.}}}
\def\Q{\mathbb{Q}}
\def\Z{{\sf Z\kern-4.5pt Z}}
\renewcommand{\Re}{\mathcal{R}e}
\renewcommand{\Im}{\mathcal{I}\!m}
\def\epsi{\varepsilon}
\def\lbd{\lambda}
\def\tht{\theta}
\def\Cf{\mathcal{C}_f}
\nwc{\tm}{\times}
\nwc{\V}[1]{\overrightarrow{#1}}
\nwc{\zb}{\mbox{$0\hspace{-0.67em}\mid$}}
\nwc{\db}{\mbox{$\hspace{0.1em}|\hspace{-0.67em}\mid$}}
\nwc{\ul}[1]{\underline{#1}}
\newcounter{nex}%[section]
\setcounter{nex}{0}
\newenvironment{EX}{%
\stepcounter{nex}
\bgsk{\noindent\large {\bf Exercice }\arabic{nex}}\hspace{0.2cm}
}{}
\nwc{\bgex}{\begin{EX}}\nwc{\enex}{\end{EX}}
\nwc{\bgfg}{\begin{figure}}\nwc{\enfg}{\end{figure}}
\nwc{\epsx}{\epsfxsize}\nwc{\epsy}{\epsfysize}
\nwc{\bgmp}{\begin{minipage}}\nwc{\enmp}{\end{minipage}}
\headheight=0cm
\textheight=27.4cm
\topmargin=-1.8cm
\footskip=.8cm
\textwidth=18.8cm
\oddsidemargin=-1.5cm
\newcounter{ntheo}
\setcounter{ntheo}{1}
\newlength{\ltheo}
\nwc{\bgth}[1]{
\settowidth{\ltheo}{Théorème }%\arabic{ntheo}}
\noindent
\paragraph{Théorème}% \arabic{ntheo}}
\hspace{-0.5em}%\hspace{-0.4cm}
\bgmp[t]{\textwidth-\ltheo-0.5em}{\it #1}\enmp\bigskip
\stepcounter{ntheo}
}
\newcounter{nprop}
\setcounter{nprop}{1}
\newlength{\lprop}
\nwc{\bgprop}[1]{
\settowidth{\lprop}{Propriété \arabic{nprop}}
\noindent
\paragraph{Propriété}% \arabic{ntheo}}
\hspace{-0.5em}%\hspace{-0.4cm}
\bgmp[t]{\textwidth-\lprop-0.5em}{\it #1}\enmp\bigskip
\stepcounter{nprop}
}
\nwc{\bgcorol}[1]{
\settowidth{\ltheo}{Corollaire \arabic{ntheo}}
\noindent
\paragraph{Corollaire}% \arabic{ntheo}}
\hspace{-0.5em}%\hspace{-0.4cm}
\bgmp[t]{\textwidth-\ltheo-0.5em}{\it #1}\enmp\bigskip
}
\newcounter{ndef}
\setcounter{ndef}{1}
\newlength{\ldef}
\nwc{\bgdef}[1]{
\settowidth{\ldef}{Définition \arabic{ndef}}
\noindent
\paragraph{Définition}% \arabic{ndef}}
\hspace{-0.5em}%\hspace{-0.4cm}
\bgmp[t]{\textwidth-\ldef-0.5em}{\it #1}\enmp
\stepcounter{ntheo}
}
%\newenvironment{proof}{
% \noindent\textsc{Preuve.~}}{\hfill$\square$\bigbreak}
\nwc{\bgproof}[1]{
\vspd\noindent
\ul{Démonstration:} #1
\hfill$\square$
}
\renewcommand\thesection{\Roman{section}\ \ -}
\renewcommand\thesubsection{\arabic{subsection})}
% Bandeau en bas de page
\newcommand{\TITLE}{Arithmétique}
\author{Y. Morel}
\date{}
\usepackage{fancyhdr}
\pagestyle{fancyplain}
\setlength{\headheight}{0cm}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0.1pt}
\lhead{}\chead{}\rhead{}
\lfoot{Y. Morel - \href{https://xymaths.fr/Lycee/Terminale-maths-expertes/}{ xymaths - Maths expertes}}
\rfoot{\TITLE\ - Maths expertes - \thepage/\pageref{LastPage}}
\cfoot{}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
%\thispagestyle{empty}
\vspace*{2cm}
\hfill{\LARGE \bf \TITLE}
\hfill\bgmp{5cm} Mathématiques expertes\\Terminale générale\enmp
\bigskip
\ct{\Large\bf Divisiblité, division euclidienne et congruences}
\vspace*{2cm}
\hspace*{5cm}\bgmp{10cm}\og La mathématique est la reine des sciences\\
et l'arithmétique est la reine des mathématiques\fg,\enmp\\
\hfill\textit{Carl Friedrich Gauss (1777 - 1855)}
\renewcommand{\baselinestretch}{1.8}\normalsize
\tableofcontents
\renewcommand{\baselinestretch}{1.0}\normalsize
\clearpage
\section{\'Echauffements}
\vspace{-1em}
\bgex \textbf{Divisiblité par 3 et par 9}\\
Les nombres suivants sont-ils divisibles par 3 ? par 9 ? par 6 ? par 18 ?
27
\quad-\quad
129
\quad-\quad
567
\quad-\quad
837
\quad-\quad
22134
\quad-\quad
1556
\quad-\quad
50166
\enex
\bgex\textbf{Sur la parité}
\bgen[a)]
\item Quelle est la parité du carré d'un nombre pair ? du carré d'un nombre impair ?
\item Quelle est la parité du produit de deux nombres pairs ? de deux nombres impairs ?
\item Quelle est la parité de la somme de deux nombres pairs ? de deux nombres impairs ?
\item \'Enoncer une règle sur la parité du produit de deux entiers et une règle sur la parité de la somme de deux entiers.
\enen
\enex
\bgex\textbf{Sur les puissances}\\
\'Ecrire sous la forme de produits et puissances, plus simples:
$\lp5^2\rp^6$ \ - \ $\lp2\tm3^2\rp^3$ \ - \ $\lp2^{2n+1}\rp^3$
\ - \ $\lp\dfrac{5^2}{3}\rp^4$\\
Factoriser: $2^{n+3}-2^n$ \ - \ $3^{2n+1}-3^{n+1}$ \ - \ $4^{n+1}-2^{n+2}$
\enex
\section{Introduction - A propos de $\N$}
L'arithmétique est la branche des mathématiques qui s'intéresse aux nombres entiers (naturels et relatifs), à leurs relations et propriétés en lien avec les opérations élémentaires: addition, soustraction, multiplication et division.
\\
Tous les problèmes concernent donc ici l'ensemble des entiers naturels $\N$ ou celui des entiers relatif~$\Z$.
\bgprop{\textbf{Axiomes de $\N$}
\bgen[$\bullet$]
\item\textbf{Principe du bon ordre:} toute partie de $\N$ admet un plus petit élément
\item\textbf{Principe de descente infinie:} toute suite dans $\N$ strictement décroissante est finie.
\item\textbf{Principe des tiroirs:} si l’on range $(n + 1)$ chaussettes dans $n$ tiroirs, alors un tiroir contiendra au moins deux chaussettes.
\enen
}
\medskip\noindent
\ul{Remarques:}
\bgit
\item Le principe de bon ordre permet de donner une démonstration du principe de récurrence (qui devient alors un théorème de récurrence), \href{https://xymaths.fr/Lycee/TS/Cours-TS/Principe-de-recurrence-demonstration.php}{\ul{voir la démonstration là}}
\item Le reste de la division par 7 d'un entier non multiple de 7 ne peut prendre que 6 valeurs: 1, 2, ...,6.
Ainsi, à partir de la 7ème division, on retrouve forcément un reste déjà obtenu (7 resultats dans 6 tiroirs). Par exemple, on a
$\dfrac{10}7 = 1, 42857\,42857\,42\dots$ est le développement est périodique.
\enit
\bgex
Je dispose de 100 chaussettes, 50 noires et 50 rouges, toutes mélangées en vrac.\\
Avoir une chaussette rouge à un pied et une noire à l'autre est particulièrement moche.\\
Combien dois-je en tirer, au minimum, pour \^etre s\^ur d'avoir une paire de chaussettes de la m\^eme couleur ?
\enex
\section{Divisibilité dans $\Z$}
\bgprop{Rappels de règles de divisibilité:
\bgen[$\bullet$]
\item Un entier est divisible par 2 si et seulement si son chiffre des unités l'est, c'est-à-dire s'il se termnie par 0, 2, 4, 6 ou 8.\\
Un entier divisible par 2 est dit \textbf{pair}. S'il ne l'est pas, il est \textbf{impair}.
\item Un entier est divisible par 3 si et seulement si la somme de ses chiffres l'est
\item Un entier est divisible par 4 si et seulement si le nombre formé par ses deux derniers chiffres l'est
\item Un entier est divisible par 5 si et seulement si son chiffre des unités l'est, c'est-à-dire s'il se termnie par 0 ou 5
\item Un entier est divisible par 10 si et seulement si il est divisible à la fois par 2 et par 5, donc s'il se termine par 0.
\item Un entier est divisible par 9 si et seulement si la somme de ses chiffres l'est
\enen
}
\bgex
\bgen[a)]
\item Donner les éventuels diviseurs parmi 2, 3, 4, 5, 9 10 des nombres suivants:\\
20 \ - \ 54 \ - \ 126 \ - \ 1932 \ - \ - \ 2020 \ - \ 2040 \ - \ 10\,004
\item Donner \ul{tous} les diviseurs de:
20 \ - \ 36 \ - \ 54 \ - 147
\enen
\enex
\bgex
\bgen[a)]
\item Déterminer tous les couples d'entiers naturels $(x;y)$ tels que $x^2-2xy=15$
\item Déterminer tous les couples d'entiers naturels $(x;y)$ tels que $4x=20+2xy$
\enen
\enex
\bgdef{
Soit $a$ et $b$ deux entiers relatifs. \\
On dit que $a$ divise $b$ lorsque il existe un entier relatif $k$ tel que $b=ka$.
On note $a|b$.
On dit aussi que $a$ est un \textbf{diviseur} de $b$,
ou encore que $b$ est un \textbf{multiple} de $a$.
}
\medskip\noindent
\ul{Exemples:}
\bgen[$\bullet$]
\item $3|15$ car $15=5\tm3$ donc $3$ divise 15, et 15 est un multiple de 3.
\item $3|-24$ car $-24=3\tm(-8)$ donc $-8$ et $3$ sont des diviseurs de $-24$.
\item Tous les diviseurs de 24 dans $\N$ sont 1; 2; 3; 4; 8; 12; 24
\enen
\bgprop{\textbf{Divisibilité et combinaison linéraire}
Si $a|b$ et $a|c$ alors, pour tous entiers relatifs $\alpha$ et $\beta$,
\[a|(\alpha b+\beta c)\]
}
\bgproof{
On revient à la définition de la divisibilité: il existe deux entiers relatifs $k$ et $l$ tels que
\[\la\bgar{ll}
a|b \iff b=ka \\
a|c \iff c=la
\enar\right.\]
Maintenant, en multipliant par $\alpha$ la 1ère égalité et $\beta$ la 2ème puis en les ajoutant terme à terme, on obtient
\[\alpha b+\beta c = \alpha(ka) + \beta (la) = a\underbrace{\lp\alpha k+\beta l\rp}_{K\in\Z}\]
ce qui montre exactement que $a|(\alpha b+\beta c)$.
}
\medskip\noindent
\ul{Exemples:}
\bgen[$\bullet$]
\item $7|14$ et $7|700$ donc $7|728$ car $728=2\tm14 + 1\tm 700$.
\item Trouver une condition sur les diviseurs communs positifs à
$b=3k+1$ et $c=5k-2$, pour un entier $k$ quelconque.
Si $a$ est un tel diviseur, alors $a$ divise toute combinaison linéaire de $b$ et $c$, en particulier, $a$ divise
\[5b-3c = 5(3k+1)-3(5k-2) = 11\]
Or 11 est premier: ses seuls diviseurs sont 1 lui-m\^eme.
Ainsi, un diviseur commun à $b=3k+1$ et $c=5k-2$ ne peut \^etre que 1 ou 11.
\enen
\bgex
Déterminer, de deux manières différentes, les entiers relatifs $n$ tels que $(n-3)$ divise $(n+5)$.
\bgen[a)]
\item en revenant à la définition de la divisibilité
\item en remarquant que $(n-3)$ divise $(n-3)$ et en faisant intervenir une combinaison linéaire judicieuse de $(n-3)$ et $(n+5)$.
\enen
\enex
\bgex
\bgen
\item Pour quelles valeurs de l'entier naturel $n$ a-t-on $(n+8)$ divisible par $n$ ?
\item Pour quelles valeurs de l'entier relatif $n$ la fraction
$\dfrac{6n+12}{2n+1}$ est-elle un entier relatif ?
\enen
\enex
\bgex
\bgen[a)]
\item Montrer que si un entier naturel $d$ divise $(12n+7)$ et $(3n+1)$ alors il divise 3.
\item En déduire que la fraction $\dfrac{12n+7}{3n+1}$ est irréductible.
\enen
\enex
\section{Division euclidienne}
Rappel: poser la division de 34 par 4
\[\begin{tabular}{r|r}
35 & 4\\\cline{2-2}
32 & 8\\\psline[linestyle=dashed](-.3,.4)(.4,.4)
3
\end{tabular}\]
ce qui signifie que $35= 4\tm8+3$.\\
Dans ce calcul,
\bgit
\item $a=35$ est le \textbf{dividende}
\item $b=4$ est le \textbf{diviseur}
\item $q=5$ est le \textbf{quotient}
\item $r=3$ est le \textbf{reste}
\enit
Cette opération s'appelle la \textbf{division euclidienne de $a$ par $b$}:
\bgth{
Soit $a$ un entier relatif et $b$ un entier naturel non nul. \\
Il existe alors un unique couple d'entiers relatifs $(q ;r)$ tels que
\[a=bq+r\ , \text{ avec } 0\leqslant r<b \]
}
\medskip\noindent
\ul{Exemple:} \'Ecrire les divisions euclidiennes de 112 par 5 puis de 86 par 7.
\bgex
Trouver les entiers naturels $n$ qui ont, dans la division euclidienne par 4, un quotient égal au reste.
\enex
\bgex
Trouver un entier naturel qui, dans la division euclidienne par 23 a pour reste 1, et dans la division euclidienne par 17 a le m\^eme quotient et pour reste 13.
\enex
\bgex
La différence de deux entiers naturels est 885.
Si on divise l'un par l'autre, le quotient est 29 et le reste 17.
Quels sont ces deux entiers ?
\enex
\bgex
Un entier naturel $n$ est tel que si on le divise par 5 le reste vaut 3 et si on le divise par 6 le reste augmente de 1 et le quotient diminue de 1.
Déterminer $n$.
\enex
\bgex
Soit $n$ et $p$ deux entiers naturels. On sait que le reste dans la division euclidienne de $n$ par 11 vaut 8 et que le reste dans la division euclidienne de $p$ par 11 vaut 7.
Quel est le reste de $n+p$ dans la division euclidienne par 11 ?
\enex
\section{Congruences}
\subsection{Définition - Relation d'équivalence}
\bgdef{
Soit $a$ et $b$ deux entiers relatifs et $n\geqslant2$ un entier naturel. \\
On dit que $a$ et $b$ sont congrus modulo $n$ lorsque $a$ et $b$ ont le m\^eme reste dans la division euclidienne par $n$.\\
On note
\[a\equiv b\, [n] \quad \text{ ou }\quad a\equiv b\mod n\]
}
\medskip\noindent
\ul{Exemples}
\bgen[$\bullet$]
\item $47 = 9\tm5 +2$ et $32 = 6\tm5 + 2$ d'où $47\equiv32\,[5]$\\
En fait,
$47\equiv2\,[5]$ et $32\equiv2\,[5]$
\item $40\equiv0\,[2]$ car $40=20\tm2 + 0$
\item $-3\equiv4\,[7]$ car $-3= -1\tm7+4$
\enen
\bgcorol{\vspace{-.9em}
\bgen[$\bullet$]
\item Tout nombre est congru à son reste dans la division euclidienne:
si $a=bq+r$ alors $a\equiv r\,[q]$
\item $n$ est un diviseur de $a$ si et seulement si $a\equiv0\,[n]$ ($\iff a=qn+0$)
\item Un nombre $a$ est pair si et seulement si $a\equiv0\,[2]$\\
$a$ est impair si et seulement si $a\equiv1\,[2]$
\item $a\equiv b\,[n] \iff a-b\equiv 0\,[n]$
\enen
}
Cette relation \og est congru à\fg\, est ce qu'on appelle \textbf{une relation d'équivalence}.
Ce type de relation est fondamentale en mathématiques: elle permet de mettre en relation des éléments dans un ensemble, donc les catégoriser suivant une propriété donnée. Plus tard (après le bac...) on pourra ainsi regarder non plus chaque élément seul, mais chaque groupe d'éléments ainsi formé, qu'on appelle alors une classe d'équivalence, et travailler plus abstraitement sur les propriétés de chaque classe.
\bgprop{La congruence est une \textbf{relation d'équivalence}, c'est-à-dire une relation qui vérifie, pour tous entiers $a$, $b$et $c$,
\bgen[1.]
\item\textbf{Réflexivité:} $a\equiv a\,[n]$
\item\textbf{Symétrie:} $a\equiv b\,[n] \Longrightarrow b\equiv a\,[n]$
\item\textbf{Transitivité:} si $a\equiv b\,[n]$ et $b\equiv c\,[n]$
alors $a\equiv c\,[n]$
\enen
}
\noindent
\ul{Autres exemples:}
\bgit
\item La relation \og est égale à\fg{} est une relation d'équivalence sur l'ensemble des nombres entiers (ou des nombres réels, ou des fonctions, ...)
\item la relation \og avoir le m\^eme \^age\fg{} est une relation d'équivalence sur l'ensemble des \^etres humains
\item la relation \og \^etre parallèle à\fg{} est une relation d'équivalence sur l'ensemble des droites du plan
\item Dans l'ensemble des couples de $\N^2$, on définit la relation d'équivalence (essayer de montrer que cette relation est bien réflexive, symétrique et transitive\dots) entre deux couples
\[(a;b)\equiv (c;d) \iff ad=bc\]
Cette relation d'équivalence s'écrit aussi
$ad=bc \iff \dfrac{a}b=\dfrac{c}d$: c'est l'égalité entre les fractions !
Une fraction est bien un couple d'entiers (numérateur ; dénominateur) qui admet une infinité de représentant, par exemple $(1;3)\equiv(2;6)\equiv(12;36)\equiv\dots$
Dans notre utilisation des fractions, ensuite, on peut se contenter d'utiliser un représentant quelconque pour toute une classe d'équivalence, $(1;3)$ dans l'exemple précédent.
On utilise ainsi déjà, très couramment, des classes d'équivalence en maths !
\enit
\subsection{Congruences et opérations}
Il est important de savoir comment se comportent les opérations usuelles avec les congruences.
\bgprop{Soit $a$, $b$, $c$ et $d$ des entiers relatifs, et $n\geqslant2$ un entier naturel.\\
Si $a\equiv b\,[n]$ et $c\equiv d\,[n]$ alors
\bgen
\item $a+c\equiv b+d\,[n]$ (\textbf{addition terme à terme})
\item $a-c\equiv b-d\,[n]$ (\textbf{soustraction terme à terme})
\item $ac\equiv bd\,[n]$ (\textbf{multiplication terme à terme})\\
En particulier, pour tout entier $p$, $a^p\equiv b^p\,[n]$
\enen
}
\bgproof{La démonstration est assez importante à conna\^itre car elle contient des mécanismes très courants et utiles (en exercices entre autre).
L'idée principale est de revenir à la définition de la congruence et la division euclidienne. \\
Pour le 1er point, on traduit:
\[\la\bgar{ll}
a\equiv b\,[n] \iff a=kn + b\\[.4em]
c\equiv d\,[n] \iff c=k'n + d
\enar\right.\]
d'où, en ajoutant termes à termes
\[\bgar{cccl}&a+c&=&(k+k')n + b+d\\
\iff&(a+c)&=&k''n+(b+d)\\
\iff&(a+c)&=&(b+d)\,[n]\enar\]
On obtient le deuxième point de m\^eme en soustrayant termes à termes.\\
De m\^eme encore, en mulipliant termes à termes, puis en développent et ordonnant, on obtient
\[\bgar{lcl}
ac&=&(kn+b)(k'n+d)\\
&=&kk'n^2+kdn+k'bn+bd
\enar\]
Enfin, pour faire appar\^itre la division euclidienne par $n$, on factorise au plus par $n$, soit
\[ac=n\underbrace{\Bigl(kk'n+kd+k'b\Bigr)}_{q}+bd\]
d'où
\[ac=qn+bd\iff ac=bd\,[n]\]
}
\bigskip
Donnons maintenant deux exemples d'utilisation de ces règles de calculs sur les congruences.
\bigskip\noindent
\textbf{\ul{Exemple 1:}} Montrer que, pour tout entier $n$, le produit $n(n+1)(2n+1)$ est divisible par 3.
Il n'y a que 3 restes possibles dans la division par 3, et on peut penser à traiter ce genre de problème par \textbf{disjonction de cas}, c'est-à-dire en étudiant \textbf{tous les cas}.\\
Par exemple, sous la forme d'un tableau de congruence:
\[\renewcommand\arraystretch{1.8}
\begin{tabular}{|*4{c|}}\hline
$n\,[3]$ & 0 & 1 & 2 \\\hline
$(n+1)\,[3]$ & 1 & 2 & $3\equiv0$\\\hline
$(2n+1)\,[3]$ & 1 & $3\equiv0$ & $5\equiv2$\\\hline
$n(n+1)(2n+3)[3]$ & 0 & 0 & 0 \\\hline
\end{tabular}\]
Dans tous les cas, le produit est congru à 0 modulo 3, ce qui signifie exactement que ce produit est divisible par 3.
\bigskip\noindent
\textbf{\ul{Exemple 2:}} Donner le reste de la division euclidienne de $18^{23}$ par 7.
\medskip
\ul{Méthode 1:} par congruences successives.
On a $18=2\tm7+4$ donc $18\equiv4\,[7]$
et donc $18^{23}\equiv4^{23}\,[7]$
On dimminue la puissance en écrivant maintenant $4^{23}=\lp4^2\rp^{11}\tm4$
or $4^2=16\equiv2\,[7]$, d'où
$4^{23}=\lp4^2\rp^{11}\tm4\equiv2^{11}\tm4\,[7]$
Maintenant $2^{11}\tm4=2^{11}\tm2^2=2^{13}$ et on cherche encore à diminuer la puissance: $2^{13}=\lp2^3\rp^4\tm2$
Mais, $2^3=8\equiv1\,[7]$ d'où
$2^{13}\equiv1\tm2\,[7]$.
Finalement, par transitivité, $18^{23}\equiv2\,[7]$
\medskip
\ul{Méthode 2:} Dans la méthode précédente, dès qu'on arrive à une congruence à 1, les calculs sont grandement simplifiés. Autant chercher cela dès le début:
On a $18^1=2\tm7+4$ donc $18^1\equiv4\,[7]$ \\
Ensuite, $18^2=18\tm18\equiv4\tm4\,[7]\equiv16\,[7]\equiv2\,[7]$\\
Après, $18^3=18\tm18^2\equiv4\tm2\,[7]\equiv1\,[7]$.
On va donc chercher à faire appara\^itre cette puissance:
\[18^{23}=\lp18^3\rp^7\tm18^2\]
et donc, avec les résultats précédents,
\[18^{23}\equiv1^7\tm2\,[7]\equiv2\,[7]\]
\bigskip
\bgex
Donner le reste de la division euclidienne de $4^2$ par 15.
En déduire que que $4^{6n}-1$ est divisible par 15.
\enex
\bgex
Déterminer le reste de la division euclidienne de $39^{60}$ par 7.
\enex
\bgex
Déterminer le chiffre des unités dans l'écriture décimale de $3^{2023}$.
\enex
\bgex
\bgen
\item Déterminer, suivant les valeurs de $n$, les restes possibles de $2^n$ dans la division par 9. Résumer les résultats dans un tableau de congruence.
\item En déduire les entiers $n$ tels que $2^n-1$ est divisible par 9.
\enen
\enex
\bgex
\bgen
\item Déterminer, suivant les valeurs de $n$, les restes possibles de $3^n$ dans la division par 7. Résumer les résultats dans un tableau de congruence.
\item En déduire les entiers $n$ tels que $3^n-6$ est divisible par 7.
\item En déduire que $164^{2021}\equiv5 [7]$.
\enen
\enex
\bgex
Le 1er janvier 2012 était un dimanche.
\bgen
\item Calculer le nombre de jours séparant ce 1er janvier 2012 du 1er janvier 2019.\\
En déduire quel était le jour de la semaine du 1er janvier 2019.
\item Quel est le jour de la semaine du 1er janvier 2040 ?
\enen
\enex
\bgex
On appelle inverse de $x$ modulo 5, un entier $y$ tel que $xy\equiv1 [5]$.
\bgen[1.]
\item Déterminer un inverse modulo 5 de $x=2$.
\item Déterminer un inverse modulo 5 de $x=3$ et $x=4$.
\item Est-ce que $x=5$ admet un inverse ?
\item \`A l'aide d'un tableau de congruence, déterminer suivant la valeur de $x$ son inverse modulo 5.
\item Résoudre les équations \quad
$E_1: 2x\equiv 3 [5]$ \quad et $E_2: 9x\equiv 1 [5]$
\enen
\enex
\bigskip
\ul{Remarque:} L'ensemble $\mathbb{F}_5=\la 0; 1; 2; 3; 4\ra$ est un \textbf{corps}: tous ses éléments (sauf 0) ont un inverse dans $\mathbb{F}_5$.\\
Dans cet ensemble, on peut résoudre toutes les équations du premier degré $ax=b$, comme dans $\R$ et dans $C$ (mais pas dans $\N$, et $\Z$).
\bgex
On décide de former des nombres dans le système décimal en écrivant de gauche à droite quatre chiffres consécutifs dans l'ordre croissant puis on permute les deux premiers chiffres de gauche.\\
Par exemple, à partir de 4567 on obtient 5467, ou encore à partir de 2345 on obtient 3245.
Démontrer que tous les entiers naturels ainsi obtenus sont multiples de 11.
\enex
\bgex
On considère un entier de 3 chiffres. On appelle renversé de cet entier le nombre qui s'écrit en échangeant les chiffres des centaines et des unités.\\
Par exemple, le renversé de 238 est 832.
Montrer que la différence entre un entier et son renversé est divisible par 9.
\enex
\bgex
On considère la suite $(u_n)$ d'entiers définie par $u_0=14$ et, pour
tout entier naturel $n$,
\[u_{n+1}=5u_n-6\]
\bgen
\item Calculer $u_1$, $u_2$, $u_3$ et $u_4$. \\ Quelle conjecture
peut-on faire concernant les deux derniers chiffres de $u_n$ ?
\item Montrer que, pour tout entier $n$, on a $u_{n+2}\equiv u_n
[4]$.\\ En déduire que, pour tout entier $n$, on a $u_{2n}\equiv 2
[4]$ et $u_{2n+1}\equiv0 [4]$.
\item
\bgen[a)]
\item Montrer par récurrence que pour tout entier naturel $n$, on a
$2u_n=5^{n+2}+3$.
\item En déduire que, pour tout entier naturel $n$, $2u_n\equiv 28
[100]$.
\item Déterminer les deux derniers chiffres de l'écriture décimale
de $u_n$ suivant les valeurs de $n$. \enen
\enen
\enex
\label{LastPage}
\end{document}
Télécharger le fichier source 
