Exercice Type 1 :

 Trouver les solutions de 31x+58y=1

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

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…)

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 ?

ça ressemble fortement à un = .

123456 ≡ 123456 [9]

123456 ≡ 1*10⁵ + 2*10⁴ + 3*10³ + 4*10² + 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 10^x ≡ 1^x [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 = n³ –3n² +2n est divisble par 3 pour tout n …

à idée : on factorise : n³ –3n² +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

^{Source : www.fvirtman.fr.st – Auteur : Fman}
ÓSNOCLUB.fr.st