+0  
 
+2
446
3
avatar+435 

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
avatar
+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
avatar+770 
0

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

PartialMathematician  Nov 21, 2018
 #3
avatar+24089 
+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\)

 

laugh

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

23 Online Users