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

MathCuber
Nov 21, 2018

#1**+2 **

a=listfor(n, 1, 23, GCD(( 9*n-2), (7*n+3))=(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 41)=**n=23 **and the** GCD of [164, 205] =41**

Guest Nov 21, 2018

#2**+2 **

You can put that into the "LaTeX" box to make the GCD part look nicer.

PartialMathematician
Nov 21, 2018

#3**+9 **

**What is the smallest positive integer n for which **

**9n-2 and 7n+3 **

**share a common factor greater than 1?**

\(\text{Euclidean algorithm:}~ \boxed{gcd(a-nb,b)=gcd(a,b)} \)

\(\begin{array}{|rcll|} \hline && gcd(9n-2,7n+3) \\ &=& gcd(9n-2-1\cdot(7n+3) ,7n+3)=gcd(2n-5,7n+3) \\ &=& gcd(2n-5,7n+3-3\cdot(2n-5))=gcd(2n-5,n+18) \\ &=& gcd(2n-5-2\cdot(n+18),n+18)=gcd(-41,n+18) \\ \hline \end{array} \)

\(\begin{array}{|rcll|} \hline gcd(-41,\underbrace{n+18}_{=41~(\Rightarrow n>0!)}) \qquad -41~ \text{is prime} \\\\ n+18 &=& 41 \\ n &=& 41-18 \\ n &=& 23 \\ \hline \end{array}\)

The common factor greater than 1 is \(\mathbf{41}\).

and the smallest positive integer **n** is \(\mathbf{23}\)

Hint: \(gcd(-41,41) = 41\)

heureka
Nov 21, 2018