Solution :
On examine les cas modulo 6 :
• Si n ≡ 0 mod 6 : évident
• Si n ≡ ±1 mod 6 : n² + 5 ≡ 1 + 5 ≡ 0 mod 6
• Si n ≡ ±2 mod 6 : n² + 5 ≡ 4 + 5 ≡ 9 ≡ 0 mod 3 et n est pair ⇒ divisible par 6
• Si n ≡ 3 mod 6 : n² + 5 ≡ 9 + 5 ≡ 14 ≡ 2 mod 6 mais n est divisible par 3 et le produit par 2 ⇒ divisible par 6

Solution :
150 = 84 × 1 + 66
84 = 66 × 1 + 18
66 = 18 × 3 + 12
18 = 12 × 1 + 6
12 = 6 × 2 + 0
Le dernier reste non nul est 6 ⇒ PGCD(84,150) = 6

Solution :
Algorithme d’Euclide étendu :
17 = 13×1 + 4
13 = 4×3 + 1
4 = 1×4 + 0
Remontée : 1 = 13 – 4×3 = 13 – (17-13)×3 = 4×13 – 3×17
⇒ Solution particulière : x = -3, y = 4

Solution :
• On cherche l’inverse de 5 modulo 7 : 5×3 = 15 ≡ 1 mod 7 ⇒ inverse est 3
• On multiplie les deux côtés par 3 : x ≡ 9 mod 7 ⇒ x ≡ 2 mod 7
• Solution générale : x = 7k + 2, k ∈ ℤ

Solution :
On utilise l’identité de Sophie Germain :
n⁴ + 4 = (n²)² + (2)² = (n² + 2)² – (2n)² = (n² – 2n + 2)(n² + 2n + 2)
Pour n ≥ 2, les deux facteurs sont > 1 ⇒ n⁴ + 4 est composé

Solution :
36 = 2² × 3²
60 = 2² × 3 × 5
PPCM = produit des facteurs avec les plus grands exposants = 2² × 3² × 5 = 180

Solution :
1. PGCD(15,21) = 3 qui divise 9 ⇒ solutions existent
2. On simplifie : 5x + 7y = 3
3. Solution particulière : x = 2, y = -1
4. Solution générale : x = 2 + 7k, y = -1 – 5k, k ∈ ℤ

Solution :
Par le petit théorème de Fermat, 7¹⁰ ≡ 1 mod 11
222 = 22×10 + 2 ⇒ 7²²² = (7¹⁰)²² × 7² ≡ 1 × 49 ≡ 5 mod 11

Solution :
-25 = 7 × (-4) + 3
On vérifie : 0 ≤ 3 < 7
⇒ Quotient = -4, Reste = 3

Solution :
1. Soit d un diviseur commun de a+b et ab. Comme a∧b=1, d est premier avec a et b (théorème de Gauss) ⇒ d=1
2. a²+b² = (a+b)² – 2ab. Soit d = PGCD(a+b, a²+b²).
d divise 2ab, mais d∧ab=1 ⇒ d divise 2 ⇒ d ∈ {1,2}