Processing math: 100%
 

heureka

avatar
Benutzernameheureka
Punkte26397
Membership
Stats
Fragen 17
Antworten 5678

 #3
avatar+26397 
+5

What is the smallest number that 

when divided by 31 leaves a remainder of 9, and

when divided by 41 leaves a remainder of 39?

 

n9(mod31)n39(mod41)m=3141=1271

 

Because 31 and 41 are relatively prim ( gcd(31,41) = 1! ) we can go on:

 

n=941[141(mod31)]+3931[131(mod41)]+3141k|kZ

 

[141(mod31)]| modular inverse 411411(mod31)=41φ(31)1(mod31)| Euler's totient function φ(n)φ(p)=p1=41301(mod31)=4129(mod31)|41(mod31)=10=1029(mod31)=28[131(mod41)]| modular inverse 311311(mod41)=31φ(41)1(mod41)| Euler's totient function φ(n)φ(p)=p1=31401(mod41)=3139(mod41)=4

 

n=94128+39314+3141kn=10332+4836+1271kn=15168+1271k|kZ

 

nmin=15168(mod1271)nmin=1187n=1187+1271k|kZ

 

The smallest number is 1187

 

laugh

13.02.2017
 #13
avatar+26397 
+10

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.

 

n14(mod127)n66(mod131)m=127131=16637

 

Because 127 and 131 are relatively prim ( gcd(127,131) = 1! ) we can go on:

 

n=14131[1131(mod127)]+66127[1127(mod131)]+127131k|kZ

 

[1131(mod127)]| modular inverse 13111311(mod127)=131φ(127)1(mod127)| Euler's totient function φ(n)φ(p)=p1=1311261mod127=131125mod127=32[1127(mod131)]| modular inverse 12711271(mod131)=127φ(131)1(mod131)| Euler's totient function φ(n)φ(p)=p1=1271301mod131=127129mod131=98

 

n=1413132+6612798+127131kn=58688+821436+16637kn=880124+16637k|kZ

 

nmin=880124(mod16637)nmin=15000n=15000+16637k|kZ

 

k=0:n=15000

 

The smallest number is 15000

 

laugh

13.02.2017