Loading [MathJax]/jax/output/SVG/jax.js
 

heureka

avatar
Benutzernameheureka
Punkte26396
Membership
Stats
Fragen 17
Antworten 5678

 #5
avatar+26396 
+5

What is the smallest positive n under 50,000 that satisfies the following:

n mod 43 = 22 

n mod 101 = 64 

n mod 211 = 30 . Thanks for help.

 

n22(mod43)n64(mod101)n30(mod211)Let m=43101211=916373

 

43 is a prime number, and 101 is a prime number, and 211 is a prime number.

Because 43 and 101 and 211 are relatively prim ( gcd(43,101,211) = 1! ) we can go on:

 

n=22101211[(101211)φ(43)1mod43]=modulo inverse (101211)(mod43)=(101211)421(mod43)=(101211)41(mod43)=(21311(mod43))41(mod43)=(26)41(mod43)=5+6443211[(43211)φ(101)1mod101]=modulo inverse (43211)(mod101)=(43211)1001(mod101)=(43211)99(mod101)=(9073(mod101))99(mod101)=(84)99(mod101)=95+3043101[(43101)φ(211)1mod211]=modulo inverse (43101)(mod211)=(43101)2101mod211=(43101)209mod211=(4343(mod211))209mod211=(123)209mod211=199+43101211k|kZn=22101211[5]+6443211[95]+3043101[199]+43101211kn=2344210+55163840+25927710+43101211kn=83435760+916373k|kZnmin=83435760(mod916373)nmin=45817n=45817+916373k|kZ

 

The smallest positive n under 50,000 is 45817

 

laugh

20.02.2017
 #1