Arithmétique :

Exercice Type 1 :

 Trouver les solutions de 31x+58y=1

 trouver le PGCD de 58 et de 23 : Algorithme d'Euclide.
58 = 31 * 1 + 27
31 = 27 * 1 + 4
27 =  4 * 6 + 3
 4 =  3 * 1 + 1
 3 =  1 * 3 + 0

(forme a = b*q + r, ou q est le quotient, r le reste, a et b les 2 nombres a diviser,a la ligne qui quit suit, b devient a, r devient b, et ainsi de suite jusqu'a ce que r = 0)
Alors le PGCD est le dernier b (ou le dernier r non nul).

 Trouver une solution particuliere : remonter l'algorithme d'Euclide.

Truc : réécrire l'algorithme d'Euclide différemment :
a = b*q +r    r = a - b*q

27 = 58 - 31*1
4  = 31 - 27*1
3  = 27 - 4*6
1  = 4 - 3*1
0  = 3 - 1*3

On veut 58x+31y = 1, on veut donc un "=1", on sait que 1 = 4 - 3*1, on part de la :
(c'est toujours la meme chose)

1 =  4 – 3*1
On peut remplacer le 4 et le 3 par quelque l’une des lignes d’au dessus :
Le truc est de tout exprimer en fonction de 31 ou de 58 (nombre de départ)
NE JAMAIS EFFECTUER D’OPERATIONS A CE STADE ! On factorise et on développe, mais on ne fait pas d’opérations !

1 = (31 – 27*1) – (27 – 4*6)*1
on développe :
1 = 31 – 27*1 – 27*1 + (4*6)*1
comme on veut une forme 1 = 31 * a + 58 *b, on factorise.
1 = 31 * (1) + 58*(0)  - 27*1 –27*1 + (4*6)*1
Il faut donc transformer ce dernier bloc : - 27*1 –27*1 + (4*6)*1.
on sait que 27 = 58 – 31*1 et  4 = 31 – 27*1.
donc
1 = 31* (1) + 58*(0) – (58 – 31*1)*1 – (58 – 31*1)*1 + ((31 - 27*1)*6)*1
On développe a nouveau !
1 = 31*(1) + 58*(0) – 58*1 + 31*1*1 – 58*1 + 31*1*1 + 31*6*1 – 27*1*6*1
Et on refactorise ce qu’on peut !
1 = 31*(1 + 1*1 +1*1 + 6*1) + 58*(-1-1)   -27*1*6*1
On a encore un 27 qui fait chier ! on transforme : 27 = 58 – 31*1
1 = 31*(1 + 1*1 +1*1 +6*1) + 58*(-1-1)   - (58 – 31*1)*1*6*1
on développe !
1 = 31*(1 + 1*1 +1*1 +6*1) + 58*(-1-1) – 58*1*6*1 + 31*1*1*6*1
Et on refactorise :
1 = 31*(1 + 1*1 +1*1 +6*1 + 1*1*6*1) + 58*(-1-1 – 1*6*1)
ça y’est on a plus rien qui nous emmerde, on a le droit de calculer ce qu’il y a entre parenthèse
1 = 31*(15) + 58*(-8)

On a donc une solution particulière : x0 = 15 et y0 = -8, et on vérifie : 31*15 +58*-8 =1 :ça marche !
(Quand on est a l’aise (Blaise) on peut se permettre de faire des calculs pendant, et aller plus vite, mais c’est un coup à se planter, et c’est plus prudent de faire les calculs a la fin)
(le Dragon a dit : la voie la plus courte est souvent la plus dangereuse…)

 Résolution finale : Lemme de GAUSS

On a 31*x0 + 58*y0 = 1 (solution particulière)
et 31*x + 58*y = 1 (solution générale)
les 2 donnent « =1 »
Donc on peut écrire 

31*x0 + 58*y0 = 31*x + 58*y
On passe les 31 d’un coté, les 58 de l’autre :
31*x0 – 31*x = 58*y – 58*y0
On factorise !
31*(x0 – x) = 58*(y – y0)
Lemme de Gauss : Si a divise b*c et a et b premiers entre eux, alors a divise c.
Comme 31 et 58 sont premiers entre eux (PGCD = 1), alors selon le lemme de Gauss :
31 divise (y – y0)	 (y – y0) = 31 * q + 0	 y – y0 ≡ 0 [31]  y ≡ y0 [31]
58 divise (x0 – x)	 (x0 –x) = 58 *q’ + 0 	 x0 – x ≡ 0 [58]  x ≡ x0 [58]
D’ou :
y ≡ -8 [31]		y ≡ 23 [31]
x ≡ 15 [58]		x ≡ 15 [58]
Ainsi sont les solutions générales…

Exercice Type 2 :

quel est le reste de la divisions de 123456 par 9 ?

 manipulation des congruences :

ça ressemble fortement à un = .
123456 ≡ 123456 [9]
123456 ≡ 1*105 + 2*104 + 3*103 + 4*102 + 5*10 + 6 [9]
or d’après des règles sur les congruences, on a : 
10 ≡ 1 [9] « 10 est congru a 1 modulo 9  le reste de la divison de 10 par 9 est 1 »
donc 10x ≡ 1x [9] ≡ 1 [9]
donc 123456 ≡ 1*1 + 2*1 +3*1 +4*1 +5*1 +6 [9]
 123456 ≡ 21 [9]
 123456 ≡ 3 [9]
règles sur les congruences : si a ≡ b [n] alors a + c ≡ b + c [n] et a*c ≡ b*c [n]

Exercice Type 3 :

Prouver que P = n3 –3n2 +2n est divisble par 3 pour tout n …

 idée : on factorise : n3 –3n2 +2n = (n –2)(n – 1)n
Factorisé, il suffit de démontrer que 3 divise (n –2) ou (n –1) ou n.
On envisage 3 cas :
•	Si n ≡ 0 [3] alors n divise P…
•	Si n ≡ 1 [3] alors n –1  ≡ 0 [3]  et (n –1) divise P…
•	Si n ≡ 2 [3] alors n –2  ≡ 0 [3] et (n –2) divise P…
Donc pour tout n, P est divisible par 3. CQFD