Combien de bûchettes

On a donc x = 13a + 7 = 7b + 5 = 5c + 2
13a + 7 = 7b + 5 soit 13a - 7b = -2 équation de Diophante dont les solutions sont a = 2 + 7k, b = 4 + 13k
7b + 5 = 5c + 2 soit 7b - 5c = -3 et b = 1 + 5m, c = 2 + 7m
En égalant les deux valeurs de b obtenues : 4 + 13k = 1 + 5m soit 13k - 5m = -3 et k = 4 + 5p, m = 11 + 13p
Donc a = 2 + 7k = 30 + 35p et finalement x = 13a + 7 = 397 + 455p
Comme x < 500, x = 397 est la seule solution.

Ceci est une application du

Théorème des restes chinois

Si m₁, m₂, ... m_n sont des entiers ≥2 et premiers deux à deux et si a₁, a₂,... a_n sont des entiers quelconques,
alors il existe un entier x unique à une congruence modulo m₁m₂...m_n près, vérifiant simultanément les congruences
x ≡ a₁ modulo m₁
x ≡ a₂ modulo m₂
...
x ≡ a_n modulo m_n

Ici 13, 7 et 5 étant premiers deux à deux (et même premiers tout court), quels que soient les restes choisis pour l'énoncé précédent, le problème est toujours possible.
On obtient un x unique à une congruence modulo 5×7×13 = 455 près.
Posons m = m₁m₂...m_n et calculons les inverses q_i ≡ (m/m_i)^-1 modulo m_i
Alors x ≡ ∑ q_ia_im/m_i    modulo m
L'application du théorème d'Euler-Fermat donne une formule pour les q_i ≡ (m/m_i)^φ(m_i)-1 modulo m_i
Dans la pratique, on utilise plutôt l'algorithme d'Euclide pour résoudre (m/m_i)*q_i ≡ 1 modulo m_i
Ici m₁ = 13, m₂ = 7, m₃ = 5 et m = 455
q₁ ≡ (455/13)^-1 ≡ 35^-1 ≡ 9^-1 ≡ 9¹¹ ≡ 3 modulo 13
q₂ ≡ (455/7)^-1 ≡ 65^-1 ≡ 2^-1 ≡ 2⁵ ≡ 4 modulo 7
q₃ ≡ (455/5)^-1 ≡ 91^-1 ≡ 1^-1 ≡ 1 modulo 5
x ≡ 3×35×7 + 4×65×5 + 1×91×2 = 2217 ≡ 397 modulo 455

Extension

Si les m_i ne sont pas premiers deux à deux, le théorème des restes chinois ne s'applique pas. Ce n'est pas pour cela que le problème est insoluble. Simplement les a_i doivent être particuliers et non plus quelconques pour que le problème ait une solution, modulo le PPCM des m_i. Ici on aura peut être (en choisissant judicieusement la donnée manquante dans l'énoncé) une solution, modulo le PPCM(12,10,9) = 180.
En écrivant directement les équations de Diophante :
x = 12a + 7 = 10b + 5 = 9c + r
12a + 7 = 10b + 5 soit 12a - 10b = -2, le PGCD(12,10) = 2 divise -2 et on simplifie en 6a - 5b = -1, a = 4 + 5k, b = 5 + 6k
12a + 7 = 9c + r soit 12a - 9c = r - 7 Le PGCD(12,9) = 3 doit diviser r -7 et donc r = 7 + 3u = 1,4,7 puisque entre 0 et 8.
La seule valeur paire est r = 4 et l'équation 12a - 9c = 4 - 7 = -3 soit 4a - 3c = -1, a = 2 + 3m, c = 3 + 4m
En égalant les valeurs de a obtenues a = 4 + 5k = 2 + 3m, soit 5k - 3m = -2, k = 2 + 3p, m = 4 + 5p
a = 4 + 5k = 14 + 15p et x = 12a + 7 = 175 + 180p
Le PGCD de 10 et 9 étant 1, il divise bien 5 - r et la solution est correcte.

De façon générale :
N ≡ a_i modulo m_i soit N = a_i + m_ik_i
N ≡ a_j modulo m_j soit N = a_j + m_jk_j
ou a_i - a_j = m_jk_j - m_ik_i    et si G_i,j est le PGCD de m_i et m_j, il doit diviser a_i - a_j

ai - aj ≡ 0 modulo PGCD(mi,mj)