Devoir surveillé : Divisibilité, PGCD, congruences, Bézout, Gauss et nombres premiers

1. a)$6\times (-14)=-84>-85$ et $6\times (-15)=-90⩽-85$. Donc $-85=6\times (-15)+5$ avec $0⩽5<6$ : le quotient vaut $-15$ et le reste $5$. (1 pt) (1)
2. b)$6\equiv -1[7]$, donc $6^{41}\equiv (-1{)}^{41}=-1[7]$, car $41$ est impair. Or $-1\equiv 6[7]$ : le reste vaut $6$. (1 pt : 0,5 pour $6\equiv -1$, 0,5 pour la conclusion) (1)
3. c)$546=2\times 234+78$ ; $234=3\times 78+0$. Le dernier reste non nul est $78$ : $\text{pgcd}(546;234)=78$. Contrôle : $546=78\times 7$ et $234=78\times 3$. (1 pt) (1)
4. d)$1400=14\times 100=(2\times 7)\times (2^2\times 5^2)=2^3\times 5^2\times 7$. Nombre de diviseurs positifs : $(3+1)(2+1)(1+1)=4\times 3\times 2=24$. (1 pt : 0,5 pour la décomposition, 0,5 pour le nombre de diviseurs) (1)
5. e)$17\times 5-12\times 7=85-84=1$, soit $17u+12v=1$ avec $u=5$ et $v=-7$ entiers. D'après le théorème de Bézout, $17$ et $12$ sont premiers entre eux. (1 pt) (1)

Méthode — Un reste vérifie toujours $0⩽r<b$ : pour un dividende négatif, on descend d'un multiple du diviseur au lieu de changer les signes.

1. a)Par compatibilité des congruences avec la somme et le produit, $A$ a le même reste modulo $3$ que $r^2+r+1$, où $r$ est le reste de $n$. Pour $r=0$ : $1$ ; pour $r=1$ : $3\equiv 0$ ; pour $r=2$ : $4+2+1=7\equiv 1[3]$.

   $n$ modulo $3$	$0$	$1$	$2$
   $A$ modulo $3$	$1$	$0$	$1$

   (1 pt) (1)
2. b)D'après le tableau, $A\equiv 0[3]$ si et seulement si $n\equiv 1[3]$ : $A$ est divisible par $3$ exactement pour les entiers $n=3k+1$, $k\in \mathbb{Z}$. (1 pt) (1)
3. c)$A=(3k+1{)}^2+(3k+1)+1=9k^2+6k+1+3k+2=9k^2+9k+3=3(3k^2+3k+1)$. Or $3k^2+3k+1\equiv 1[3]$ n'est pas divisible par $3$, donc $9$ ne divise pas $A$. Si $n\not\equiv 1[3]$, $3$ ne divise même pas $A$. Ainsi $A$ n'est divisible par $9$ pour aucun entier $n$. (1 pt : 0,5 pour le développement, 0,5 pour la conclusion) (1)
4. d)Pour $n=4$ : $A=16+4+1=21=3\times 7$, qui n'est pas premier. Ce contre-exemple était prévisible : $4=3\times 1+1$, donc $3$ divise $A$ d'après b), et $A>3$. (1 pt) (1)

Erreur fréquente — Des exemples, même nombreux, ne prouvent pas une propriété « pour tout $n$ » ; un seul contre-exemple suffit en revanche à la réfuter.

1. a)$13=1\times 8+5$ ; $8=1\times 5+3$ ; $5=1\times 3+2$ ; $3=1\times 2+1$ ; $2=2\times 1+0$. Le dernier reste non nul vaut $1$ : $\text{pgcd}(13;8)=1$. (1 pt) (1)
2. b)On remonte l'algorithme : $1=3-2=3-(5-3)=2\times 3-5=2(8-5)-5=2\times 8-3\times 5$ $=2\times 8-3(13-8)=5\times 8-3\times 13$. Donc $(u;v)=(-3;5)$. Vérification : $-39+40=1$. (1 pt) (1)
3. c)En multipliant $13\times (-3)+8\times 5=1$ par $5$ : $13\times (-15)+8\times 25=5$. Le couple $(-15;25)$ est solution ; contrôle : $-195+200=5$. (1 pt) (1)
4. d)Si $(x;y)$ est solution, en soustrayant $13\times (-15)+8\times 25=5$ : $13(x+15)=8(25-y)$. Donc $8$ divise $13(x+15)$ ; comme $\text{pgcd}(8;13)=1$, le théorème de Gauss donne : $8$ divise $x+15$, soit $x=-15+8k$, $k\in \mathbb{Z}$. En reportant, $13\times 8k=8(25-y)$, d'où $y=25-13k$. Réciproquement, $13(-15+8k)+8(25-13k)=-195+200=5$. Les solutions sont les couples $(-15+8k;25-13k)$, $k\in \mathbb{Z}$. (1 pt : 0,5 pour Gauss, 0,5 pour la réciproque et l'ensemble des solutions) (1)
5. e)$13x\equiv 5[8]$ équivaut à l'existence d'un entier $y$ tel que $13x-5=-8y$, c'est-à-dire $13x+8y=5$. D'après d), $x=-15+8k$ : les solutions sont les entiers $x\equiv -15\equiv 1[8]$. Contrôle : $13\times 1=13=8+5$. (1 pt) (1)

Astuce — Une équation $ax+by=c$ se lit aussi comme une congruence : modulo $b$, elle devient $ax\equiv c[b]$. Ses solutions en $x$ sont donc exactement une classe modulo $b$ quand $a$ et $b$ sont premiers entre eux.

1. a)${15}^2=225⩽227<256={16}^2$ : il suffit de tester les nombres premiers $p$ tels que $p^2⩽227$, soit $2$, $3$, $5$, $7$, $11$ et $13$. $227$ est impair ; $2+2+7=11$ n'est pas un multiple de $3$ ; il ne se termine ni par $0$ ni par $5$ ; $7\times 32=224$ (reste $3$), $11\times 20=220$ (reste $7$), $13\times 17=221$ (reste $6$). Aucun ne divise $227$ : il est premier. (1,5 pt : 0,5 pour la borne, 1 pour les divisions) (1,5)
2. b)$11$ est premier et ne divise pas $3$ : d'après le petit théorème de Fermat, $3^{10}\equiv 1[11]$. Or $503=10\times 50+3$, donc $3^{503}=(3^{10}{)}^{50}\times 3^3\equiv 1\times 27[11]$, et $27=2\times 11+5$. Le reste vaut $5$. (1,5 pt : 0,5 pour Fermat avec ses hypothèses, 0,5 pour la division de l'exposant, 0,5 pour le reste) (1,5)
3. c)$1260=2^2\times 315=2^2\times 3^2\times 35=2^2\times 3^2\times 5\times 7$ ; $1188=2^2\times 297=2^2\times 3^3\times 11$. On garde les facteurs premiers communs avec le plus petit exposant : $\text{pgcd}(1260;1188)=2^2\times 3^2=36$. (1,5 pt : 1 pour les décompositions, 0,5 pour le PGCD) (1,5)
4. d)$1188=36\times 33$ et $1260=36\times 35$, donc ${\displaystyle \frac{1188}{1260}}={\displaystyle \frac{33}{35}}$. Comme on a divisé par le PGCD, $33$ et $35$ sont premiers entre eux ; on le voit aussi sur $33=3\times 11$ et $35=5\times 7$, sans facteur premier commun. (1,5 pt) (1,5)

Piège — Pour tester si $n$ est premier, on s'arrête aux nombres premiers $p$ tels que $p^2⩽n$ : s'arrêter avant laisse passer des entiers composés, aller au-delà est inutile.

1. a)$2^3=8\equiv -1[9]$, donc $2^6\equiv 1[9]$. Or $100=6\times 16+4$, donc $2^{100}=(2^6{)}^{16}\times 2^4\equiv 16\equiv 7[9]$. Le reste vaut $7$. (1 pt) (1)
2. b)$7\times 13=91=3\times 30+1$ : $13$ est un inverse de $7$ modulo $30$. En multipliant les deux membres par $13$ : $x\equiv 52\equiv 22[30]$ ; réciproquement, $7\times 22=154=5\times 30+4$. Les solutions sont les entiers $22+30k$, $k\in \mathbb{Z}$. (1 pt : 0,5 pour l'inverse, 0,5 pour la résolution) (1)
3. c)Facteurs premiers communs avec le plus petit exposant : $\text{pgcd}(a;b)=2^3\times 3^2=72$. Les diviseurs communs sont les diviseurs du PGCD ; $72=2^3\times 3^2$ en a $(3+1)(2+1)=12$. (1 pt : 0,5 + 0,5) (1)
4. d)Cet entier vaut $N=1000a+100b+10b+a$. Comme $10\equiv -1[11]$, par compatibilité des congruences avec la somme, le produit et les puissances : $N\equiv a\times (-1{)}^3+b\times (-1{)}^2+b\times (-1)+a$ $=-a+b-b+a=0[11]$. On peut aussi factoriser : $N=1001a+110b=11(91a+10b)$, avec $91a+10b$ entier. Donc $11$ divise $N$ ; par exemple $3773=11\times 343$. (1 pt) (1)

Méthode — Pour une grande puissance, on cherche une puissance de la base congrue à $1$ ou à $-1$, puis on divise l'exposant : on ne calcule jamais la puissance elle-même.

1. a)Vraie. $12=2^2\times 3$ : $2$ et $3$ divisent $n^2=n\times n$. Comme ils sont premiers, le lemme d'Euclide donne : $2$ divise $n$ et $3$ divise $n$. $2$ et $3$ étant premiers entre eux, le corollaire du théorème de Gauss donne : $6$ divise $n$. (1 pt : 0,5 pour le lemme d'Euclide, 0,5 pour le corollaire) (1)
2. b)Fausse. $4$ divise $2^2=4$, mais $4$ ne divise pas $2$. Le lemme d'Euclide, utilisé en a), ne s'applique qu'à un diviseur premier : si $p$ premier divise $b\times b$, alors $p$ divise $b$. (1 pt) (1)
3. c)Vraie. $p$ est impair : $p=2k+1$ et $p^2-1=4k(k+1)$ ; l'un des entiers consécutifs $k$ et $k+1$ est pair, donc $8$ divise $p^2-1$. De plus $3$ ne divise pas $p$ (premier différent de $3$), donc $p\equiv 1$ ou $p\equiv 2\equiv -1[3]$, et dans les deux cas $p^2\equiv 1[3]$ : $3$ divise $p^2-1$. Comme $3$ et $8$ sont premiers entre eux ($3\times 3-8=1$), le corollaire du théorème de Gauss donne : $24$ divise $p^2-1$. (1 pt : 0,5 pour $8$ et $3$, 0,5 pour le corollaire) (1)
4. d)Fausse. $4^2=16=15+1$, donc $4^2\equiv 1[15]$ ; pourtant $4\not\equiv 1[15]$ et $4\not\equiv -1\equiv 14[15]$. L'affirmation serait vraie modulo un nombre premier $p$ : $p$ diviserait $x^2-1=(x-1)(x+1)$, donc $x-1$ ou $x+1$ d'après le lemme d'Euclide ; mais $15=3\times 5$ n'est pas premier. (1 pt) (1)

Piège — Le corollaire de Gauss exige deux diviseurs premiers entre eux : c'est parce que $\text{pgcd}(3;8)=1$ qu'on passe de « $3$ et $8$ divisent » à « $24$ divise ».

1. a)E : $11\times 4+8=52=2\times 26+0$, donc $y=0$ : E est chiffrée en A. T : $11\times 19+8=217=8\times 26+9$, donc $y=9$ : T est chiffrée en J. (1 pt : 0,5 par lettre) (1)
2. b)$26=2\times 11+4$ ; $11=2\times 4+3$ ; $4=1\times 3+1$. Remontée : $1=4-3=4-(11-2\times 4)=3\times 4-11=3(26-2\times 11)-11=3\times 26-7\times 11$. Donc $11\times (-7)\equiv 1[26]$, et $-7\equiv 19[26]$ : l'inverse est $19$. Contrôle : $11\times 19=209=8\times 26+1$. (1 pt) (1)
3. c)Si $y\equiv 11x+8[26]$, en multipliant par $19$ : $19y\equiv 209x+152[26]$. Or $209\equiv 1$ et $152=5\times 26+22\equiv 22[26]$, donc $19y\equiv x+22$, soit $x\equiv 19y-22\equiv 19y+4[26]$. Réciproquement, si $x\equiv 19y+4[26]$, en multipliant par $11$ : $11x\equiv 209y+44\equiv y+18[26]$, donc $y\equiv 11x-18\equiv 11x+8[26]$. (1 pt : 0,5 par implication) (1)
4. d)On calcule le reste de $19y+4$ modulo $26$. A ($y=0$) : $4$, soit E. U ($y=20$) : $384=14\times 26+20$, soit U. Z ($y=25$) : $479=18\times 26+11$, soit L. N ($y=13$) : $251=9\times 26+17$, soit R. Le mot est EULER. (1 pt) (1)
5. e)On cherche les rangs $x$ tels que $11x+8\equiv x[26]$, soit $10x\equiv -8\equiv 18[26]$. Il existe alors un entier $k$ tel que $10x-18=26k$ ; en divisant par $2$ : $5x-9=13k$, donc l'équation équivaut à $5x\equiv 9[13]$. Comme $5\times 8=40=3\times 13+1$, on multiplie par $8$ : $x\equiv 72\equiv 7[13]$. Entre $0$ et $25$ : $x=7$ ou $x=20$, soit H et U. Contrôle : $11\times 7+8=85=3\times 26+7$ et $11\times 20+8=228=8\times 26+20$. (1 pt : 0,5 pour la réduction modulo $13$, 0,5 pour les deux lettres) (1)

Erreur fréquente — Pour déchiffrer, on ne « divise » pas par $11$ : on multiplie par l'inverse de $11$ modulo $26$, qui n'existe que parce que $\text{pgcd}(11;26)=1$.

1. a)La position finale vaut $29x-12y$ (en cm), donc $29x-12y=2$. Algorithme d'Euclide : $29=2\times 12+5$ ; $12=2\times 5+2$ ; $5=2\times 2+1$. Remontée : $1=5-2\times 2=5-2(12-2\times 5)=5\times 5-2\times 12$ $=5(29-2\times 12)-2\times 12=5\times 29-12\times 12$. En multipliant par $2$ : $29\times 10-12\times 24=2$ ; le couple $(10;24)$ est solution. Contrôle : $290-288=2$. (1 pt : 0,5 pour l'équation et l'algorithme, 0,5 pour la solution) (1)
2. b)Si $(x;y)$ est solution, en soustrayant $29\times 10-12\times 24=2$ : $29(x-10)=12(y-24)$. Donc $12$ divise $29(x-10)$ ; comme $\text{pgcd}(12;29)=1$ (dernier reste non nul de l'algorithme de a), le théorème de Gauss donne : $12$ divise $x-10$, soit $x=10+12k$, $k\in \mathbb{Z}$. En reportant, $29\times 12k=12(y-24)$, d'où $y=24+29k$. Réciproquement, $29(10+12k)-12(24+29k)=290-288=2$. Les solutions sont les couples $(10+12k;24+29k)$, $k\in \mathbb{Z}$. (1 pt : 0,5 pour Gauss, 0,5 pour la réciproque et l'ensemble des solutions) (1)
3. c)Les nombres de pas sont des entiers naturels : $10+12k⩾0$ et $24+29k⩾0$ imposent $k⩾0$ ($k=-1$ donne $x=-2$). Le nombre total de pas vaut $x+y=34+41k$. Pour $75$ pas : $41k=41$, donc $k=1$, soit $22$ pas en avant et $53$ en arrière ; contrôle : $29\times 22-12\times 53=638-636=2$. Pour $100$ pas : $41k=66$, impossible car $41$ ne divise pas $66$. Le robot peut s'arrêter au point $2$ après $75$ pas, mais pas après $100$. (1 pt : 0,5 par cas) (1)

Méthode — Les contraintes de l'énoncé (entiers naturels, nombre total de pas imposé) deviennent des conditions sur le paramètre $k$ de la solution générale : on résout d'abord dans ${\mathbb{Z}}^2$, on trie ensuite.

1. a)$2\equiv -1[3]$, donc $2^n\equiv (-1{)}^n[3]$. Si $n$ est pair, $2^n\equiv 1$ et $M_n\equiv 0[3]$ ; si $n$ est impair, $2^n\equiv -1$ et $M_n\equiv -2\equiv 1[3]$. Donc $3$ divise $M_n$ si et seulement si $n$ est pair. (1 pt) (1)
2. b)$2^1=2$, $2^2=4$, $2^3=8\equiv 1[7]$ : le cycle a pour longueur $3$. Si $n=3q+r$ avec $r\in \{0;1;2\}$, $2^n=(2^3{)}^q\times 2^r\equiv 2^r[7]$, qui vaut $1$, $2$ ou $4$. Donc $M_n\equiv 0[7]$ si et seulement si $r=0$ : $7$ divise $M_n$ exactement quand $n$ est un multiple de $3$. (1 pt) (1)
3. c)$2^r\equiv 1[M_r]$, donc $2^n=(2^r{)}^s\equiv 1^s=1[M_r]$ : $M_r$ divise $M_n$. De plus $2⩽r<n$ donne $3⩽M_r<M_n$ : si $n$ n'est pas premier, $M_n$ a un diviseur strictement compris entre $1$ et lui-même, il n'est pas premier. Par contraposée, si $M_n$ est premier, $n$ est premier. (1 pt : 0,5 pour la divisibilité, 0,5 pour la contraposée) (1)
4. d)$2^5=32\equiv 9[23]$, donc $2^{10}\equiv 81=3\times 23+12\equiv 12$ et $2^{11}\equiv 24\equiv 1[23]$. Ainsi $23$ divise $M_{11}$, et $M_{11}\ne 23$ (car $2^{11}>24$) : $M_{11}$ n'est pas premier alors que $11$ l'est. La réciproque est fausse ($M_{11}=2047=23\times 89$). (1 pt : 0,5 pour la congruence, 0,5 pour la conclusion) (1)

Astuce — De $2^r\equiv 1[2^r-1]$, on tire $2^{rs}\equiv 1$ : une congruence modulo une expression fournit un diviseur sans aucune division à poser.

1. a)$2026=7\times 289+3$, donc $2{026}^{2026}\equiv 3^{2026}[7]$. $7$ est premier et ne divise pas $3$ : $3^6\equiv 1[7]$ (petit théorème de Fermat). Or $2026=6\times 337+4$, donc $3^{2026}\equiv 3^4=81=11\times 7+4[7]$. Le reste vaut $4$. (1 pt) (1)
2. b)${12}^{10}=(2^2\times 3{)}^{10}=2^{20}\times 3^{10}$ : il a $(20+1)(10+1)=231$ diviseurs positifs, de la forme $2^{\alpha }\times 3^{\beta }$ avec $0⩽\alpha ⩽20$ et $0⩽\beta ⩽10$. Un tel diviseur est un carré si et seulement si $\alpha$ et $\beta$ sont pairs : $11$ choix pour $\alpha$ ($0,2,\dots ,20$) et $6$ pour $\beta$ ($0,2,\dots ,10$), soit $66$ carrés. (1 pt : 0,5 + 0,5) (1)
3. c)$65=2\times 26+13$ et $26=2\times 13$ : $\text{pgcd}(26;65)=13$, qui divise $39$. $26x-39=65k$ équivaut, en divisant par $13$, à $2x-3=5k$ : l'équation équivaut à $2x\equiv 3[5]$. Comme $2\times 3=6\equiv 1[5]$, on multiplie par $3$ : $x\equiv 9\equiv 4[5]$. Les solutions sont les entiers $4+5k$, $k\in \mathbb{Z}$ (treize classes modulo $65$). Contrôle : $26\times 4=104=65+39$. (1 pt) (1)

Méthode — Avant d'appliquer le petit théorème de Fermat, on réduit la base modulo $p$ ; l'exposant, lui, se réduit modulo $p-1$.

1. a)Comme $\text{pgcd}(a;b)=1$, le théorème de Bézout donne des entiers $u$ et $v$ tels que $au+bv=1$. En multipliant par $c$ : $acu+bcv=c$. Or $a$ divise $acu$, et $a$ divise $bc$ donc $bcv$ : $a$ divise la somme $c$. (1 pt) (1)
2. b)Soit $d⩾1$ un diviseur commun. Il divise la combinaison $(n+1)!+1-(n+1)(n!+1)=(n+1)!+1-(n+1)!-(n+1)=-n$, donc $d$ divise $n$. Or $n$ divise $n!=1\times 2\times \dots \times n$, donc $d$ divise $n!$ ; divisant aussi $n!+1$, il divise la différence $1$. Ainsi $d=1$ : les deux entiers sont premiers entre eux. (1 pt : 0,5 pour la combinaison, 0,5 pour la conclusion) (1)
3. c)Pour $1⩽k⩽p-1$, $p$ ne divise pas $k$ ; comme $p$ est premier, le petit théorème de Fermat donne $k^{p-1}\equiv 1[p]$. En ajoutant ces $p-1$ congruences : la somme est congrue à $p-1\equiv -1[p]$. (1 pt) (1)
4. d)$(n^2+2{)}^2-4n^2=n^4+4n^2+4-4n^2=n^4+4$, donc $n^4+4=(n^2+2-2n)(n^2+2+2n)$ $=(n^2-2n+2)(n^2+2n+2)$. Pour $n⩾2$ : $n^2-2n+2=(n-1{)}^2+1⩾2$, et $n^2+2n+2>n^2-2n+2⩾2$. Ainsi $n^4+4$ est le produit de deux entiers supérieurs ou égaux à $2$ : il admet un diviseur strictement compris entre $1$ et lui-même, il n'est pas premier. Exemple : $3^4+4=85=5\times 17$. Pour $n=1$, en revanche, $1^4+4=5$ est premier. (1 pt : 0,5 pour la factorisation, 0,5 pour les deux facteurs supérieurs ou égaux à $2$) (1)

Erreur fréquente — Le théorème de Gauss et le petit théorème de Fermat ont une hypothèse (premiers entre eux ; $p$ premier ne divisant pas l'entier) : on l'écrit et on la justifie avant de conclure, sinon la preuve ne vaut rien.

1. a)$40=13\times 3+1$, donc $3\times (-13)+40\times 1=1$ : d'après le théorème de Bézout, $\text{pgcd}(3;40)=1$, et $3\times (-13)\equiv 1[40]$. Comme $-13\equiv 27[40]$, $d=27$. Contrôle : $3\times 27=81=2\times 40+1$. (1 pt) (1)
2. b)Si $5$ divise $m$, les deux membres sont congrus à $0$. Sinon, $5$ étant premier, le petit théorème de Fermat donne $m^4\equiv 1[5]$ ; comme $81=4\times 20+1$, $m^{81}=(m^4{)}^{20}\times m\equiv m[5]$. (1 pt : 0,5 par cas) (1)
3. c)Si $11$ divise $m$, c'est clair. Sinon $m^{10}\equiv 1[11]$ (Fermat, $11$ premier) et $81=10\times 8+1$, donc $m^{81}\equiv m[11]$. Ainsi $5$ et $11$ divisent $m^{81}-m$ ; ce sont deux nombres premiers distincts, donc premiers entre eux, et le corollaire du théorème de Gauss donne : $55$ divise $m^{81}-m$. (1 pt : 0,5 pour le cas modulo $11$, 0,5 pour le recollement) (1)
4. d)$m^3\equiv 13[55]$ ; en élevant à la puissance $27$ : $m^{81}\equiv {13}^{27}[55]$. D'après c), $m^{81}\equiv m[55]$, donc $m\equiv {13}^{27}[55]$. Comme $0⩽m⩽54$, $m$ est le reste de ${13}^{27}$ modulo $55$ : le message est unique. (1 pt) (1)
5. e)Modulo $5$ : $13\equiv 3$, $3^4\equiv 1$ et $27=4\times 6+3$, donc ${13}^{27}\equiv 3^3=27\equiv 2[5]$. Modulo $11$ : $13\equiv 2$, $2^{10}\equiv 1$ et $27=10\times 2+7$, donc ${13}^{27}\equiv 2^7=128=11\times 11+7\equiv 7[11]$. On cherche $m$ entre $0$ et $54$ avec $m\equiv 7[11]$, parmi $7$, $18$, $29$, $40$, $51$ : seul $7$ vérifie $m\equiv 2[5]$. Donc $m=7$. Vérification : $7^3=343=6\times 55+13$. (1 pt : 0,5 pour les deux restes, 0,5 pour $m$) (1)

Astuce — Pour un module $pq$ produit de deux nombres premiers distincts, on travaille séparément modulo $p$ et modulo $q$ (Fermat), puis le corollaire de Gauss recolle les deux congruences modulo $pq$.

1. a)Le bus A passe aux instants $t=12+35x$ et le bus B aux instants $t=5+24y$, avec $x$ et $y$ entiers naturels (nombre d'intervalles écoulés depuis le premier passage). Ils passent ensemble si et seulement si un même $t$ s'écrit des deux façons : $12+35x=5+24y$, c'est-à-dire $24y-35x=7$. (1 pt) (1)
2. b)$35=1\times 24+11$ ; $24=2\times 11+2$ ; $11=5\times 2+1$. Remontée : $1=11-5\times 2=11-5(24-2\times 11)=11\times 11-5\times 24=11(35-24)-5\times 24=11\times 35-16\times 24$. Donc $24\times (-16)-35\times (-11)=1$, puis, en multipliant par $7$ : $24\times (-112)-35\times (-77)=7$. Si $(x;y)$ est solution, $24(y+112)=35(x+77)$ ; $35$ divise $24(y+112)$ et $\text{pgcd}(35;24)=1$, donc par Gauss $y=-112+35k$, puis $x=-77+24k$, $k\in \mathbb{Z}$. Réciproquement, $24(-112+35k)-35(-77+24k)=-2688+2695=7$. (1 pt : 0,5 pour la solution particulière, 0,5 pour Gauss et la réciproque) (1)
3. c)$x⩾0$ impose $24k⩾77$, soit $k⩾4$ ; $y⩾0$ impose $35k⩾112$, soit $k⩾4$. Pour $k=4$ : $x=19$, $y=28$ et $t=12+35\times 19=677=5+24\times 28$. Or $677$ min $=11$ h $17$ min : premier passage commun à 18 h 17. Plus généralement $t=12+35(-77+24k)=840k-2683$ : deux rencontres sont séparées de $840$ min, soit $14$ h. La suivante tomberait à $t=1517$, au-delà de $t=960$ (23 h) : une seule rencontre par jour. (1 pt : 0,5 pour 18 h 17, 0,5 pour l'unicité) (1)
4. d)Ils passeraient ensemble s'il existait des entiers $x$ et $z$ tels que $12+35x=3+21z$, soit $21z-35x=9$. Or $7$ divise $21$ et $35$, donc $21z-35x$ ; il diviserait $9$, ce qui est faux. Les bus A et C ne se croisent jamais à cet arrêt. (1 pt) (1)

Piège — Le pas des solutions de $24y-35x=7$ est $35$ pour $y$ et $24$ pour $x$ ; en temps, deux rencontres sont donc séparées de $35\times 24=840$ minutes, et non de $35$ ou de $24$ minutes.

1. a)$x^2-y^2=(x-y)(x+y)=2025$. Comme $x+y⩾0$ et que le produit est strictement positif, $x+y>0$, puis $x-y>0$. Ce sont donc deux diviseurs positifs de $2025$ de produit $2025$, et $x-y⩽x+y$ car $y⩾0$. (1 pt) (1)
2. b)$2025=81\times 25=3^4\times 5^2$. On pose $\delta =x-y$ et $D=x+y$, avec $\delta D=2025$ et $\delta ⩽D$, donc $\delta ⩽45$ : $\delta \in \{1;3;5;9;15;25;27;45\}$. Les deux sont impairs, donc $x={\displaystyle \frac{\delta +D}{2}}$ et $y={\displaystyle \frac{D-\delta }{2}}$ sont entiers ; réciproquement, chaque couple vérifie $(x-y)(x+y)=\delta D=2025$. Solutions : $(1013;1012)$, $(339;336)$, $(205;200)$, $(117;108)$, $(75;60)$, $(53;28)$, $(51;24)$ et $(45;0)$. (1 pt : 0,5 pour la décomposition et les diviseurs, 0,5 pour les couples) (1)
3. c)Un carré est congru à $0$ ou $1$ modulo $4$ ($0^2=0$, $1^2=1$, $2^2=4\equiv 0$, $3^2=9\equiv 1$). Donc $x^2-y^2$ est congru à $0$, $1$ ou $-1\equiv 3$ modulo $4$, jamais à $2$. Or $2026=4\times 506+2\equiv 2[4]$ : pas de solution. (1 pt) (1)
4. d)Si $N=x^2-y^2$, c) montre que $N\not\equiv 2[4]$. Réciproquement, si $N$ est impair, $N=2k+1=(k+1{)}^2-k^2$ ; si $N\equiv 0[4]$, $N=4k=(k+1{)}^2-(k-1{)}^2$, car $(k+1{)}^2-(k-1{)}^2=4k$. Ces deux cas couvrent tous les $N\not\equiv 2[4]$. (1 pt : 0,5 par sens) (1)

Astuce — Une factorisation $(x-y)(x+y)=N$ ramène l'équation à la liste des diviseurs de $N$, et les carrés modulo $4$ (seulement $0$ et $1$) suffisent à exclure les entiers congrus à $2$ modulo $4$.