Question

Find the smallest positive integer that satisfies both of the following equations: x≡3(mod4) and x≡5(mod6).

Answer 1

11

Explanation:

Because 4 and 6 aren't co prime we can't start the chinese remainder theorem

so first we check

`x\equiv 3\mod4\\\\\rightarrow x\equiv 3 \mod 2\\\\\rightarrow x \equiv 3 \mod 2`

because 4 = 2*2

`x\equiv3\equiv1\mod2`

and the other one

`x\equiv5\mod6\\\\\rightarrow x\equiv5\mod2\\\\\rightarrow x\equiv5\mod3\\\\x\equiv5\equiv1\mod2\\\\x\equiv5\equiv2\mod3`

so now we have

`x\equiv3\mod4\\\\x\equiv1\mod2\\\\x\equiv2\mod3`

but the mod 2 we don't need it

so now we have

`x\equiv3\mod 4\\\\x\equiv 2\mod 3\\\\`

for the first one we can say that

`x=4n+3`

so we plug in that in the second one

`4n+3\equiv2\mod3\\\\4n\equiv2\mod3\\\\n\equiv2\mod3`

we can say that

`n=3k+2`

so for x

`x=4(3k+2)+3\\\\x=12k+8+3\\\\x=12k+11`

so if k=0

a solution is 11

we check if it works

`11\equiv8+3\equiv0+3\equiv3\mod4`

`11\equiv6+5\equiv0+5\equiv5\mod6`

so it works so the smallest solution is 11

Answer 2

Explanation:

x≡3(mod4) and x≡5(mod6)

=> x≡-1(mod4) and x≡-1(mod6)

Since LCM of 4 and 6 is 12,

=> x≡-1(mod12)

=> x≡11(mod12)

The smallest positive integer for x is 11.