Determine the smallest non-negative integer a that satisfies the congruences:
a≡2(mod3)a≡4(mod5)a≡1(mod7)a≡8(mod9)
1. join
a≡2(mod3)a≡8(mod9)
a=2+3na=8+9m2+3n=8+9m3n=6+9m|:3n=2+3ma=2+3n|n=2+3ma=2+3(2+3m)a=2+6+9ma=8+9ma≡8(mod9)a≡2(mod3)a≡8(mod9)}a≡8(mod9)
2. join
a≡4(mod5)a≡1(mod7)
a=4+5ra=1+7s4+5r=1+7s5r=7s−3r=7s−35r=5s+2s−35r=s+2s−35⏟=tr=s+tt=2s−355t=2s−32s=5t+3s=5t+32s=4t+t+2+12s=2t+1+t+12⏟=us=2t+1+uu=t+122u=t+1t=2u−1s=2(2u−1)+1+us=5u−1r=5u−1+2u−1r=7u−2a=4+5ra=4+5(7u−2)a=−6+35ua≡−6(mod35)a≡4(mod5)a≡1(mod7)}a≡−6(mod35)
3. join
a≡8(mod9)a≡−6(mod35)
a=8+9va=−6+35w8+9v=−6+35w9v=35w−14v=35w−149v=27w+8w−9−59v=3w−1+8w−59⏟=xv=3w−1+xx=8w−599x=8w−58w=9x+5w=9x+58w=8x+x+58w=x+x+58⏟=yw=x+yy=x+588y=x+5x=8y−5w=8y−5+yw=9y−5v=3(9y−5)−1+8y−5v=35y−21a=8+9va=8+9(35y−21)a=−181+315ya≡−181(mod315)a≡−181+315(mod315)a≡134(mod315)a≡8(mod9)a≡−6(mod35)}a≡134(mod315)
The smallest non-negative integer a is 134
