What is the smallest number under 16,000 that
when divided by 127 leaves a remainder of 14,
and when divided by 131 leaves a ramainder of 66.
n≡14(mod127)n≡66(mod131)m=127⋅131=16637
Because 127 and 131 are relatively prim ( gcd(127,131) = 1! ) we can go on:
n=14⋅131⋅[1131(mod127)]+66⋅127⋅[1127(mod131)]+127⋅131⋅k|k∈Z
[1131(mod127)]| modular inverse 131⋅1131≡1(mod127)=131φ(127)−1(mod127)| Euler's totient function φ(n)φ(p)=p−1=131126−1mod127=131125mod127=32[1127(mod131)]| modular inverse 127⋅1127≡1(mod131)=127φ(131)−1(mod131)| Euler's totient function φ(n)φ(p)=p−1=127130−1mod131=127129mod131=98
n=14⋅131⋅32+66⋅127⋅98+127⋅131⋅kn=58688+821436+16637⋅kn=880124+16637⋅k|k∈Z
nmin=880124(mod16637)nmin=15000n=15000+16637⋅k|k∈Z
k=0:n=15000
The smallest number is 15000
