Questions   
Sort: 
 #2
avatar+845 
0
Jan 20, 2019
 #1
avatar
0
Jan 20, 2019
 #2
avatar+6248 
+2

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

2 Online Users

avatar