Exercices corrigés — Divisibilité Et Congruences (Tle expertes)

1. On développe : \[(n+2)(3n+2)=3n^2+8n+4.\] Donc \(\boxed{A_n=(n+2)(3n+2)+1}\).

2. Comme \(0\le 1

3. Tout diviseur commun de \(A_n\) et \(n+2\) divise \(A_n-(3n+2)(n+2)=1\). Ainsi \[\boxed{\operatorname{PGCD}(A_n,n+2)=1}.\]

4. Par définition, \(A_n\) et \(n+2\) sont donc \(\boxed{\text{premiers entre eux}}\).

Conclusion : la division euclidienne fournit immédiatement une information de coprimalité.

1. On obtient \[3,\ 2,\ 6,\ 4,\ 5,\ 1\pmod7.\]

2. En particulier, \(\boxed{3^6\equiv1\pmod7}\), puis les restes se répètent avec une période divisant \(6\).

3. \(2026=6\times337+4\), donc \[3^{2026}\equiv3^4\equiv\boxed4\pmod7.\]

4. Dans le cycle, \(-1\equiv6\pmod7\) apparaît pour l'exposant \(3\). Ainsi \[\boxed{3^n\equiv-1\pmod7\iff n\equiv3\pmod6}.\]

Conclusion : les puissances modulo un entier se traitent efficacement par cycles.

1. \[2520=1980+540,\quad1980=3\times540+360,\quad540=360+180,\quad360=2\times180.\] Donc \(\boxed{\operatorname{PGCD}(2520,1980)=180}\).

2. Les restes non nuls sont \(\boxed{540,360,180}\).

3. \[180=540-360=540-(1980-3\times540)=4\times540-1980.\] Or \(540=2520-1980\), donc \[180=4\times2520-5\times1980.\]

4. On peut prendre \(\boxed{u=4\text{ et }v=-5}\).

Conclusion : l'algorithme d'Euclide étendu fournit simultanément le PGCD et une relation de Bézout.

1. L'algorithme d'Euclide conduit à \(\boxed{\operatorname{PGCD}(101,37)=1}\).

2. La remontée donne \[\boxed{1=11\times101-30\times37}.\]

3. Modulo \(101\), \(-30\times37\equiv1\). Ainsi un inverse de \(37\) est \(-30\), soit \(\boxed{71}\) modulo \(101\).

4. \[x\equiv24\times71=1704\equiv\boxed{88}\pmod{101}.\]

Conclusion : une relation de Bézout permet de déterminer directement un inverse modulaire.

1. \[\boxed{45360=2^4\times3^4\times5\times7}.\]

2. Le nombre de diviseurs positifs vaut \[(4+1)(4+1)(1+1)(1+1)=\boxed{100}.\]

3. Le plus grand carré diviseur est \[2^4\times3^4=\boxed{1296}.\]

4. Il faut rendre pairs les exposants de \(5\) et \(7\). Le plus petit multiplicateur est donc \(\boxed{k=35}\).

Conclusion : la décomposition en facteurs premiers transforme les questions de divisibilité en questions sur les exposants.

1. \[n^3-n=(n-1)n(n+1).\] Parmi trois entiers consécutifs, l'un est multiple de \(3\) et au moins l'un est pair. Donc \(\boxed{6\mid n^3-n}\).

2. Pour \(n\equiv0,1,2,3,4\pmod5\), on vérifie que \(n^5\equiv n\pmod5\). Ainsi \(\boxed{5\mid n^5-n}\).

3. Modulo \(2\), \(n^5\equiv n\). Modulo \(3\), les restes \(0,1,2\) donnent également \(n^5\equiv n\). Donc \(2\) et \(3\) divisent \(n^5-n\).

4. Comme \(2,3,5\) sont deux à deux premiers entre eux, leur produit divise \(n^5-n\). Donc \[\boxed{30\mid n^5-n}.\]

Conclusion : combiner factorisation et congruences donne une démonstration courte et générale.

1. \(\operatorname{PGCD}(14,30)=2\) et \(2\mid8\), donc des solutions existent.

2. La congruence équivaut à \[7x\equiv4\pmod{15}.\]

3. Comme \(7\times13=91\equiv1\pmod{15}\), \[x\equiv4\times13\equiv\boxed7\pmod{15}.\]

4. Les deux classes modulo \(30\) correspondant à \(x\equiv7\pmod{15}\) sont \[\boxed{x\equiv7\text{ ou }22\pmod{30}}.\]

Conclusion : lorsque le coefficient et le module ne sont pas premiers entre eux, il faut d'abord examiner leur PGCD.

1. \[2A-3B=2(6n+5)-3(4n+3)=\boxed1.\]

2. Tout diviseur commun de \(A\) et \(B\) divise \(1\), donc \[\boxed{\operatorname{PGCD}(A,B)=1}.\]

3. Modulo \(B\), la relation donne \(2A\equiv1\pmod B\). Ainsi \(\boxed2\) est un inverse de \(A\) modulo \(B\).

4. Puisque \(A\mid Bk\) et \(\operatorname{PGCD}(A,B)=1\), le théorème de Gauss donne \(\boxed{A\mid k}\).

Conclusion : une combinaison linéaire constante est un outil puissant pour étudier un PGCD dépendant d'un paramètre.

1. L'équation est \[\boxed{23x+17y=800}.\]

2. Modulo \(17\), \(6x\equiv1\pmod{17}\). Comme \(6^{-1}\equiv3\), \(x\equiv3\pmod{17}\). Ainsi \[x=3+17k,\qquad y=43-23k,\qquad k\in\mathbb Z.\]

3. Les conditions \(x>0\), \(y>0\) donnent \(k=0\) ou \(k=1\). Donc \[\boxed{(x,y)=(3,43)\text{ ou }(20,20)}.\]

4. Les nombres totaux de billets sont respectivement \(\boxed{46}\) et \(\boxed{40}\).

Conclusion : une contrainte concrète peut se ramener à une équation linéaire dans \(\mathbb Z\).

1. Si \(1009\) était composé, il posséderait un facteur premier inférieur ou égal à \(\sqrt{1009}\).

2. Comme \(31<\sqrt{1009}<32\), il suffit de tester \[\boxed{2,3,5,7,11,13,17,19,23,29,31}.\]

3. Aucun de ces nombres ne divise \(1009\). Donc \(\boxed{1009\text{ est premier}}\).

4. Pour \(1\le a<1009\), le seul diviseur commun possible de \(a\) et \(1009\) est \(1\). Ainsi \(\boxed{\operatorname{PGCD}(a,1009)=1}\).

Conclusion : pour tester la primalité d'un entier, il suffit d'examiner les diviseurs premiers jusqu'à sa racine carrée.

1. Comme \(d_n\) divise \(2n+1\) et \(n+3\), il divise \[2(n+3)-(2n+1)=5.\] Donc \(\boxed{d_n\mid5}\).

2. Ainsi \(\boxed{d_n\in\{1,5\}}\).

3. On a \(5\mid n+3\iff n\equiv2\pmod5\). Pour cette classe, \(2n+1\equiv5\equiv0\pmod5\). Donc \(d_n=5\iff n\equiv2\pmod5\).

4. \[\boxed{d_n=\begin{cases}5&\text{si }n\equiv2\pmod5,\\1&\text{sinon.}\end{cases}}\]

Conclusion : un PGCD paramétré se réduit souvent à un petit entier grâce à une combinaison linéaire.

1. L'algorithme d'Euclide donne \(\boxed{\operatorname{PGCD}(527,221)=17}\).

2. Une remontée fournit \[\boxed{17=-5\times527+12\times221}.\]

3. Une solution particulière est donc \(\boxed{(x_0,y_0)=(-5,12)}\).

4. Après division par \(17\), on a \(31x+13y=1\). Toutes les solutions sont \[\boxed{x=-5+13k,\qquad y=12-31k,\qquad k\in\mathbb Z}.\]

Conclusion : l'existence puis la paramétrisation des solutions reposent sur le PGCD et Bézout.

1. \(\operatorname{PGCD}(84,66)=6\) et \(6\mid1800\), donc l'équation possède des solutions entières.

2. On obtient \(14x+11y=300\). Modulo \(11\), \(3x\equiv3\), donc \(x\equiv1\pmod{11}\). Le couple \(\boxed{(1,26)}\) est une solution particulière.

3. Toutes les solutions sont \[\boxed{x=1+11k,\qquad y=26-14k,\qquad k\in\mathbb Z}.\]

4. Les inégalités imposent \(k=0\) ou \(k=1\). Ainsi \[\boxed{(x,y)=(1,26)\text{ ou }(12,12)}.\]

Conclusion : après la résolution dans \(\mathbb Z\), les contraintes du problème sélectionnent les couples admissibles.

1. Par Bézout, il existe \(u,v\in\mathbb Z\) tels que \(au+bv=1\). En multipliant par \(c\), \[acu+bcv=c.\] Or \(a\mid acu\) et, puisque \(a\mid bc\), \(a\mid bcv\). Donc \(\boxed{a\mid c}\) : c'est le théorème de Gauss.

2. \(\operatorname{PGCD}(12,35)=1\). Ainsi \(35\mid12n\) implique \(\boxed{35\mid n}\).

3. \(12n\equiv0\pmod{35}\iff35\mid12n\iff35\mid n\). Donc \[\boxed{n\equiv0\pmod{35}}.\]

4. Si \(p\mid x^2=x\times x\) et si \(p\nmid x\), alors \(\operatorname{PGCD}(p,x)=1\) ; Gauss imposerait \(p\mid x\), contradiction. Ainsi \(\boxed{p\mid x}\).

Conclusion : Gauss est une conséquence directe de Bézout et intervient constamment en arithmétique.

1. Écrivons \(x=2+5k\). La condition modulo \(7\) donne \(5k\equiv1\pmod7\), donc \(k\equiv3\pmod7\).

2. On obtient \(x=2+5(3+7s)=17+35s\), soit \[\boxed{x\equiv17\pmod{35}}.\]

3. Avec \(x=17+35t\), la condition modulo \(9\) devient \(8+8t\equiv4\), donc \(8t\equiv5\). Comme \(8^{-1}\equiv8\pmod9\), \(t\equiv4\pmod9\).

4. \[x=17+35(4+9q)=157+315q.\] Ainsi \[\boxed{x\equiv157\pmod{315}}.\]

Conclusion : on peut résoudre un système de congruences successivement, sans invoquer directement une formule générale.

1. \[3^{10}=59049\equiv\boxed{49}\pmod{100}.\]

2. \[3^{20}\equiv49^2=2401\equiv\boxed1\pmod{100}.\]

3. \(2026=20\times101+6\), donc \[3^{2026}\equiv3^6\pmod{100}.\]

4. \(3^6=729\equiv29\pmod{100}\). Les deux derniers chiffres sont donc \(\boxed{29}\).

Conclusion : une puissance énorme peut être réduite à un petit exposant grâce à une période modulo \(100\).

1. Comme \(29\) est premier et \(29\nmid5\), \[\boxed{5^{28}\equiv1\pmod{29}}.\]

2. \(2026=28\times72+10\), donc \(5^{2026}\equiv5^{10}\pmod{29}\). Par carrés successifs, \(5^2\equiv25\equiv-4\), \(5^4\equiv16\), \(5^8\equiv24\), puis \(5^{10}\equiv24\times25=600\equiv20\pmod{29}\). Ainsi \(\boxed{5^{2026}\equiv20\pmod{29}}\).

3. \(12\times17=204=7\times29+1\), donc \(\boxed{17}\) est un inverse de \(12\) modulo \(29\).

4. \[x\equiv7\times17=119\equiv\boxed3\pmod{29}.\]

Conclusion : Fermat réduit les exposants, tandis que Bézout ou un calcul direct fournit les inverses modulaires.

1. \(p\) est impair. Si \(p=2k+1\), alors \[p^2-1=4k(k+1).\] L'un des deux entiers \(k,k+1\) est pair, donc \(8\mid p^2-1\), soit \(\boxed{p^2\equiv1\pmod8}\).

2. Comme \(p\not\equiv0\pmod3\), on a \(p\equiv\pm1\pmod3\), donc \(\boxed{p^2\equiv1\pmod3}\).

3. Ainsi \(3\mid p^2-1\) et \(8\mid p^2-1\). Comme \(\operatorname{PGCD}(3,8)=1\), \[\boxed{24\mid p^2-1}.\]

4. Puisque \(p^2-1=(p-1)(p+1)\), on obtient \[\boxed{24\mid(p-1)(p+1)}.\]

Conclusion : les congruences modulo \(3\) et \(8\) se combinent pour produire une divisibilité modulo \(24\).

1. Si \(n=kd\), alors \[10^n-1=(10^d)^k-1=(10^d-1)(1+10^d+\cdots+10^{(k-1)d}).\] Après division par \(9\), on obtient \(\boxed{R_d\mid R_n}\).

2. \(R_3=111=3\times37\), donc \(\boxed{37\mid R_3}\).

3. Comme \(\operatorname{PGCD}(9,37)=1\), \[37\mid R_n\iff37\mid(10^n-1)\iff\boxed{10^n\equiv1\pmod{37}}.\]

4. \(10^3=1000\equiv1\pmod{37}\), tandis que \(10\not\equiv1\) et \(10^2\not\equiv1\). Donc \[\boxed{37\mid R_n\iff3\mid n}.\]

Conclusion : les propriétés des répunités se traduisent naturellement par des congruences sur les puissances de \(10\).

1. \[\boxed{75600=2^4\times3^3\times5^2\times7}.\]

2. Le nombre de diviseurs est \[(4+1)(3+1)(2+1)(1+1)=\boxed{120}.\]

3. Le plus grand carré diviseur est \[2^4\times3^2\times5^2=\boxed{3600}.\]

4. Les exposants impairs sont ceux de \(3\) et \(7\). Il faut multiplier par \(3\times7\), donc \(\boxed{m=21}\).

Conclusion : les exposants de la factorisation première codent directement les propriétés de carré parfait.

1. \[x^2\equiv1\pmod{35}\iff35\mid(x^2-1)= (x-1)(x+1).\]

2. Comme \(5\) et \(7\) sont premiers, \[x\equiv\pm1\pmod5,\qquad x\equiv\pm1\pmod7.\]

3. Les quatre combinaisons donnent \[\boxed{x\equiv1,6,29,34\pmod{35}}.\]

4. Si le module est un nombre premier \(p\), alors \(p\mid(x-1)(x+1)\) implique \(p\mid x-1\) ou \(p\mid x+1\). Ainsi \[\boxed{x\equiv\pm1\pmod p}.\] Le module composé \(35\) permet davantage de combinaisons.

Conclusion : le nombre de solutions de \(x^2\equiv1\) dépend fortement de la structure du module.

1. \(\operatorname{PGCD}(12,18)=6\), et \(5\equiv11\equiv5\pmod6\). Le système est donc compatible.

2. Avec \(x=5+12k\), \[5+12k\equiv11\pmod{18}\iff12k\equiv6\pmod{18}.\]

3. En divisant par \(6\), \(2k\equiv1\pmod3\), donc \(k\equiv2\pmod3\). Ainsi \[x=5+12(2+3q)=29+36q,\] soit \(\boxed{x\equiv29\pmod{36}}\).

4. Pour l'autre système, il faudrait avoir \(4\equiv11\pmod6\), ce qui est faux. Il est donc \(\boxed{\text{incompatible}}\).

Conclusion : lorsque les modules ne sont pas premiers entre eux, la compatibilité des restes doit être vérifiée avant toute résolution.

1. \(\operatorname{PGCD}(5,26)=1\) et \(5\times21=105\equiv1\pmod{26}\). Donc \(\boxed{5^{-1}\equiv21\pmod{26}}\).

2. De \(y\equiv5x+8\), on tire \[x\equiv21(y-8)\pmod{26}.\] Ainsi \(\boxed{D(y)\equiv21(y-8)\pmod{26}}\).

3. Les images de \(12,0,19,7,18\) sont \(16,8,25,17,20\), soit les lettres \[\boxed{\text{QIZRU}}.\]

4. L'application de \(D\) à \(16,8,25,17,20\) redonne \(12,0,19,7,18\), donc \(\boxed{\text{MATHS}}\).

Conclusion : un chiffrement affine est réversible exactement lorsque son coefficient multiplicatif est inversible modulo \(26\).

1. \[\boxed{F_0=3,\quad F_1=5,\quad F_2=17,\quad F_3=257}.\]

2. L'identité est vraie pour \(n=1\). Si \(F_0\cdots F_{n-1}=F_n-2\), alors \[F_0\cdots F_n=(F_n-2)F_n=(2^{2^n}-1)(2^{2^n}+1)=2^{2^{n+1}}-1=F_{n+1}-2.\] Donc l'identité est démontrée par récurrence.

3. Pour \(m

4. Chaque \(F_n\) possède au moins un facteur premier, et ces facteurs sont distincts d'un indice à l'autre puisque les \(F_n\) sont deux à deux premiers entre eux. Il existe donc \(\boxed{\text{une infinité de nombres premiers}}\).

Conclusion : les nombres de Fermat donnent une élégante variante de la preuve de l'infinité des nombres premiers.

1. Si \(n=ab\), alors \[M_n=(2^a)^b-1=(2^a-1)\left(1+2^a+\cdots+2^{a(b-1)}\right).\] Les deux facteurs sont strictement supérieurs à \(1\), donc \(M_n\) est composé.

2. Par contraposée, si \(M_n\) est premier, \(n\) ne peut pas être composé. Donc \(\boxed{M_n\text{ premier}\Rightarrow n\text{ premier}}\).

3. \[M_{11}=2^{11}-1=2048-1=\boxed{2047}.\]

4. \[23\times89=2047.\] Ainsi \(11\) est premier mais \(M_{11}\) ne l'est pas. La réciproque \(n\) premier \(\Rightarrow M_n\) premier est donc \(\boxed{\text{fausse}}\).

Conclusion : la primalité de l'exposant est nécessaire, mais elle n'est pas suffisante pour obtenir un nombre de Mersenne premier.

1. Modulo \(B\), \(2^{30}\equiv1\), donc \[2^{84}-1=2^{60}2^{24}-1\equiv2^{24}-1\pmod B.\] L'algorithme d'Euclide donne alors \[\operatorname{PGCD}(A,B)=\operatorname{PGCD}(2^{24}-1,2^{30}-1).\]

2. De même, \(30=24+6\) conduit à \[\operatorname{PGCD}(2^{24}-1,2^{30}-1)=\operatorname{PGCD}(2^{24}-1,2^6-1).\]

3. Comme \(24=4\times6\), \[(2^6)^4-1\] est divisible par \(2^6-1\). Donc \(\boxed{2^6-1\mid2^{24}-1}\).

4. Le PGCD vaut donc \[2^6-1=63=\boxed{3^2\times7}.\]

Conclusion : l'algorithme d'Euclide peut être appliqué aux exposants sans développer les nombres gigantesques.

1. \[2^6=64\equiv-1\pmod{13},\qquad3^3=27\equiv1\pmod{13}.\]

2. Comme \(74=6\times12+2\), on a \(2^{74}\equiv(-1)^{12}2^2\equiv4\pmod{13}\). De plus \(74=3\times24+2\), donc \(3^{74}\equiv3^2\equiv9\pmod{13}\). Ainsi \(2^{74}+3^{74}\equiv4+9\equiv0\pmod{13}\), donc \(\boxed{13\mid2^{74}+3^{74}}\).

3. L'inverse de \(3\) est \(9\). En multipliant par \(3^{-n}\), \[2^n+3^n\equiv0\iff(2\times9)^n+1\equiv0\iff\boxed{5^n\equiv-1\pmod{13}}.\]

4. \(5^2=25\equiv-1\pmod{13}\) et \(5^4\equiv1\pmod{13}\). Donc \(5^n\equiv-1\) exactement lorsque \(n\equiv2\pmod4\). Ainsi \[\boxed{13\mid2^n+3^n\iff n\equiv2\pmod4}.\]

Conclusion : l'usage d'un inverse transforme une somme de deux puissances en l'étude d'un seul cycle multiplicatif.

1. Comme \(p\mid n^2+n+1\), l'identité \[n^3-1=(n-1)(n^2+n+1)\] donne \(\boxed{n^3\equiv1\pmod p}\).

2. Si \(n\equiv1\pmod p\), alors \(0\equiv n^2+n+1\equiv3\pmod p\), donc \(p=3\), contradiction. De plus \(p\nmid n\), sinon \(n^2+n+1\equiv1\pmod p\). Ainsi \(\boxed{n\not\equiv1\pmod p\text{ et }p\nmid n}\).

3. Fermat donne \(n^{p-1}\equiv1\pmod p\). Écrivons \(p-1=3q+r\) avec \(r\in\{0,1,2\}\). Puisque \(n^3\equiv1\), on a \(n^{p-1}\equiv n^r\). Si \(r=1\), on aurait \(n\equiv1\), impossible. Si \(r=2\), on aurait \(n^2\equiv1\), puis avec \(n^3\equiv1\), \(n\equiv1\), impossible. Donc \(r=0\), soit \(\boxed{3\mid p-1}\).

4. Ainsi \(\boxed{p\equiv1\pmod3}\). Pour \(n=10\), \(n^2+n+1=111=3\times37\), et \(37\equiv1\pmod3\), ce qui confirme le résultat.

Conclusion : une identité algébrique, combinée à Fermat, impose une forte contrainte sur les diviseurs premiers.

1. On trouve \[\boxed{1=-4\times17+3\times23}.\] Ainsi \(u=-4\), \(v=3\).

2. \[N=7\times23\times3+11\times17\times(-4)=483-748=-265.\] Modulo \(17\), \(N\equiv7\), et modulo \(23\), \(N\equiv11\).

3. Comme \(-265+391=126\), une solution est \(126\). Deux solutions diffèrent d'un multiple de \(17\) et de \(23\), donc d'un multiple de \(391\). Ainsi \[\boxed{n\equiv126\pmod{391}}.\]

4. Le plus petit entier naturel solution est \(\boxed{126}\).

Conclusion : Bézout fournit une construction explicite d'une solution d'un système à modules premiers entre eux.

1. \(\operatorname{PGCD}(5,28)=1\) et \[5\times17=85=3\times28+1.\] Donc \(\boxed{d=17}\).

2. Si \(m\neq0\), Fermat donne \(m^{28}\equiv1\pmod{29}\). Or \(5d=85=3\times28+1\), donc \[(m^5)^{17}=m^{85}=m(m^{28})^3\equiv m\pmod{29}.\] Pour \(m=0\), l'égalité est immédiate. Ainsi \(\boxed{D(c)=c^{17}\pmod{29}}\) inverse le chiffrement.

3. \[8^2\equiv6,\quad8^4\equiv7,\quad8^5\equiv8\times7=56\equiv\boxed{27}\pmod{29}.\] Le message chiffré est \(\boxed{c=27}\).

4. Par carrés successifs, \(27^2\equiv4\), \(27^4\equiv16\), \(27^8\equiv24\), \(27^{16}\equiv25\). Ainsi \[27^{17}\equiv25\times27=675\equiv\boxed8\pmod{29}.\] On retrouve bien le message initial.

Conclusion : cet exercice combine inverses modulo \(p-1\), petit théorème de Fermat et chiffrement par puissances.