Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question

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

share|cite|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'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|cite|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


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.