Answer to Question #272613 in Combinatorics | Number Theory for Prathibha Rose

Question

.Solve𝑥 ≡ 7(𝑚𝑜𝑑 11) 𝑥 ≡ 6(𝑚𝑜𝑑 8) 𝑥 ≡ 10(𝑚𝑜𝑑 15) Also find the

smallest non-negative solutions

Answer 1

Let us solve the following system of congruences:

$\begin{cases} x≡7 \mod 11\\ x≡6\mod 8\\ x≡10\mod 15 \end{cases}.$

The first congruence is equivalent to the equality $x=7+11t,\ t\in\Z.$ Let us put this in the second conqruence. Then we have $7+11t\equiv 6 \mod 8.$ The last conqruence is equivalent to $11t\equiv -1 \mod 8,$ and hence to $(11-8)t\equiv (16-1) \mod 8,$ that is $3t\equiv 15 \mod 8.$ Since 3 and 8 are relatively prime, we conclude that $t\equiv 5\mod 8.$ It follows that $t=5+8s,$ and hence $x=7+11(5+8s)=62+88s.$ Let us put this in the last conqruence. Then we get $62+88s≡ 10 \mod 15,$ which is equivalent to $88s≡-52\mod 15,$ and hence to $13s≡-52\mod 15.$ It follows that $s\equiv-4\mod 15,$ and hence $s=-4+15k.$ We conclude that $x=62+88s=62+88(-4+15k)=-290+1320k.$

Consequently, the solution of the system is $x\equiv -290\mod 1320$ or $[-290]_{1320}.$

The smallest non-negative solution is $-290+1320=1030.$