Processing math: 100%
 
+0  
 
0
1019
3
avatar

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? Thanks for help.

 Feb 10, 2017
 #1
avatar+170 
0

(32 devide 3.555555555555)=9

 Feb 10, 2017
 #2
avatar
0

LCM 31, 41 =31 x 41 =1,271
31r + 9 =41s + 39, solve for r, s
r=38, s=28
The smallest number n =
31 x 38 + 9 =1,187, and the general form of n=
1,271(LCM)*C + 1,187 =n. When C=0, 1, 2......etc., we have:
n=1,187
n=2,458
n=3,729........etc.

 Feb 10, 2017
 #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

 Feb 13, 2017

1 Online Users

avatar