+0

help

0
237
1

What is the smallest positive integer $n$ for which $9n-2$ and $7n + 3$ share a common factor greater than $1$?

May 12, 2020

#1
+25565
+1

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}$$

May 12, 2020