We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive pseudonymised information about your use of our website. cookie policy and privacy policy.

Find the least positive four-digit solution to the following system of congruences.

\(7x \equiv 21 \pmod{14} \)

\(2x+13 \equiv 16 \pmod{9} \)

\(-2x+1 \equiv x \pmod{25} \)

 Jan 20, 2019

from the first one, you can see that x is odd.


now you do the second one.


this means 2x leaves a remainder of 3 when divided by 9.


this means x is a multiple of 3.


now, 3x divided by 25 leaves  remainder of 1 from the third one.


now you do guess and check and see tht the first x is 17, the next is 42, the next is 67, and on and on


this means that the number when divided by 25 leaves remainder 17, and that it is odd.


2x is remainder of 3 when divided by 9, so the first one would be 42, then adding 225 because of 25 and 9, so then it would be 942 would be one, then 1167. you can double check and it all works.



 Jan 20, 2019
edited by asdf335  Jan 20, 2019

There is a more formal method to solving this problem.

First let's reduce these congruences.


\(7x \equiv 21 \pmod{14}\\ x \equiv 3 \pmod{2}\\ x \equiv 1 \pmod{2}\)


\(2x+13 \equiv 16 \pmod{9}\\ 2x \equiv 3 \pmod{9}\\ \text{now we multiply both sides by the multiplicative inverse of }2 \pmod{9}\\ 5\cdot 2x \equiv 5\cdot 3 \pmod{9}\\ x \equiv 6 \pmod{9}\)


\(-2x + 1 \equiv x \pmod{25}\\ 3x \equiv 1 \pmod{25}\\ 17\cdot 3x \equiv 17 \pmod{25}\\ x \equiv 17 \pmod{25}\)


\(\text{Now we have the following system of linear congruences}\\ x \equiv 1 \pmod{2}\\ x \equiv 6 \pmod{9}\\ x \equiv 17 \pmod{25}\)


\(\text{From the first congruence we have}\\ x = 2t+1,~t \in \mathbb{Z}\\ \text{substitute this into the second congruence}\\ 2t+1 \equiv 6 \pmod{9}\\ 2t\equiv 5 \pmod{9}\\ 5\cdot 2t \equiv 5\cdot 5 \pmod{9}\\ t \equiv 7 \pmod{9}\\ t = 9s+7,~s \in \mathbb{Z}\)


\(\text{substitute this back into }x \text{ and simplify}\\ x = 2(9s+7)+1\\ x = 18s + 14+1 = 18s+15\)


\(\text{Now we substitute this into the third congruence}\\ 18s+15 \equiv 17 \pmod{25}\\ 18s \equiv 2 \pmod{25}\\ \text{Now we have to find }18^{-1} \pmod{25},\text{ with these small numbers trial and error works}\\ 18^{-1}\pmod{25} = 7\\ 7\cdot 18 s \equiv 14 \pmod{25}\\ s \equiv 14 \pmod{25}\\ s = 25u+14,~u\in \mathbb{Z}\)


\(\text{and we substitute this back into }x\\ x = 18(25u+14)+15 = 267+450u\\ x \equiv 267 \pmod{450}\\ \text{The smallest 4 digit solution will be}\\ x = 2\cdot 450 + 267 = 1167\)

 Jan 20, 2019
edited by Rom  Jan 20, 2019
edited by Rom  Jan 20, 2019

28 Online Users