Find the smallest positive integer that satisfies the system of congruences
a)
n congruency sign 2 (mod ll)
n congruency sign 3 (mod 17)
n≡2(mod11)n≡3(mod17)Let m=11⋅17=187
Because 11 and 17 are relatively prim ( gcd(11,17) = 1! ) we can go on:
n=2⋅17⋅[17φ(11)−1(mod11)]⏟=modulo inverse 17 mod 11⏟=1710−1mod11⏟=179mod11⏟=2+3⋅11⋅[11φ(17)−1(mod17)]⏟=modulo inverse 11 mod 17⏟=1116−1mod17⏟=1115mod17⏟=14n=2⋅17⋅[2]+3⋅11⋅[14]n=68+462n=530n(modm)=530(mod187)=156n=156+k⋅187k∈Znmin=156
b)
n congruency sign 1 (mod 7)
n congruency sign 7 (mod 13)
n congruency sign 13 (mod 20)
n≡1(mod7)n≡7(mod13)n≡13(mod20)Let m=7⋅13⋅20=1820
Because 7 and 13 and 20 are relatively prim we can go on:
n=1⋅13⋅20⋅[(13⋅20)φ(7)−1(mod7)]⏟=modulo inverse (13⋅20)mod7⏟=(13⋅20)6−1mod7⏟=(13⋅20)5mod7⏟=(260(mod7))5mod7⏟=(1)5mod7⏟=1+7⋅7⋅20⋅[(7⋅20)φ(13)−1(mod13)]⏟=modulo inverse (7⋅20)mod13⏟=(7⋅20)12−1mod13⏟=(7⋅20)11mod13⏟=(140(mod13))11mod13⏟=(10)11mod13⏟=4+13⋅7⋅13⋅[(7⋅13)φ(20)−1(mod20)]⏟=modulo inverse (7⋅13)mod20⏟=(7⋅13)8−1mod20⏟=(7⋅13)7mod20⏟=(91(mod20))7mod20⏟=(11)7mod20⏟=11n=1⋅13⋅20⋅[1]+7⋅7⋅20⋅[4]+13⋅7⋅13⋅[11]n=260+3920+13013n=17193n(modm)=17193(mod1820)=813n=813+k⋅1820k∈Znmin=813
In number theory, Euler's theorem (also known as the Fermat–Euler theorem or Euler's totient theorem)states that if n and a are coprime positive integers, then aφ(n)≡1(modn)
