+0  
 
+2
131
3
avatar+302 

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+679 
0

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

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

 

laugh

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

12 Online Users

avatar
avatar

New Privacy Policy

We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive information about your use of our website.
For more information: our cookie policy and privacy policy.