What is the smallest positive integer $n$ for which $9n-2$ and $7n + 3$ share a common factor greater than $1$?
+26367 What is the smallest positive integer \(n\) for which \(9n-2\) and \(7n + 3\) share a common factor greater than \(1\)?
My attempt:
\(\gcd(9n-2,\ 7n+3) \ne 1\)
\(\begin{array}{|rcll|} \hline \mathbf{\gcd(9n-2,\ 7n+3)} &=& \gcd(9n-2-( 7n+3),\ 7n+3) \\ &=& \gcd(2n-5,\ 7n+3) \\ &=& \gcd(7n+3,\ 2n-5) \\ &=& \gcd(7n+3-3(2n-5),\ 2n-5) \\ &=& \gcd(n+18,\ 2n-5) \\ &=& \gcd(2n-5,\ n+18) \\ &=& \gcd(2n-5-2(n+18),\ n+18) \\ &=& \mathbf{\gcd(-41,\ n+18)} \\ \hline \end{array}\)
\(\begin{array}{|rcll|} \hline \mathbf{\gcd(-41,\ 41)} &=& 41 \\ n+18 &=& 41 \\ n &=& 41-18 \\ \mathbf{n} &=& \mathbf{23} \quad | \quad \text{smallest positive integer n }\\ \hline \end{array}\)
In general:
\(\begin{array}{|rcll|} \hline n+18 &\equiv& 0 \pmod{41} \quad | \quad -18\\ n &\equiv& -18 \pmod{41} \\ n &\equiv& -18 +41 \pmod{41} \\ n &\equiv& 23 \pmod{41} \\ n-23 &=& z\cdot 41 \quad | \quad z\in \mathbb{Z} \\ \mathbf{n} &=& \mathbf{23+z\cdot 41} \\ \hline \end{array}\)
