1. **State the problem:** We are given a system of congruences: $$3x \equiv 5 \pmod{19},$$ $$7x \equiv 9 \pmod{29},$$ $$9x \equiv 11 \pmod{31}.$$ We need to find the least positive solution for $x$ that satisfies all three congruences. 2. **Solve each congruence for $x$:** - For $3x \equiv 5 \pmod{19}$, find the inverse of 3 modulo 19. Since $3 \times 13 = 39 \equiv 1 \pmod{19}$, the inverse of 3 mod 19 is 13. Thus, $$x \equiv 5 \times 13 = 65 \equiv 65 - 57 = 8 \pmod{19}.$$ - For $7x \equiv 9 \pmod{29}$, find the inverse of 7 modulo 29. Since $7 \times 25 = 175 \equiv 1 \pmod{29}$ (because $175 - 174 = 1$), the inverse of 7 mod 29 is 25. Thus, $$x \equiv 9 \times 25 = 225 \equiv 225 - 203 = 22 \pmod{29}.$$ - For $9x \equiv 11 \pmod{31}$, find the inverse of 9 modulo 31. Since $9 \times 7 = 63 \equiv 1 \pmod{31}$ (because $63 - 62 = 1$), the inverse of 9 mod 31 is 7. Thus, $$x \equiv 11 \times 7 = 77 \equiv 77 - 62 = 15 \pmod{31}.$$ 3. **Rewrite the system:** $$x \equiv 8 \pmod{19},$$ $$x \equiv 22 \pmod{29},$$ $$x \equiv 15 \pmod{31}.$$ 4. **Use the Chinese Remainder Theorem (CRT):** Let $N = 19 \times 29 \times 31 = 17051$. Define: $$N_1 = \frac{N}{19} = 29 \times 31 = 899,$$ $$N_2 = \frac{N}{29} = 19 \times 31 = 589,$$ $$N_3 = \frac{N}{31} = 19 \times 29 = 551.$$ Find inverses $M_i$ such that: $$N_1 M_1 \equiv 1 \pmod{19},$$ $$N_2 M_2 \equiv 1 \pmod{29},$$ $$N_3 M_3 \equiv 1 \pmod{31}.$$ - For $M_1$: Solve $899 M_1 \equiv 1 \pmod{19}$. Calculate $899 \mod 19$: $19 \times 47 = 893$, remainder $6$, so $899 \equiv 6 \pmod{19}$. Solve $6 M_1 \equiv 1 \pmod{19}$. Since $6 \times 16 = 96 \equiv 1 \pmod{19}$ (because $96 - 95 = 1$), $M_1 = 16$. - For $M_2$: Solve $589 M_2 \equiv 1 \pmod{29}$. Calculate $589 \mod 29$: $29 \times 20 = 580$, remainder $9$, so $589 \equiv 9 \pmod{29}$. Solve $9 M_2 \equiv 1 \pmod{29}$. Since $9 \times 13 = 117 \equiv 1 \pmod{29}$ (because $117 - 116 = 1$), $M_2 = 13$. - For $M_3$: Solve $551 M_3 \equiv 1 \pmod{31}$. Calculate $551 \mod 31$: $31 \times 17 = 527$, remainder $24$, so $551 \equiv 24 \pmod{31}$. Solve $24 M_3 \equiv 1 \pmod{31}$. Since $24 \times 13 = 312 \equiv 1 \pmod{31}$ (because $312 - 311 = 1$), $M_3 = 13$. 5. **Calculate $x$ using CRT formula:** $$x \equiv a_1 N_1 M_1 + a_2 N_2 M_2 + a_3 N_3 M_3 \pmod{N},$$ where $a_1=8$, $a_2=22$, $a_3=15$. Calculate each term: - $8 \times 899 \times 16 = 8 \times 899 = 7192; 7192 \times 16 = 115072$ - $22 \times 589 \times 13 = 22 \times 589 = 12958; 12958 \times 13 = 168454$ - $15 \times 551 \times 13 = 15 \times 551 = 8265; 8265 \times 13 = 107445$ Sum: $$115072 + 168454 + 107445 = 390971.$$ Find $390971 \mod 17051$: Divide $390971$ by $17051$: $17051 \times 22 = 375122$, remainder $390971 - 375122 = 15849$. So, $$x \equiv 15849 \pmod{17051}.$$ The least positive solution is $x = 15849$. --- 6. **Part a) Find $d$ such that:** $$d \equiv 4x^2 + 3x \pmod{5701}.$$ Calculate $x^2 \mod 5701$: Calculate $15849 \mod 5701$ first: $5701 \times 2 = 11402$, remainder $15849 - 11402 = 4447$. So $x \equiv 4447 \pmod{5701}$. Calculate $x^2 \equiv 4447^2 \pmod{5701}$. Calculate $4447^2 = 4447 \times 4447$: $4447 \times 4447 = (4000 + 447)^2 = 4000^2 + 2 \times 4000 \times 447 + 447^2 = 16,000,000 + 3,576,000 + 199,809 = 19,775,809.$ Now find $19,775,809 \mod 5701$: Divide $19,775,809$ by $5701$: Calculate approximate quotient: $5701 \times 3000 = 17,103,000$ remainder $2,672,809$ $5701 \times 400 = 2,280,400$ remainder $392,409$ $5701 \times 68 = 387,668$ remainder $4,741$ $5701 \times 0 = 0$ Sum quotients: $3000 + 400 + 68 = 3468$ Remainder: $4,741$ So, $$4447^2 \equiv 4741 \pmod{5701}.$$ Calculate $4x^2 \equiv 4 \times 4741 = 18,964 \equiv 18,964 - 3 \times 5701 = 18,964 - 17,103 = 1,861 \pmod{5701}.$ Calculate $3x \equiv 3 \times 4447 = 13,341 \equiv 13,341 - 2 \times 5701 = 13,341 - 11,402 = 1,939 \pmod{5701}.$ Finally, $$d \equiv 1861 + 1939 = 3800 \pmod{5701}.$$ **Answer:** $$\boxed{d = 3800}.$$