Soit $N$ le nombre de soldats. D'après l'énoncé, l'empereur a moins d'un million d'hommes, donc $N < 10^6$.
Les deux mises en formation se traduisent par le système de congruences suivant : \[\begin{cases} N \equiv 180 \pmod{841} & (\text{car } 29^2 = 841) \\ N \equiv 1120 \pmod{1225} & (\text{car } 35^2 = 1225) \end{cases}\]
-
1. Traduction de la première équation :
D'après la première congruence, il existe un entier naturel $k$ tel que : \[N = 841k + 180\] -
2. Injection dans la seconde équation :
En substituant $N$ dans la deuxième congruence, on obtient : \[841k + 180 \equiv 1120 \pmod{1225}\] Ce qui se simplifie en : \[841k \equiv 940 \pmod{1225}\] -
3. Inversion modulaire :
Les entiers $841 = 29^2$ et $1225 = 5^2 \times 7^2$ sont premiers entre eux ($\text{pgcd}(841, 1225) = 1$).
L'algorithme d'Euclide étendu nous donne la relation de Bézout correspondante : \[386 \times 841 - 265 \times 1225 = 1\] L'inverse de $841$ modulo $1225$ est donc $386$.
En multipliant les deux membres de notre congruence par cet inverse, on isole $k$ : \[k \equiv 940 \times 386 \pmod{1225}\] \[k \equiv 362840 \pmod{1225}\] En effectuant la division euclidienne de $362840$ par $1225$ pour réduire le résultat, on trouve un reste de $240$. D'où : \[k \equiv 240 \pmod{1225}\] -
4. Conclusion pour $N$ :
Il existe donc un entier $m$ tel que $k = 1225m + 240$.
On réinjecte cette expression de $k$ dans notre équation initiale pour $N$ : \[N = 841(1225m + 240) + 180\] \[N = 1030225m + 201840 + 180\] \[N = 1030225m + 202020\]
Puisque l'énoncé stipule que $N < 10^6$, la seule valeur possible pour $m \in \mathbb{N}$ est $m = 0$.
L'armée de l'empereur comptait donc très exactement 202 020 soldats.