Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What would the GCD of $3n + 2$ and $4n + 3$ be using Euclid's algorithm

share|improve this question

2 Answers 2

Hint: Note that $$-4(3n+2)+3(4n+3)=1$$

share|improve this answer
    
Probably the point of the exercise was to learn how to use the Euclidean algorithm symbolically - as instructed "by using Euclid's algorithm" (see Brett's answer). This gives the gcd without needing to obtain the above Bezout identity (i.e. without using the extended Euclidean algorithm). –  Math Gems Feb 9 '13 at 20:15
    
@MathGems: Yes and that's why I prefer Brett answer than mine. I tried to solve it by using Bézout's identity. You are right. +1 for him. –  Babak S. Feb 9 '13 at 20:21
    
That's not to say that other methods aren't useful. For example, the above apporach may be generalized to show that $\rm\: A(n,1)\:$ is a coprime pair for any $2 \times 2$ integer matrix $\rm\,A\,$ with determinant $ = 1,$ e.g. see this answer. –  Math Gems Feb 9 '13 at 20:32
    
I like this...it's good to have different approaches+1 –  amWhy Feb 10 '13 at 0:16

$$4n+3=(3n+2)+(n+1)$$ $$(3n+2)=3\cdot(n+1)-1$$

Since the remainder is $\pm 1$, the GCD is $1$.

Alternatively, note that the greatest common divisor must divide both numbers, as well as their difference. So if $d$ is the GCD, $d|(n+1)$. But $(n+1)$ cannot share any factors with $(4n+3)=4\cdot(n+1)-1$.

share|improve this answer
    
I hope the OP didn't mislead by my very short answer. –  Babak S. Feb 9 '13 at 20:23

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.