+0

# Math Help

+2
264
3
+335

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

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

Nov 21, 2018
#2
+701
0

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

PartialMathematician  Nov 21, 2018
#3
+22358
+11

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

Nov 21, 2018
edited by heureka  Nov 21, 2018
edited by heureka  Nov 21, 2018