Page 30 - MATINF Nr. 13-14

30 V. P˘aun

21*3 (unde 3 este restul imp˘art , irii la 5)=63;

15*2 (unde 2 este restul imp˘art , irii la 7)=30.
2. Adun˘am rezultatele: 140+63+30=233.
Se observ˘a c˘ 233 verific˘ resturile din enunt , .
a
a
3. Ajustarea la dimensiunea armatei:
Deoarece 3*5*7=105, orice multiplu de 105 adunat sau sc˘azut din 233 va oferi aceleas , i
resturi la imp˘art , irile cu 3, 5 respectiv 7 (adic˘ tot 2, 3, 2).
a
Astfel cel mai mic num˘ar natural care indeplines , te condit , iile din enunt , este 233-2*105=23.

Dac˘ generalul s , tia c˘ are o armat˘ ˆın jur de 1000 de oameni, aduna multipli de 105 pˆan˘
a
a
a
a
ajungea la numarul plauzibil (23+10*105=1073 soldat , i).
Pentru a ret , ine aceste ,,numere magice”, matematicienii chinezi au creat un cˆantec:
,,Trei oameni merg ˆımpreun˘a, s , aptezeci de ani au implinit, Cinci pruni ˆınflorit , i, cu dou˘azeci
a
s , i una de ramuri, S , apte copii se joac˘, cincisprezece zile au trecut ,Scade o sut˘ cinci s , i vei afla
a
r˘aspunsul.”
ˆ a
In 1801, matematicianul Carl Friedrich Gauss a definit conceptul de congruent , ˘ ˆın cartea sa
Disquisitiones Arithmeticae” s , i a inventat notat , ia (≡) pentru congruent , ˘a.
”
Dou˘a numere ˆıntregi sunt ,,congruente modulo m” dac˘a dau acelas , i rest la ˆımp˘art , irea prin
a
m s , i se noteaz˘ a ≡ b (mod m).
Sunt valabile propriet˘at , ile:

1. a ≡ b (mod m) s , i c≡ d (mod m) ⇒ a + c ≡ b + d (mod m) s , i ac ≡ bd (mod m).

Demonstrat , ie:
a ≡ b (mod m), deci a = p ∗ m + b;

c ≡ d (mod m), deci c = q ∗ m + c.

a + c = (p + q) ∗ m + (b + c), deci a + c ≡ b + c (mod m);

a ∗ c = m(p ∗ q ∗ m + p ∗ c + q ∗ b) + b ∗ c, deci ac ≡ bc (mod m).
2. Dac˘a x ≡ a (mod m) s , i x ≡ a (mod n) atunci x ≡ a (mod cmmmc(m, n)).

Demonstrat , ie:

x ≡ a (mod m), deci m|(x − a);
x ≡ a (mod n), deci n|(x − a).

Prin urmare x − a este multiplu comun al numerelor m s , i n, deci este multiplu s , i pentru
cmmmc(m, n).
3. Inversul modular al unui num˘ar aˆın raport cu un modul m este un num˘ar b cu proprietatea
c˘a a ∗ b ≡ 1 (mod m). De exemplu 3 este inversul modular al lui 2 ˆın raport cu modulul 5
deoarece 2 ∗ 3 ≡ 1 (mod 5).

a
a
a
Inversul modular al lui a exist˘ dac˘ s , i numai dac˘ num˘arul a s , i modulul m sunt prime ˆıntre
ˆ
ele. Intr-adev˘ar, din a ∗ b ≡ 1 (mod m) rezult˘a a ∗ b = m ∗ k + 1; dac˘a d = cmmdc(a, m), cum
d|a s , i d|m rezult˘ d|1, deci d = 1.
a