Solution: Solve $x \equiv 3 \pmod{7}$ and $x \equiv 5 \pmod{9}$. Let $x = 7k + 3$. Substitute into the second congruence: $7k + 3 \equiv 5 \pmod{9} \Rightarrow 7k \equiv 2 \pmod{9}$. The modular inverse of 7 modulo 9 is 4 (since $7 imes 4 = 28 \equiv 1 \pmod{9}$), so $k \equiv 2 imes 4 = 8 \pmod{9}$. Thus, $k = 9m + 8$, and $x = 7(9m + 8) + 3 = 63m + 59$. The solutions are $59, 122, 185, \dots$. Within 1â150, only 59 and 122 satisfy. The count is $oxed{2}$.
["Solving the System of Congruences: A Step-by-Step Guide to Find All Solutions", "When faced with a system of modular equations like:", "$$\n\begin{align}\nx &\equiv 3 \pmod{7}, \\nx &\equiv 5 \pmod{9},\n\end{align}\n$$", "finding a solution that satisfies both conditions can be efficiently achieved using substitution and modular arithmetic—especially when dealing with relatively prime moduli. This article explains the solution process clearly and demonstrates how to find all valid solutions within a given range.", "---", "### Step 1: Express ( x ) from the First Congruence", "From the first congruence:", "$$\nx \equiv 3 \pmod{7},\n$$", "we can express ( x ) as:", "$$\nx = 7k + 3,\n$$", "for some integer ( k ). This substitution simplifies the problem by replacing ( x ) in the second congruence.", "---", "### Step 2: Substitute into the Second Congruence", "Substitute ( x = 7k + 3 ) into the second equation:", "$$\n7k + 3 \equiv 5 \pmod{9}.\n$$", "Subtract 3 from both sides:", "$$\n7k \equiv 2 \pmod{9}.\n$$", "Now the key step is solving this single modular linear equation for ( k ) modulo 9.", "---", "### Step 3: Find the Modular Inverse of 7 Modulo 9", "To solve ( 7k \equiv 2 \pmod{9} ), we need the modular inverse of 7 modulo 9—the number ( m ) such that:", "$$\n7m \equiv 1 \pmod{9}.\n$$", "By testing small values or using the extended Euclidean algorithm, we find ( m = 4 ) because:", "$$\n7 \ imes 4 = 28 \equiv 1 \pmod{9}.\n$$", "Thus, multiply both sides of ( 7k \equiv 2 \pmod{9} ) by 4:", "$$\nk \equiv 4 \ imes 2 = 8 \pmod{9}.\n$$", "So,\n$$\nk = 9m + 8 \quad \ ext{for some integer } m.\n$$", "---", "### Step 4: Back-Substitute to Find ( x )", "Recall ( x = 7k + 3 ). Substitute ( k = 9m + 8 ):", "$$\nx = 7(9m + 8) + 3 = 63m + 56 + 3 = 63m + 59.\n$$", "Therefore, the general solution is:", "$$\nx \equiv 59 \pmod{63}.\n$$", "---", "### Step 5: Find All Solutions Within 1 to 150", "The general solution ( x = 63m + 59 ) gives all integers satisfying both congruences. We now find which values fall between 1 and 150.", "Set up the inequality:", "$$\n1 \leq 63m + 59 \leq 150.\n$$", "Subtract 59:", "$$\n-58 \leq 63m \leq 91.\n$$", "Divide by 63:", "$$\n-0.919 \leq m \leq 1.444.\n$$", "So integer values of ( m ) are ( m = 0 ) and ( m = 1 ).", "- For ( m = 0 ): ( x = 63(0) + 59 = 59 )\n- For ( m = 1 ): ( x = 63(1) + 59 = 122 )", "For ( m = 2 ), ( x = 63 \ imes 2 + 59 = 185 ), which exceeds 150.", "Thus, the valid solutions in the range are ( 59 ) and ( 122 )—a total of two solutions.", "---", "### Final Answer", "The solutions to the system\n$$\nx \equiv 3 \pmod{7}, \quad x \equiv 5 \pmod{9}\n$$\nwithin the range ( 1 \leq x \leq 150 ) are ( 59 ) and ( 122 ). The total count is securely:", "$$\n\boxed{2}\n$$", "---", "### Why This Method Works", "This approach efficiently reduces a system of linear congruences to a single one by substitution, leveraging modular inverses to isolate variables. When moduli are relatively prime—as in this case, gcd(7,9) = 1—this method guarantees a unique solution modulo the product (here, ( 7 \ imes 9 = 63 )). For repeated values in the range, simple enumeration confirms all valid solutions.", "This technique is not only fundamental in number theory but also foundational in cryptography and computer science for solving simultaneous modular constraints efficiently."]
