# prime numbers and greatest common divisor [duplicate]

Question: For any prime numbers $p$ and $q$, one has $\text{gcd}(p+q, q) = \text{gcd}(p,q)$. Is this statement true?

can someone explain why?

my reasoning: for any prime numbers, if an integer $q$ is added to it, the $\text{gcd}$ between $p+q$ and $q$ will still be $1$, since $q$ is still a prime number (prime = $1$(prime))

## marked as duplicate by Bill Dubuque, Pragabhava, Willie Wong, iadvd, suomynonAOct 22 '16 at 2:55

• – Tensor_Product Oct 19 '16 at 8:19
• @vikassrivastava hello! thank you so much for your help! i understand their answer but what I'm afraid is that my prof won't let me use this approach since it has not been taught yet:( – jellybeanbilly Oct 19 '16 at 8:31

$p$ and $q$ don't even have to be prime: $\gcd(a,b)=\gcd(a+b,b)$. The Euclidean algorithm is based on this property.

The reason for this relies on this simple observation, easily checked: if $D(a,b)$ denotes the set of common divisors of $a$ and $b$, we have $D(a+b,b)=D(a,b)$, and more generally, for any integer $q$, $$D(a+qb,b)=D(a,b).$$ This is quite obvious since any number which divides $a$ and $b$ divides $a+qb$ ($\supset$) and conversely, a number which divides $b$ and $a+qb$ divides $(a+qb)-qb=a$ ($\subset$).

• Thank you for your help!! I can better understand this qns :) – jellybeanbilly Oct 19 '16 at 11:14

We define the greatest common divisor (gcd) of two or more integers, when at least one of them is not zero, is the largest positive integer that divides the numbers without a remainder.

More precisely, given $a, b \in \mathbb{Z}$, their gcd, let us denote it by $d$ is the positive integer such that

1. $d|a$ and $d|b$, (where notation $x|y$ means $x$ divides $y$)
2. If $d^{'}$ is another positive integer which satisfies 1, that is $d^{'}$ also divides $a$ and $b$, then $d^{'}|d$

Now you want to show that $gcd(a,b)=gcd(a+b,b)$.

So let us apply the definition. Let $\alpha= gcd(a,b)$, we will show that $gcd(a+b,b)=\alpha$.

By definition $\alpha |a$ and $\alpha |b$, it implies that $\alpha |(a+b)$ so first condition is satisfied. You can check the second condition. Hence we have shown that $\alpha=gcd(a+b,b)$