Find the least positive integer that yields the remainders 1

Find the least positive integer that yields the remainders 1, 3, and 5 when divided by 5, 7, and 9, respectively.

Solution

Let x be the required integer

x=1 mod 5

Hence, x=5m+1 ,m =0,1,2,3,....

x=3 mod 7

Case 1: m=0 mod 7

x=1 mod 7

Case 2: m=1 mod 7

x=5(1)+1=6 mod 7

Case 3: m=2 mod 7

x=5*2+1=4 mod 7

Case 4: m=3 mod 7

x=5*3+1=16=2 mod 7

Case 5: m=4 mod 7

x=5*4+1=21=0 mod 7

Case 6: m=5 mod 7

x=5*5+1=26=5 mod 7

Case 7: m=6 mod 7

x=5*6+1=31=3 mod 7

Hence, m=6 mod 7

Hence, m=7k+6,k=0,1,2

Hence, x=5(7k+6)+1=35k+31,k=0,1,2,....

35k+31=8k+4 mod 9

k=1,8k+4=12 =3 mod 9

k=2,8k+4=20=2 mod 9

k=3,8k+4=28=1 mod 9

k=4,8k+4=36=0 mod 9

k=5,8k+4=44=8 mod 9

k=6,8k+4=52=7 mod 9

k=7,8k+4=60=6 mod 9

k=8,8k+4=68=5 mod 9

So smallest k is k=8

Hence, x=35*8+31=311