What is the smallest positive integer that will satisfy the following congruences:
N mod 105 = 104,
N mod 111 = 110,
N mod 121 = 111,
N mod 122 = 111
Thanks for any help.
n≡104(mod105)n≡110(mod111)⇒n−104=105xn−110=111y⇒n=104+105xn=110+111yn=104+105x=110+111y104+105x=110+111y105x−111y=6|:335x−37y=2x,y∈Z→x=−1+37b1)b∈Zn=104+105xn=104+105(−1+37b)n=104−105+105⋅37bn=−1+3885bn≡−1(mod3885)(1)
n≡111(mod121)n≡111(mod122)⇒n−111=121xn−111=122y⇒n=111+121xn=111+122yn=111x+121y=111+122y111x+121y=111+122y121x−122y=0x,y∈Z→x=122a2)a∈Zn=111+121xn=111+121(122a)n=111+121⋅122an=111+14762an≡111(mod14762)(2)
After reducing, we have two formulas:
n≡−1(mod3885)(1)n≡111(mod14762)(2)
n≡−1(mod3885)n≡111(mod14762)⇒n+1=3885xn−111=14762y⇒n=−1+3885xn=111+14762yn=−1+3885x=111+14762y−1+3885x=111+14762y3885x−14762y=112x,y∈Z→x=3378+14762g3)g∈Zn=−1+3885xn=−1+3885⋅(3378+14762g)n=−1+3885⋅3378+3885⋅14762gn=13123529+57350370gg∈Z
The smallest positive integer is 13 123 529
Proof:
13 123 529mod 105=10413 123 529mod 111=11013 123 529mod 121=11113 123 529mod 122=111
1)Solve of the diophantine equation 35x−37y=2 The variable with the smallest coefficient is x. The equation is transformed after x: 35x=2+37yx=2+37y35=2+35y+2y35=35y+2+2y35=35y35+2+2y35x=y+2+2y35we set:a=2+2y3535a=2+2yThe variable with the smallest coefficient is y. The equation is transformed after y: 2y=−2+35ay=−2+35a2=−2+34a+a2=34a−2+a2=−−22+34a2+a2y=−1+17a+a2we set:b=a22b=aThe variable with the smallest coefficient is a. The equation is transformed after a: no fraction there:a=2b
Elemination of the unknowns:y=−2+35a2|a=2b=−2+35⋅(2b)2y=−1+35bx=2+37y35|y=−1+35b=2+37⋅(−1+35b)11x=−1+37b
2)Solve of the diophantine equation 121x−122y=0 The variable with the smallest coefficient is x. The equation is transformed after x: 121x=122yx=122y121=121y+y121=121y121+y121x=y+y121we set:a=y121121a=yThe variable with the smallest coefficient is y. The equation is transformed after y: no fraction there:y=121a
Elemination of the unknowns:x=122y121|y=121a=122⋅(121a)121x=122a
3)Solve of the diophantine equation 3885x−14762y=112 The variable with the smallest coefficient is x. The equation is transformed after x: 3885x=112+14762yx=112+14762y3885=112+11655y+3107y3885=11655y+112+3107y3885=11655y3885+112+3107y3885x=3y+112+3107y3885we set:a=112+3107y38853885a=112+3107yThe variable with the smallest coefficient is y. The equation is transformed after y: 3107y=−112+3885ay=−112+3885a3107=−112+3107a+778a3107=3107a−112+778a3107=3107a3107+−112+778a3107y=3a+112+3107a3107we set:b=−112+778a31073107b=−112+778aThe variable with the smallest coefficient is a. The equation is transformed after a: 778a=112+3107ba=112+3107b778=112+2334b+773b778=2334b+112+773b778=2334b3107+112+773b778a=3b+112+773b778we set:c=112+773b778778c=112+773bThe variable with the smallest coefficient is b. The equation is transformed after b: 773b=−112+778cb=−112+778c773=−112+773c+5c773=773c−112+5c773=773c773+−112+5c773b=c+−112+5c773we set:d=−112+5c773773d=−112+5cThe variable with the smallest coefficient is c. The equation is transformed after c: 5c=112+773dc=112+773d5=110+2+770d+3d5=110+770d+2+5d5=1105+770d5+2+3d5c=22+154d+2+3d5we set:e=2+3d55e=2+3dThe variable with the smallest coefficient is d. The equation is transformed after d: 3d=−2+5ed=−2+5e3=−2+3e+2e3=3e−2+2e3=3e3+−2+2e3d=e+−2+2e3we set:f=−2+2e33f=−2+2eThe variable with the smallest coefficient is e. The equation is transformed after e: 2e=2+3fe=2+3f2=2+2f+f2=22+2f2+f2e=1+f+f2we set:g=f22g=fThe variable with the smallest coefficient is f. The equation is transformed after f: no fraction there:f=2g
Elemination of the unknowns:e=2+3f2|f=2g=2+3⋅2g2e=1+3gd=−2+5e3|e=1+3g=−2+5⋅(1+3g)2d=1+5gc=112+773d5|d=1+5g=112+773⋅(1+5g)2c=177+773gb=−112+778c773|c=177+773g=−112+778⋅(177+773g)773b=178+778ga=112+3107b778|b=178+778g=112+3107⋅(178+778g)778a=711+3107gy=−112+3885a3107|a=711+3107g=−112+3885⋅(711+3107g)3107y=889+3885gx=112+14762y3885|y=889+3885g=112+14762⋅(889+3885g)3885x=3378+14762g
