Question

1. let ( a ) be a positive integer. what is the greatest common divisor of ( a ) and ( a + 1 )? prove it. 8. use the euclidean algorithm to find the gcd of 51 and 87 and then to

Explanation:

---

For $\gcd(a, a+1)$:

Step1: Define common divisor $d$

Let $d = \gcd(a, a+1)$. By definition, $d \mid a$ and $d \mid (a+1)$.

Step2: Apply divisibility property

If $d$ divides two numbers, it divides their difference:
$$d \mid (a+1) - a$$
$$d \mid 1$$

Step3: Conclude $d=1$

The only positive divisor of 1 is 1, so $d=1$.

---

For $\gcd(51, 87)$ (Euclidean Algorithm):

Step1: Divide larger by smaller number

$$87 = 1 \times 51 + 36$$
So $\gcd(87,51) = \gcd(51,36)$

Step2: Divide 51 by 36

$$51 = 1 \times 36 + 15$$
So $\gcd(51,36) = \gcd(36,15)$

Step3: Divide 36 by 15

$$36 = 2 \times 15 + 6$$
So $\gcd(36,15) = \gcd(15,6)$

Step4: Divide 15 by 6

$$15 = 2 \times 6 + 3$$
So $\gcd(15,6) = \gcd(6,3)$

Step5: Divide 6 by 3

$$6 = 2 \times 3 + 0$$
When remainder is 0, the divisor is the gcd: $\gcd(6,3)=3$

Answer:

1. $\gcd(a, a+1) = 1$
2. $\gcd(51, 87) = 3$