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.
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.
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?
n≡9(mod31)n≡39(mod41)m=31⋅41=1271
Because 31 and 41 are relatively prim ( gcd(31,41) = 1! ) we can go on:
n=9⋅41⋅[141(mod31)]+39⋅31⋅[131(mod41)]+31⋅41⋅k|k∈Z
[141(mod31)]| modular inverse 41⋅141≡1(mod31)=41φ(31)−1(mod31)| Euler's totient function φ(n)φ(p)=p−1=4130−1(mod31)=4129(mod31)|41(mod31)=10=1029(mod31)=28[131(mod41)]| modular inverse 31⋅131≡1(mod41)=31φ(41)−1(mod41)| Euler's totient function φ(n)φ(p)=p−1=3140−1(mod41)=3139(mod41)=4
n=9⋅41⋅28+39⋅31⋅4+31⋅41⋅kn=10332+4836+1271⋅kn=15168+1271⋅k|k∈Z
nmin=15168(mod1271)nmin=1187n=1187+1271⋅k|k∈Z
The smallest number is 1187