Οι Στρατιώτες

Ένας Κινέζος στρατηγός κάθε πρωί μετράει τους στρατιώτες του και με την παρακάτω μέθοδο βρίσκει πόσοι λείπουν από τους 1.000 συνολικά που έχει. Στην πρωινή αναφορά τους ζητά να παραταχτούν σε σειρές των 11, 13 και 17, και μετρά πόσοι περισσεύουν κάθε φορά. Αν ένα πρωί δει ότι περισσεύουν 3 από τις σειρές των 11, 4 από τις σειρές των 13 και 9 από τις σειρές των 17, πόσοι είναι συνολικά οι στρατιώτες που έχουν παρουσιαστεί; (Κατ.34./Νο.712)

Πηγή:https://www.google.gr/#q=777686223.pdf

Λύση

Παρουσιάστηκαν 927 στρατιώτες. x ≡ 3 mod 11, x ≡ 4 mod 13, x ≡ 9 mod 17, έχει μοναδική λύση modulo n = 11*13*17 = 2.431. Ν1 = n/n1 = 13*17 = 221 M1 = (221)-1 mod 11 = 1-1 mod 11, Ν2 = n/n2 = 11*17 = 187 M2 = (187)-1 mod 13 = 5-1 mod 13, Ν3 = n/n3 = 11*13 = 143 M3 = (143)-1 mod 17 = 7-1 mod 17, M1 = 1, M2 = 8, M3 = 5. Άρα, x ≡ a1N1M1 + a2N2M2 + a3N3M3 mod n ≡ 927 mod 2.431 Λύση του Ε. Αλεξίου. X=3mod11 X=4mod13 X=9mod17 11*13*17=2431 11, 13*17=221=1mod11, 221*3=663=3mod11 13, 11*17=187=5mod13,187*6= 1122=4mod13 17, 11*13=143=7mod17, 143*11=1573=9mod17 663+1122+1573=3358 3358-2431=927=3mod11=4mod13=9mod17