Divisibilité dans Z

Le cours

1. Divisibilité dans Z\n\nDéfinition : Soient a,b∈Z. On dit que a divise b (noté a|b) s'il existe k∈Z tel que b = a×k.\n\nPropriétés :\n- Si a|b et b|c alors a|c\n- Si a|b et a|c alors a|(bx+cy) pour tous x,y∈Z\n- Si a|b et b|a alors a=±b\n\n## 2. Division euclidienne\n\nThéorème : Pour tout a∈Z et b∈N, il existe un unique couple (q,r)∈Z×N tel que :\n$$a = bq + r \\quad \\text{avec} \\quad 0 \\leq r < b$$\nq est le quotient, r le reste.\n\nExemple : Division de 23 par 5 : 23=5×4+3 (q=4, r=3)\nDivision de -23 par 5 : -23=5×(-5)+2 (q=-5, r=2)\n\n## 3. Congruences\n\nDéfinition : a≡b [n] si n|(a-b) (n>0)\n\nPropriétés (compatibilité avec opérations) :\nSi a≡b [n] et c≡d [n], alors :\n- a+c≡b+d [n]\n- a-c≡b-d [n]\n- a×c≡b×d [n]\n- a^k≡b^k [n] pour k∈N\n\nAttention : Pas de division générale avec les congruences.\n\n## 4. Nombres premiers\n\nDéfinition : p∈N est premier si p≥2 et ses seuls diviseurs sont 1 et p.\n\nListe : 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,...\n\nPropriétés :\n- Il y a une infinité de nombres premiers (Euclide)\n- Tout n≥2 se décompose de façon unique en produit de facteurs premiers\n\nCrible d'Ératosthène : Méthode pour trouver les nombres premiers ≤N.\n\n## 5. Décomposition en facteurs premiers\n\nThéorème fondamental de l'arithmétique : Tout entier n≥2 s'écrit de manière unique :\n$$n = p_1^{α_1} p_2^{α_2} \\cdots p_k^{α_k}$$\noù p_i sont premiers distincts et α_i≥1.\n\nExemple : 360=2³×3²×5\n\n## 6. Critères de divisibilité\n\n| Diviseur | Critère | Exemple |\n|----------|---------|---------|\n| 2 | Chiffre des unités pair | 346 : 6 pair ⇒ divisible par 2 |\n| 3 | Somme des chiffres multiple de 3 | 123 : 1+2+3=6 ⇒ divisible par 3 |\n| 4 | Nombre formé par les 2 derniers chiffres multiple de 4 | 1324 : 24 divisible par 4 ⇒ oui |\n| 5 | Chiffre des unités 0 ou 5 | 345 : unité 5 ⇒ oui |\n| 9 | Somme des chiffres multiple de 9 | 567 : 5+6+7=18 ⇒ oui |\n| 10 | Chiffre des unités 0 | 450 ⇒ oui |\n| 11 | Différence (somme chiffres de rang impair) - (somme chiffres de rang pair) multiple de 11 | 121 : (1+1)-2=0 ⇒ oui |\n\n## 7. Changements de base\n\nBase b : Tout entier n s'écrit de façon unique :\n$$n = a_k b^k + a_{k-1} b^{k-1} + \\cdots + a_1 b + a_0$$\navec 0≤a_i<b.\n\nMéthode pour passer de base 10 à base b : Divisions successives par b.\n\nExemple : 43 en base 2 :\n43÷2=21 reste 1\n21÷2=10 reste 1\n10÷2=5 reste 0\n5÷2=2 reste 1\n2÷2=1 reste 0\n1÷2=0 reste 1\nLecture des restes de bas en haut : 43₁₀=101011₂.\n\n## 8. Application à l'informatique\n\n- Base 2 (binaire) : chiffres 0,1\n- Base 8 (octal) : chiffres 0-7\n- Base 16 (hexadécimal) : chiffres 0-9, A-F\n\nExemple ivoirien : Le code postal d'Abidjan 01 peut être vu en binaire : 01₁₀=00000001₂.\n\n## 9. Petits théorèmes\n\nThéorème : Si p premier et p∤a, alors a^{p-1}≡1 [p] (Fermat)\n\nApplication : Vérifier si un nombre est premier (test probabiliste).\n\n## 10. Problèmes classiques\n\nExemple : Montrer que n(n+1)(2n+1) est divisible par 6 pour tout n∈N.\n\nSolution :\n- n(n+1) est pair (produit de 2 entiers consécutifs)\n- Parmi n, n+1, 2n+1, l'un est multiple de 3 (analyse des cas modulo 3)\nDonc divisible par 2 et par 3 ⇒ par 6.\n\nmermaid\ngraph TD\n A[Entier n] --> B{Divisible par 2?}\n A --> C{Divisible par 3?}\n B -->|Oui| D[Multiple de 2]\n C -->|Oui| E[Multiple de 3]\n D --> F[Divisible par 6]\n E --> F\n\n\n## 11. Retour à la situation initiale\n\nVérifions : 4358 = 1000100000110₂ ?\nCalculons 1000100000110₂ en base 10 :\n= 1×2¹² + 0×2¹¹ + ...\n2¹²=4096\n2⁷=128\n2²=4\n2¹=2\nSomme = 4096+128+4+2 = 4230 ? Attendez, erreur...\nRecalculons : 1000100000110₂ = 1×2¹² + 0×2¹¹ + 0×2¹⁰ + 0×2⁹ + 1×2⁸ + 0×2⁷ + 0×2⁶ + 0×2⁵ + 0×2⁴ + 0×2³ + 1×2² + 1×2¹ + 0×2⁰\n= 4096 + 256 + 4 + 2 = 4358. Correct !\n\nVérification* : 2¹²=4096, 2⁸=256, 2²=4, 2¹=2, total=4358.