Exercices corrigés — Arithmétique & structures

On cherche $(q,r)$ avec $2024=17q+r$ et $0\le r<17$.

$17\times100=1700$, $17\times119=2023$.

En déduire $r$.

$17\times119=2023\le2024<2040=17\times120$, donc $q=119$.

$r=2024-2023=1$, et $0\le1<17$. ✓

$\operatorname{pgcd}(a,b)=\operatorname{pgcd}(b,r)$ où $r$ est le reste de $a$ par $b$.

Itérer : $252=198\cdot1+54$, puis $198$ par $54$…

S'arrêter au reste nul ; le PGCD est le dernier reste non nul.

$252=198\cdot1+54$ ; $198=54\cdot3+36$ ; $54=36\cdot1+18$ ; $36=18\cdot2+0$.

Dernier reste non nul : $\operatorname{pgcd}(252,198)=18$.

$\operatorname{pgcd}\times\operatorname{ppcm}=|ab|$.

$\operatorname{ppcm}=\dfrac{252\times198}{18}$.

Simplifier.

$\operatorname{ppcm}=\dfrac{252\times198}{\operatorname{pgcd}}=\dfrac{252\times198}{18}$.

$\dfrac{198}{18}=11$, donc $\operatorname{ppcm}=252\times11=2772$.

Factoriser chaque nombre.

PGCD : $\min$ des exposants ; PPCM : $\max$ des exposants.

$360=2^3\cdot3^2\cdot5$, $84=2^2\cdot3\cdot7$.

$360=2^3\cdot3^2\cdot5$ ; $84=2^2\cdot3\cdot7$.

$\min$ des exposants : $2^{\min(3,2)}\cdot3^{\min(2,1)}=2^2\cdot3=12$.

$\max$ des exposants : $2^3\cdot3^2\cdot5\cdot7=2520$.

Nombre de diviseurs : $\prod(\alpha_i+1)$.

Somme : $\prod\dfrac{p_i^{\alpha_i+1}-1}{p_i-1}=\prod(1+p_i+\dots+p_i^{\alpha_i})$.

$1+2+4+8=15$, $1+3+9=13$, $1+5=6$.

$(3+1)(2+1)(1+1)=4\cdot3\cdot2=24$ diviseurs.

$\sigma(360)=(1+2+4+8)(1+3+9)(1+5)=15\cdot13\cdot6=1170$.

Tester la divisibilité par les premiers $\le\sqrt n$.

$\sqrt{211}\approx14{,}5$ : tester $2,3,5,7,11,13$.

Pour $221$, chercher un diviseur évident.

Non divisible par $2,3,5,7,11,13$ (tous les premiers $\le\sqrt{211}$) : $211$ est premier.

$221=13\times17$ : non premier.

Reprendre les divisions de l'algorithme d'Euclide (A2).

Remonter en exprimant $18$ à partir des restes successifs.

$18=54-36$, puis $36=198-54\cdot3$, puis $54=252-198$.

$18=54-36=54-(198-54\cdot3)=54\cdot4-198=(252-198)\cdot4-198$.

$18=252\cdot4-198\cdot5$, donc $u=4$, $v=-5$.

$15\mid 7n$ et on connaît $\operatorname{pgcd}(7,15)$.

Gauss : si $a\mid bc$ et $\operatorname{pgcd}(a,b)=1$, alors $a\mid c$.

Ici $a=15$, $b=7$, $c=n$.

$\operatorname{pgcd}(7,15)=1$.

$15\mid7n$ avec $\operatorname{pgcd}(15,7)=1$ $\Longrightarrow$ $15\mid n$.

Réduire chaque facteur modulo $7$ AVANT de multiplier.

$123=7\cdot17+4$, $456=7\cdot65+1$.

Multiplier les restes.

$123\equiv4\pmod7$ ; $456\equiv1\pmod7$.

$123\times456\equiv4\times1=4\pmod7$.

$10\equiv1\pmod9$ : $n\equiv$ somme des chiffres.

$10\equiv-1\pmod{11}$ : $n\equiv$ somme alternée des chiffres.

Chiffres de $1234$ : $1,2,3,4$.

$1234\equiv1+2+3+4=10\equiv1\pmod9$.

somme alternée (de droite à gauche) : $4-3+2-1=2$, donc $1234\equiv2\pmod{11}$.

$\operatorname{pgcd}(17,5)=1$ divise $1$ : il y a des solutions.

Trouver une solution particulière par Bézout : $17\cdot3+5\cdot(-10)=1$.

Solution générale : $x=x_0+\frac{b}{d}t$, $y=y_0-\frac{a}{d}t$ avec $d=1$.

$17\cdot3+5\cdot(-10)=51-50=1$, donc $(x_0,y_0)=(3,-10)$.

$x=3+5t$, $y=-10-17t$, $t\in\mathbb Z$.

$\operatorname{pgcd}(3,7)=1$ : $3$ est inversible modulo $7$.

Trouver $3^{-1}\pmod7$ ($3\cdot5=15\equiv1$).

Multiplier les deux membres par cet inverse.

$3\cdot5=15\equiv1\pmod7$, donc $3^{-1}\equiv5$.

$x\equiv5\cdot4=20\equiv6\pmod7$.

Le reste doit vérifier $0\le r<6$ (donc positif).

$6\times(-8)=-48\le-47$.

$r=-47-(-48)$.

$6\times(-8)=-48\le-47<-42=6\times(-7)$, donc $q=-8$.

$r=-47-(-48)=1$, et $0\le1<6$. ✓

Euclide : $1001=770\cdot1+231$, puis $770$ par $231$…

Continuer jusqu'au reste nul.

Ou factoriser : $1001=7\cdot11\cdot13$.

$1001=770+231$ ; $770=231\cdot3+77$ ; $231=77\cdot3+0$.

$\operatorname{pgcd}(1001,770)=77$.

$12=2^2\cdot3$, $18=2\cdot3^2$.

PGCD = min des exposants ; PPCM = max.

Vérifier $\operatorname{pgcd}\times\operatorname{ppcm}=12\times18$.

$2^{\min(2,1)}\cdot3^{\min(1,2)}=2\cdot3=6$.

$2^2\cdot3^2=36$ ; et $6\times36=216=12\times18$. ✓

Chercher une petite puissance de $2$ congrue à $1$ modulo $7$.

$2^3=8\equiv1\pmod7$.

$10=3\cdot3+1$.

$2^3\equiv1\pmod7$.

$2^{10}=(2^3)^3\cdot2\equiv1^3\cdot2=2\pmod7$.

$\operatorname{pgcd}(5,8)=1$ : $5$ inversible.

$5\cdot5=25\equiv1\pmod8$, donc $5^{-1}\equiv5$.

Multiplier par l'inverse.

$5^{-1}\equiv5\pmod8$.

$x\equiv5\cdot3=15\equiv7\pmod8$.

Chercher un diviseur de $91$.

$100=2^2\cdot5^2$.

Nombre de diviseurs : $\prod(\alpha_i+1)$.

$91=7\times13$ : non premier.

$100=2^2\cdot5^2$ $\Longrightarrow$ $(2+1)(2+1)=9$ diviseurs.